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。一开始写成int，看了很多源码才发现是这个原因，一定要注意。（Update on 2020-5-6：通过对源码阅读，终于彻底明白为何出现写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}

Update on 2020-5-6

当将Selector::operator()的返回值写为int时，执行时会在main()中的it = tree.find(1)时抛出Segmentation Fault。以下给出调用过程。

// main.cpp, main()
int main() {
    ...
    it = tree.find(1);
    ...
}

// stl_tree.h, std::_Rb_tree::find(const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k) {
        iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
        return (__j == end() || _M_impl._M_key_compare(__k,
            _S_key(__j._M_node))) ? end() : __j;
   }

// stl_tree.h, std::_Rb_tree::_M_lower_bound(_Link_type, _Link_type, const _Key&)
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_lower_bound(_Link_type __x, _Link_type __y, const _Key& __k) {
        while (__x != 0)
            if (!_M_impl._M_key_compare(_S_key(__x), __k))
                __y = __x, __x = _S_left(__x);
            else
                __x = _S_right(__x);
        return iterator(__y);
    }

在此处的 _M_impl._M_key_compare 也就是比较仿函数对象，在这里即less<int>对象。异常就是在这个函数里抛出的，可见问题出现在 _S_key(__x) 中。

// stl_tree.h, std::_Rb_tree::_S_key(_Const_Base_ptr)
static const _Key& _S_key(_Const_Base_ptr __x) {
    return _KeyOfValue()(_S_value(__x));
}

这里的 _KeyOfValue() 就是我们给的 Selector 了。所以在这里如果将 operator() 的返回值写为 int ，则这里将其以 const _Key& 返回，就是返回局部对象的引用，后面又在 less<int>::operator() 里面使用了这个引用（这个引用实际上指向一个已过期的栈上数据： _KeyOfValue() 的返回值），这个行为导致了Segmentation Fault。

# STL, 数据结构

STL中_Rb_tree的探索

分类

标签云

最新文章

文章

标签

Your browser is out-of-date!