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}