自己如何创建网站,最近最火的电商平台是哪个,uniapp开发者中心,做房地产网站STL关联式容器map、set、multimap、multiset#xff0c;绝大部分操作如插入、修改、删除、搜索#xff0c;都是由其内含的红黑树来完成的。
红黑树数据结构和算法的讲解见#xff1a;
数据结构与算法#xff1a;红黑树讲解-CSDN博客
我下面会总结 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个属性。然后定义了几个函数可以找到以这个节点为根节点的红黑树的最大节点和最小节点。 templatetypename _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在基础上添加了 一个数据类型同时对C11之前和之后值存储在 了解 C11之前__cplusplus 201103L值直接存储在节点内部作为_Val _M_value_field。访问函数_M_valptr()返回这个值的指针使用std::__addressof(_M_value_field)来获取其地址。 C11及以后值存储在__aligned_buffer_Val _M_storage内部。这样做很可能是为了确保数据的适当对齐。访问函数_M_valptr()通过调用_M_storage._M_ptr()返回值的指针这个函数可能处理对齐问题并返回实际值的指针。 __aligned_buffer是一个模板结构它提供了一种机制来按照类型_Val的对齐要求分配内存。在C11及更高版本中对齐是一个重要的概念因为它影响数据的访问速度和效率。不正确的数据对齐可能导致性能下降或者在某些平台上引起错误。 _M_storage使用__aligned_buffer为类型_Val的对象提供存储空间。这种方式使得即使在栈上分配时对象也能保证按照其对齐要求被正确地存储。这对于需要特定对齐要求的类型特别有用比如SIMD类型如SSE和AVX指令集中使用的类型或者其他需要特定对齐以优化硬件性能的数据类型。 在C11之前没有标准的方法来指定或查询类型的对齐要求因此_M_storage的使用也体现了对于老版本C的向后兼容性考虑。在C11及以后版本中alignof和alignas关键字引入了对齐的标准支持允许开发者更精确地控制数据的对齐方式。__aligned_buffer_Val _M_storage是一种高级技术用于确保类型_Val的对象在红黑树节点内部以正确的对齐方式存储这对于保持数据结构的性能和正确性是非常重要的。 rb_tree的迭代器
templatetypename _Tpstruct _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(); }_Selfoperator() _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;}_Selfoperator--() _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_nodeValue rb_tree_node;typedef simple_allocrb_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_iteratorvalue_type, reference, pointer iterator;link_type header;// ...// 主要接口iterator begin() { return leftmost(); } // 返回最左边的结点(最小key)iterator end() { return header; }iterator insert_equal(const value_type x); // 插入元素 并允许键值相同pairiterator,bool insert_unique(const value_type x); // 插入元素 键值是独一无二的};
insert_equal插入元素允许元素重复insert_unique插入元素不允许元素重复。
