C++ STL ：红黑树rb_tree源码剖析
STL关联式容器map、set、multimap、multiset，绝大部分操作如插入、修改、删除、搜索，都是由其内含的红黑树来完成的。
红黑树数据结构和算法的讲解见：
我下面会总结 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) { }
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
//操作符重载返回节点指针
pointer
operator->() 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;
}
_Self
operator++(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;
}
_Self
operator--(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
}
bool
operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ return _M_node == __x._M_node; }
bool
operator!=(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插入元素，不允许元素重复。
insert_equal允许RBTree中存在相同的节点，进行插入时，小于当前节点则向左走；等于或等于则向右走；如果有相同的元素，则插在相同元素的右侧，比如9的右子节点有一个10，则在插入10就插入在这个10的右子节点。
inert_unique不允许RBTree中存在相同的节点，在找到插入位置后，如果插入位置的父亲节点的值与待插入节点（插入一定插在一个空子树的位置）相同，则不插入。
红黑树存储值的类型是value_type,value_type定义是
typedef pair<const Key, T> value_type; //value_type的定义
pair存储键值对，第一个元素是Key，是const类型，不可改变的。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
25
0- 0
已为社区贡献8条内容
所有评论(0)