STL中_Rb_tree的探索

我們知道STL中我們常用的set與multiset和map與multimap都是基於紅黑樹。本文介紹了它們的在STL中的底層數據結構_Rb_tree的直接用法與部分函數。難點主要是_Rb_tree的各個參數的確定。

特別註意在如下代碼的Selector類用於從Node中選出用於排序的key值，這個仿函數必須返回const int&而不能是int，否則less<int>::operator(const int&, const int&)會拋出segmentation fault。由於源碼中邏輯比較複雜，但是可以觀察到內部涉及這方面的地方經常使用到指針。所以可以推測是因為引用了已經釋放的局部變數所以才拋出的segmentation fault。一開始寫成int，看了很多源碼才發現是這個原因，一定要註意。

接下來是樣例代碼，裡面都有註釋了。

#include <iostream>
#include <iomanip>

// 原則上不要直接引用這個頭文件，這裡只是為了測試
#include <bits/stl_tree.h>

using namespace std;

struct Node {
    int first, second;
    Node(int _first, int _second) : first(_first), second(_second){};

    friend ostream& operator<<(ostream& outs, const Node& node) {
        outs << '{' << node.first << ',' << node.second << '}';
        return outs;
    }
};

template <class T>
struct Selector {
    // MUST return const int&, not int.
    // if return int, segmentation fault will occur.
    // I have spent much time because of this.
    const int& operator()(const T& obj) const {
        return obj.first;
    }
};

int main() {
    // _Rb_tree: red-black tree in STL.
    using tree_type = _Rb_tree<int, Node, Selector<Node>, less<int>>;
    using iterator_type = tree_type::iterator;
    using result_pair_type = pair<tree_type::iterator, bool>;
    tree_type tree;

    // 插入元素Node(1, 2)
    result_pair_type res = tree._M_insert_unique(Node(1, 2));
    cout << "insert address = " << res.first._M_node << endl;
    cout << "insert result = " << boolalpha << res.second << endl; // true

    iterator_type it = tree.begin();
    cout << "begin address = " << it._M_node << endl;

    it = tree.find(1);
    cout << "address = " << it._M_node << ", value = " << *it << endl;

    // 再插入元素Node(1, 2)但是因為調用的是insert_unique
    // 它不會添加重覆值，所以插入會被拒絕
    res = tree._M_insert_unique(Node(1, 2));
    cout << "insert result = " << boolalpha << res.second << endl; // false

    // 再插入元素Node(1, 2)但這次調用insert_equal
    // multiset和multimap就是利用這個函數來插入重覆值
    // 也就是這個函數允許重覆值，所以插入成功
    tree._M_insert_equal(Node(1, 3));
    cout << "size = " << tree.size() << endl; // 大小就變為2

    pair<iterator_type, iterator_type> result = tree.equal_range(1);
    for (iterator_type ite = result.first; ite != result.second; ++ite) {
        cout << "address = " << ite._M_node << ", value = " << *ite << endl;
    }
    
    return 0;
}

程式的輸出為（記憶體地址不定）：

insert address = 0xf91be0
insert result = true
begin address = 0xf91be0
address = 0xf91be0, value = {1,2}
insert result = false
size = 2
address = 0xf91be0, value = {1,2}
address = 0xf91c10, value = {1,3}