C++ STL ：红黑树rb_tree源码剖析

本文主要是介绍C++ STL ：红黑树rb_tree源码剖析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

STL关联式容器map、set、multimap、multiset，绝大部分操作如插入、修改、删除、搜索，都是由其内含的红黑树来完成的。

红黑树数据结构和算法的讲解见：

数据结构与算法：红黑树讲解-CSDN博客

我下面会总结  STL中rb_tree怎么实现的。

首先，rb_tree是红黑树，所以需要定义红色和黑色。

enum _Rb_tree_color { _S_red = false, _S_black = true };//红黑树的颜色 红色0 黑色1

然后需要定义 红黑树的节点。

struct _Rb_tree_node_base{typedef _Rb_tree_node_base* _Base_ptr; //节点指针typedef const _Rb_tree_node_base* _Const_Base_ptr;//const节点指针_Rb_tree_color    _M_color;//颜色_Base_ptr        _M_parent;//父节点_Base_ptr        _M_left;//左节点_Base_ptr        _M_right;//右节点static _Base_ptr//最小节点,即最左节点_S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT{while (__x->_M_left != 0) __x = __x->_M_left;//只要左节点不为空就一直向左走,取得最小节点return __x;}static _Const_Base_ptr_S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT{while (__x->_M_left != 0) __x = __x->_M_left;return __x;}static _Base_ptr//最大节点,即最右节点_S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT{while (__x->_M_right != 0) __x = __x->_M_right;return __x;}static _Const_Base_ptr_S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT{while (__x->_M_right != 0) __x = __x->_M_right;return __x;}};

  _Rb_tree_node_base定义了红黑树的节点类，从类中可以看出一个节点有颜色、父指针、左孩子指针、右孩子指针4个属性。然后定义了几个函数，可以找到以这个节点为根节点的红黑树的最大节点和最小节点。

   template<typename _Val>//红黑树的节点结构struct _Rb_tree_node : public _Rb_tree_node_base{typedef _Rb_tree_node<_Val>* _Link_type;//节点指针 指向数据节点#if __cplusplus < 201103L_Val _M_value_field;//数据类型_Val*_M_valptr(){ return std::__addressof(_M_value_field); }　const _Val*_M_valptr() const{ return std::__addressof(_M_value_field); }
#else__gnu_cxx::__aligned_buffer<_Val> _M_storage;//对齐处理后数据_Val*_M_valptr() //返回对应数据的指针{ return _M_storage._M_ptr(); }const _Val*_M_valptr() const{ return _M_storage._M_ptr(); }
#endif};

 _Rb_tree_node继承了_Rb_tree_node_base，在基础上添加了 一个数据类型，同时对C++11之前和之后值存储在

了解 

C++11之前（__cplusplus < 201103L）：值直接存储在节点内部，作为_Val _M_value_field。访问函数_M_valptr()返回这个值的指针，使用std::__addressof(_M_value_field)来获取其地址。

C++11及以后：值存储在__aligned_buffer<_Val> _M_storage内部。这样做很可能是为了确保数据的适当对齐。访问函数_M_valptr()通过调用_M_storage._M_ptr()返回值的指针，这个函数可能处理对齐问题并返回实际值的指针。

__aligned_buffer是一个模板结构，它提供了一种机制来按照类型_Val的对齐要求分配内存。在C++11及更高版本中，对齐是一个重要的概念，因为它影响数据的访问速度和效率。不正确的数据对齐可能导致性能下降或者在某些平台上引起错误。

_M_storage使用__aligned_buffer为类型_Val的对象提供存储空间。这种方式使得即使在栈上分配时，对象也能保证按照其对齐要求被正确地存储。这对于需要特定对齐要求的类型特别有用，比如SIMD类型（如SSE和AVX指令集中使用的类型）或者其他需要特定对齐以优化硬件性能的数据类型。

在C++11之前，没有标准的方法来指定或查询类型的对齐要求，因此_M_storage的使用也体现了对于老版本C++的向后兼容性考虑。在C++11及以后版本中，alignof和alignas关键字引入了对齐的标准支持，允许开发者更精确地控制数据的对齐方式。__aligned_buffer<_Val> _M_storage是一种高级技术，用于确保类型_Val的对象在红黑树节点内部以正确的对齐方式存储，这对于保持数据结构的性能和正确性是非常重要的。

rb_tree的迭代器 

template<typename _Tp>struct _Rb_tree_iterator{typedef _Tp  value_type;typedef _Tp& reference;typedef _Tp* pointer;typedef bidirectional_iterator_tag iterator_category; //迭代器类型typedef ptrdiff_t                  difference_type; //两个迭代器间距离typedef _Rb_tree_iterator<_Tp>        _Self;typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;//节点指针typedef _Rb_tree_node<_Tp>*           _Link_type;//节点指针//ctor_Rb_tree_iterator() _GLIBCXX_NOEXCEPT: _M_node() { }explicit_Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT: _M_node(__x) { }referenceoperator*() const _GLIBCXX_NOEXCEPT{ return *static_cast<_Link_type>(_M_node)->_M_valptr(); }//操作符重载返回节点指针pointeroperator->() const _GLIBCXX_NOEXCEPT{ return static_cast<_Link_type> (_M_node)->_M_valptr(); }_Self&operator++() _GLIBCXX_NOEXCEPT{_M_node = _Rb_tree_increment(_M_node);//这个函数的实现在4.9中没有找到 用一下其他版本的 其实现原理基本相似return *this;}_Selfoperator++(int) _GLIBCXX_NOEXCEPT{_Self __tmp = *this;_M_node = _Rb_tree_increment(_M_node);//++操作return __tmp;}_Self&operator--() _GLIBCXX_NOEXCEPT//--也没找到 {_M_node = _Rb_tree_decrement(_M_node);return *this;}_Selfoperator--(int) _GLIBCXX_NOEXCEPT{_Self __tmp = *this;_M_node = _Rb_tree_decrement(_M_node);return __tmp;}booloperator==(const _Self& __x) const _GLIBCXX_NOEXCEPT{ return _M_node == __x._M_node; }booloperator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT{ return _M_node != __x._M_node; }_Base_ptr _M_node;};

 rb_tree迭代器定义了5个STL迭代器必须定义的类型。

然后重载了一些运算符。

重点要看一下__rb_tree_iterator 的 operator++ 跟 operator--。它们分别调用了实际是调用__rb_tree_base_iterator的increment跟decrement。

迭代器前移/后移的时候会按key的顺序找到下一个/上一个结点。

void increment()
{if (node->right != 0) {node = node->right;while (node->left != 0)node = node->left;}else {base_ptr y = node->parent;while (node == y->right) {node = y;y = y->parent;}if (node->right != y)node = y;}
}void decrement()
{if (node->color == __rb_tree_red &&node->parent->parent == node)node = node->right;else if (node->left != 0) {base_ptr y = node->left;while (y->right != 0)y = y->right;node = y;}else {base_ptr y = node->parent;while (node == y->left) {node = y;y = y->parent;}node = y;}
}

rb_tree实现与普通的红黑树类似。

template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {// rb_tree的基本定义
protected:typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
public:typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef value_type& reference;typedef rb_tree_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef __rb_tree_iterator<value_type, reference, pointer> iterator;link_type header;// ...// 主要接口iterator begin() { return leftmost(); } // 返回最左边的结点(最小key)iterator end() { return header; }iterator insert_equal(const value_type& x); // 插入元素 并允许键值相同pair<iterator,bool> insert_unique(const value_type& x); // 插入元素 键值是独一无二的};

insert_equal插入元素，允许元素重复；insert_unique插入元素，不允许元素重复。

 

 

这篇关于C++ STL ：红黑树rb_tree源码剖析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---