【C++----红黑树封装set / map底层大致封装】在C++的世界里，每一次编译都是对智慧的考验，每一次调试都是对耐心的磨砺。开发者们在这里不断学习、成长，用代码编织出一个个精彩纷呈的故事。

Ne0inhk

— 15 min read
【C++----红黑树封装set / map底层大致封装】在C++的世界里，每一次编译都是对智慧的考验，每一次调试都是对耐心的磨砺。开发者们在这里不断学习、成长，用代码编织出一个个精彩纷呈的故事。

红黑树 set / map封装

在这里插入图片描述

1 封装红⿊树实现set和map

1.1对底层源码及框架分析

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件
中。map和set的实现结构框架核⼼部分截取出来如下：

// set#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_set.h>#include<stl_multiset.h>// map#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_map.h>#include<stl_multimap.h>// stl_set.htemplate<classKey,classCompare= less<Key>,classAlloc= alloc>classset{public:// typedefs:typedef Key key_type;typedef Key value_type;private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing set};// stl_map.htemplate<classKey,classT,classCompare= less<Key>,classAlloc= alloc>classmap{public:// typedefs:typedef Key key_type;typedef T mapped_type;typedef pair<const Key, T> value_type;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing map};// stl_tree.hstruct__rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr; color_type color; base_ptr parent; base_ptr left; base_ptr right;};// stl_tree.htemplate<classKey,classValue,classKeyOfValue,classCompare,classAlloc= alloc>classrb_tree{protected:typedefvoid* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;typedef Key key_type;typedef Value value_type;public:// insert⽤的是第⼆个模板参数左形参 pair<iterator,bool>insert_unique(const value_type& x);// erase和find⽤第⼀个模板参数做形参 size_type erase(const key_type& x); iterator find(const key_type& x);protected: size_type node_count;// keeps track of size of tree link_type header;};template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;};
• 通过下图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。

• set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是pair<const key, T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。

•源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。

•那么RBTree中的第一个Key是用来干什么的呢？特别是set都有了数据类型为什么还要传多一个相同的数据类型呢？要注意的是对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和ease的是Key对象。
在这里插入图片描述

2. 模拟实现map和set

2.1 实现出复⽤红⿊树的框架，并⽀持insert

•参考源码框架，map和set复⽤之前我们实现的红⿊树。

• 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的 数据类型，我们使⽤T。

•其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K,
V>，那么insert内部进⾏插⼊逻辑⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任何时候只⽐较key，所以我们在map和set层分别实现⼀个mapKeyofpair和SetKeyofpair的仿函数传给RBtree的Keyofpair，然后RBtree中通过Keyofpair仿函数取出T类型对象中的key，再进⾏⽐较，具体细节参考如下代码实现。

~map.h
MapKeyOfT
仿函数是为了红黑树比较时能够区分map和set，传MapKeyofpair时，用仿函数去比较就能够区分你到底是传Key过来、还是传pair<K,V>过来

template<classT1,classT2>booloperator<(const pair<T1,T2>& lhs,const pair<T1,T2>& rhs){return lhs.first<rhs.first ||(!(rhs.first<lhs.first)&& lhs.second<rhs.second);}//pair支持的重载//这里使用的重点不在pair，也可以直接用库函数来包含<utility>//map.htemplate<classK,classV>classmap{structMapKeyofpair{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:boolinsert(const pair<K, V>& kv){return _t.Insert(kv);////底层是红黑树，调用红黑树的insert就行了}private: RBTree<K, pair<K, V>, MapKeyofpair> _t;};

~set.h
SetKeyofpair
仿函数是为了红黑树比较时能够区分map和set，传MapKeyofpair时，用仿函数去比较就能够区分你到底是传Key过来、还是传pair<K,V>过来

template<classK>classset{structSetKeyofT{const K&operator()(const K& key){return key;}};public:boolinsert(const K& key){return _t.Insert(key);//底层是红黑树，调用红黑树的insert就行了}private: RBTree<K, K, SetKeyofpair> _t;};

~RBtree.h

enumColour{ RED, BLACK };template<classT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr){}};// 实现步骤：// 1、实现红⿊树// 2、封装map和set框架，解决Keyofpair// 3、iterator// 4、const_iterator// 5、key不⽀持修改的问题// 6、operator[]template<classK,classT,classKeyOfT>classRBtree{private:typedef RBTreeNode<T> Node; Node* _root =nullptr;public:boolInsert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returntrue;} KeyOfT kot; Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(data); Node* newnode = cur;// 新增结点。颜⾊给红⾊ cur->_col = RED;if(kot(parent->_data)<kot(data)){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;//...returntrue;}}

2.2 ⽀持iterator的实现

红黑树的迭代器可不是++就能得到下一个结点的。
terator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。

这⾥的难点是operator++和operator–的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10所在结点的迭代器。

2.2.1红黑树迭代器结构

template<classT,classRef,classPtr>structRBtreeIterator{typedef RBTreeNode<T> Node;typedef RBtreeIterator<T, Ref, Ptr> Self; Node* _node; Node* _root;RBtreeIterator(Node* node, Node* root):_node(node),_root(root){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};

2.2.2 迭代器++

迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点
【说明】:中序走法
------------左结点->根结点->右结点

情况一（右子树不为空）++：如果指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。

情况二（右子树为空）++：如果指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上找。

分析：

在这里插入图片描述


右子树为空又可以分成两种情况
情况一：结点是父亲的左
如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结点的⽗亲；如下图：如果it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
情况二：结点是父亲的右
• 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：如果it指向15，15右为空，15是10的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个访问的结点就是18。

迭代器end()如何实现呢？
end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针置为nullptr，我们⽤nullptr去充当end。这里雨源码不同，我们是用nullptr来实现end()，而源码使用哨兵位头结点实现end()

stl源码实现迭代器end()

在这里插入图片描述


end()不为nullptr,为header(头结点)

在这里插入图片描述

iterator++代码实现

Self operator++(){if(_node->_right){// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点 Node* min = _node->_right;while(min->_left){ min = min->_left;} _node = min;}else{// 右为空，祖先里面孩子是父亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;}

2.2.4 iterator–

迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树，具体参考下⾯代码实现。

特殊处理：
–end()的之后,是走到最后一个结点（最右结点）。

 Self operator--(){if(_node ==nullptr)// --end(){// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点 Node* rightMost = _root;while(rightMost && rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}elseif(_node->_left){// 左子树不为空，中序左子树最后一个 Node* rightMost = _node->_left;while(rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}else{// 孩子是父亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;}

3 注意须知 [实现map/set]

set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree<K,const K, SetKeyOfT> _t;

• map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;

3.1 map[]实现

map要⽀持[]主要需要修改insert返回值⽀持，修改RBtree中的insert返回值为

V&operator[](const K& key){ pair<iterator,bool> ret =insert({ key,V()});return ret.first->second;}

3.2代码实现

//map.htemplate<classK,classV>classmap{structmapKeyofpair{const K&operator()(const pair<K,V>& kv){return kv.first;}};public:typedeftypenameRBtree<K, pair<const K, V>, mapKeyofpair>::Iterator iterator;typedeftypenameRBtree<K, pair<const K, V>, mapKeyofpair>::ConstIterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} pair<iterator,bool>insert(const pair<K, V>& kv){return _t.insert(kv);}private: RBtree<K, pair<const K, V>, mapKeyofpair> _t ;};//set.htemplate<classK>classset{structsetKeyofpair{const K&operator()(const K& key){return key;}};public:typedeftypenameRBtree<K,const K, setKeyofpair>::Iterator iterator;typedeftypenameRBtree<K,const K, setKeyofpair>::ConstIterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} pair<iterator,bool>insert(const K& data){return _t.insert(data);}private: RBtree<K,const K, setKeyofpair> _t;};//RBtree.henumColour{ RED, BLACK };//红黑树结点template<classT>structRBTreeNode{// 这里更新控制平衡也要加入parent指针 T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classT,classRef,classPtr>structRBtreeIterator{typedef RBTreeNode<T> Node;typedef RBtreeIterator<T, Ref, Ptr> Self; Node* _node; Node* _root;RBtreeIterator(Node* node, Node* root):_node(node),_root(root){} Self operator++(){if(_node->_right){// 右不为空，中序下一个访问的节点是右子树的最左(最小)节点 Node* min = _node->_right;while(min->_left){ min = min->_left;} _node = min;}else{// 右为空，祖先里面孩子是父亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Self operator--(){if(_node ==nullptr)// --end(){// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点 Node* rightMost = _root;while(rightMost && rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}elseif(_node->_left){// 左子树不为空，中序左子树最后一个 Node* rightMost = _node->_left;while(rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}else{// 孩子是父亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classK,classT,classKeyofpair>classRBtree{typedef RBTreeNode<T> Node;public:typedef RBtreeIterator<T, T&, T*> Iterator;typedef RBtreeIterator<T,const T&,const T*> ConstIterator; Iterator begin(){ Node* node = _root;while(node && node->_left){ node = node->_left;}returnIterator(node,_root);} ConstIterator begin()const{ Node* node = _root;while(node && node->_left){ node = node->_left;}returnConstIterator(node,_root);} Iterator end(){returnIterator(nullptr,_root);} ConstIterator end()const{returnConstIterator(nullptr,_root);} pair<Iterator,bool>insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;return{Iterator(_root, _root),true};} Keyofpair com; Node* cur = _root; Node* parent =nullptr;while(cur){if(com(cur->_data)<com(data)){ parent = cur; cur = cur->_right;}elseif(com(cur->_data)>com(data)){ parent = cur; cur = cur->_left;}else{return{Iterator(cur, _root),false};}} cur =newNode(data); Node* newnode = cur; cur->_col = RED;if(com(parent->_data)<com(data)){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;while(parent && parent->_col == RED){ Node* grandparent = parent->_parent;if(parent == grandparent->_left){// g// p u Node* uncle = grandparent->_right;if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandparent->_col = RED;// 继续往上处理 cur = grandparent; parent = cur->_parent;}else{if(cur == parent->_left){// g// p u// cRotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandparent); cur->_col = BLACK; grandparent->_col = RED;}break;}}else{ Node* uncle = grandparent->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandparent->_col = RED;// 继续往上处理 cur = grandparent; parent = cur->_parent;}else{//旋转+变色if(cur == parent->_right){// g// u p// cRotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED;}else{// g// u p// c//需双旋+变色RotateR(parent);RotateL(grandparent); cur->_col = BLACK; grandparent->_col = RED;}break;//旋转完后根或者部分根是黑色的不用在意根之前是黑或是红或是空}}} _root->_col = BLACK;return{Iterator(newnode, _root),true};}voidRotateR(Node * parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* pParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(parent == _root){ _root = subL; subL->_parent =nullptr;}else{if(pParent->_left == parent){ pParent->_left = subL;}else{ pParent->_right = subL;} subL->_parent = pParent;}}voidRotateL(Node * parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(parentParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(parent == parentParent->_left){ parentParent->_left = subR;}else{ parentParent->_right = subR;} subR->_parent = parentParent;}} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}intHeight(){return_Height(_root);}intSize(){return_Size(_root);}private:int_Height(Node* root){if(root ==nullptr)return0;int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}int_Size(Node* root){if(root ==nullptr)return0;return_Size(root->_left)+_Size(root->_right)+1;}private: Node* _root =nullptr;};

最后在这悠长的叙述即将抵达彼岸之时，愿以一曲未了的旋律，轻拂你心灵的涟漪。我们共同走过的这段旅程，如同繁星点缀的夜空，每一颗星辰都承载着故事，每一缕光芒都映照着心迹。此刻，虽言尽而意未尽，但愿这份文字的余温，能伴你度过未来的每一个静！！！

Read more

工程必学！红黑树从概念到手撕实现，讲透平衡树的 “折中智慧”----《Hello C++ Wrold!》(22)--(C/C++)

工程必学！红黑树从概念到手撕实现，讲透平衡树的 “折中智慧”----《Hello C++ Wrold!》(22)--(C/C++)

文章目录 * 前言 * 红黑树的概念 * 红黑树的性质 * AVL树跟红黑树的比较 * 红黑树的模拟实现 * 插入新节点的处理 * 红黑树的验证 * 作业部分 前言 学完 AVL 树后，你是不是也有过这样的疑惑：明明 AVL 树是 “严格平衡” 的二叉搜索树，查询效率还更高，可为啥 C++ STL 的map/set、Linux 内核里的关键结构，偏偏选红黑树而不用它？难道 “更平衡” 反而成了缺点？ 其实答案藏在 “工程取舍” 里 —— 红黑树的精髓，从来不是 “比 AVL 树更平衡”，而是 “在‘查询效率’和‘写入开销’之间找最优解”。它不像 AVL 树那样追求 “极致的矮”，而是用

By Ne0inhk
【C++】现代C++的新特性constexpr，及其在C++14、C++17、C++20中的进化

【C++】现代C++的新特性constexpr，及其在C++14、C++17、C++20中的进化

各位读者大佬好，我是落羽！一个坚持不断学习进步的学生。 如果您觉得我的文章还不错，欢迎多多互三分享交流，一起学习进步！ 也欢迎关注我的blog主页:落羽的落羽 文章目录 * 一、从C++11引入 * 1. 常量表达式和constexpr关键字的概念 * 2. constexpr修饰函数 * 二、constexpr在C++14中的进化 * 三、constexpr在C++17中的进化 * 四、constexpr在C++20中的进化 一、从C++11引入 1. 常量表达式和constexpr关键字的概念 现代C++，从C++11开始，引入了常量表达式和constexpr关键字的概念，并且在之后的C++标准中不断更新 常量表达式是指，值不会改变并且在编译过程中就能得到计算结果的表达式。用字面量、常量表达式初始化的const对象都是常量表达式。但是用变量初始化的const对象不是常量表达式。 constint a =1;//a是常量表达式constint b = a +1;//b是常量表达式int c

By Ne0inhk
自动驾驶中间件iceoryx - （附录）C++ 内存模型与原子操作详解

自动驾驶中间件iceoryx - （附录）C++ 内存模型与原子操作详解

附录A: C++ 内存模型与原子操作详解 📚 本附录内容 本附录深入讲解 C++ 11引入的内存模型（Memory Model）和原子操作（Atomic Operations）， 这是理解 iceoryx 等高性能进程间通信系统无锁机制的核心基础。 适合读者：想深入理解 acquire/release 内存序语义需要实现或优化无锁数据结构想理解 iceoryx 内部同步机制的原理对并发编程和性能优化感兴趣的开发者 与主文档的关系：本附录是 第5章 同步与通知机制 的扩展阅读主文档 5.2.3 节提供了简化版本，适合快速学习本附录提供完整的技术细节和深入分析 目录 * A.1 为什么需要内存序 * A.2 C++ 内存序类型 * A.3 实例：生产者-消费者 * A.4 iceoryx 中的内存序使用 * A.5

By Ne0inhk
【C++】深入拆解二叉搜索树：从递归与非递归双视角，彻底掌握STL容器的基石

【C++】深入拆解二叉搜索树：从递归与非递归双视角，彻底掌握STL容器的基石

【C++】深入拆解二叉搜索树：从递归与非递归双视角，彻底掌握STL容器的基石 * 摘要 * 目录 * 一、概念 * 二、 性能分析 * 三、key结构非递归模拟实现 * 1. 二叉搜索树的插入 * 2. 二叉搜索树的查找 * 3. 二叉搜索树的删除 * 4. 二叉搜索树的中序遍历 * 四、key结构递归的模拟实现 * 1. 递归与非递归二叉搜索树核心操作的对比 * 2. 递归插入 * 3. 递归查找 * 4. 递归删除 * 总结 摘要 二叉搜索树（BST）是一种重要的数据结构，它通过"左子树所有节点值小于根节点，右子树所有节点值大于根节点"的特性实现高效的元素组织。本文详细解析了BST的核心概念、性能特点，并分别通过非递归和递归两种方式完整实现了插入、查找、删除等关键操作，深入探讨了指针引用在递归实现中的巧妙应用，以及两种实现方式在时间复杂度、空间复杂度和适用场景上的差异。 目录

By Ne0inhk