【C++：封装红黑树】C++ 红黑树封装实战：从零手把手实现MyMap与MySet

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一. 架构与实现总览设计框架深入源码细节1、 map 和 set 的框架核心源代码2、对比set和map的源码泛型编程的应用二. 核心设计思路红黑树的泛型复用1、红黑树的模板参数设计2、仿函数 KeyofT统一 key 的提取逻辑3、核心约束key 不可修改三. 基础组件实现红黑树、仿函数、迭代器iterator、map支持[]1、红黑树节点结构2、仿函数实现map/set 层2.1 set 的仿函数直接返回 key2.2 map 的仿函数提取 pair 的 first3、迭代器iterator3.1 iterator 实现思路分析3.2 迭代器iterator的实现4、map支持[]四. 封装红黑树、mySet 与 myMap 完整实现RBTree.hMymap.h:Myset.h:Test.cpp:结束语前言用过 STL 的朋友都知道map 和 set 是非常高频使用的关联式容器而其底层都依赖红黑树实现 —— 通过前面的 set 和 map 学习我们已经知道了 set 容器只需要传一个类型参数K而 map 需要传两个类型参数K/V。那你们知道红黑树如何通过泛型设计同时支撑 “key-only”set和 “key-value”map两种场景吗为什么 set 的迭代器不可修改而 map 只能修改 value 不能修改 key又是怎么让它们的迭代器实现不可修改的操作的set 和 map 的迭代器走的是中序遍历那又如何通过operator找到中序遍历的下一个结点呢本文结合 set 和 map 的源码框架与实现细节从红黑树的泛型改造入手一步步拆解 myMap 和 mySet 的封装逻辑包括关键的仿函数设计、迭代器实现、key 不可修改约束及 map 的 [] 运算符重载帮你吃透 STL 容器的底层封装思想。一. 架构与实现总览设计框架深入源码细节在封装红黑树实现MyMap与MySet之前我们需要先浅浅看一下map 和 set 的源代码虽然源代码非常乱而且难理解但是两者的源代码是辅助我们实现MyMap与MySet的关键SGI-STL30版本源代码 map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。1、map 和 set 的框架核心源代码stl_tree.h// stl_tree.h struct __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; }; template class Key, class Value, class KeyOfValue, class Compare, class Alloc alloc class rb_tree { protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_nodeValue rb_tree_node; typedef rb_tree_node* link_type; typedef Key key_type; typedef Value value_type; public: // insert⽤的是第⼆个模板参数左形参 pairiterator, 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 class Value struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_nodeValue* link_type; Value value_field; };stl_set.h// set #ifndef __SGI_STL_INTERNAL_TREE_H #include stl_tree.h #endif #include stl_set.h #include stl_multiset.h // stl_set.h template class Key, class Compare lessKey, class Alloc alloc class set { public: // typedefs: typedef Key key_type; typedef Key value_type; private: typedef rb_treekey_type, value_type, identityvalue_type, key_compare, Alloc rep_type; rep_type t; // red-black tree representing set };stl_map.h// map #ifndef __SGI_STL_INTERNAL_TREE_H #include stl_tree.h #endif #include stl_map.h #include stl_multimap.h // stl_map.h template class Key, class T, class Compare lessKey, class Alloc alloc class map { public: // typedefs: typedef Key key_type; typedef T mapped_type; typedef pairconst Key, T value_type; private: typedef rb_treekey_type, value_type, select1stvalue_type, key_compare, Alloc rep_type; rep_type t; // red-black tree representing map };2、对比set和map的源码泛型编程的应用虽然两者的底层都是用红黑树实现的但是看了上面的源代码我们发现set 和 map 第一个模板参数都是 Key区别就在于第二个模板参数value 对于 set 是 key对 map 而是 pairconst key, value通过下图对框架的分析我们可以看到源码中 rb_tree 用了一个巧妙的泛型思想实现rb_tree 不管是实现 key 的搜索场景还是 key/value 的搜索场景不是直接写死的而是由第二个模板参数 Value 决定 _rb_tree_node 中存储的数据类型。set 实例化rb_tree 时第二个模板参数给的是 Keymap 实例化rb_tree 时第二个模板参数给的是 pairconst key,T这样一颗红黑树既可以实现 key 搜索场景也可以实现 key/value 搜索场景的 map。大家一定要注意源码里面模板参数是用了 T 来代表 value而内部写的 value_type 不是我们日常 Key / value 场景中说的 value源码中的 value_type 反而是红黑树节点中存储的真实的数据类型。下面有图例解释rb_tree 第二个模板参数 Value 已经控制了红黑树结点中的存储的数据类型为什么还要传第一个模板参数 Key 呢尤其是 set两个模板参数是一样的这是很多人刚学习时的一个疑问。要注意的是对于 map 和 setfind/erase 时的函数参数都是Key所以第一个模板参数是传给 find/erase 等函数做形参的类型的。对于 set 而言两个参数是一样的但是对于 map 而言就完全不一样了map insert 的是 pair 对象但是 find 和 erase 的 Key 对象如果不传第一个模板参数 Key的确对于 set 没有任何影响但是 map 就无法实现 find 和 erase 接口了二. 核心设计思路红黑树的泛型复用STL 中 map 和 set 复用同一颗红黑树的核心是泛型编程 仿函数提取 key解决了 “一颗树适配两种数据场景” 的问题具体设计思路如下1、红黑树的模板参数设计红黑树需要支持存储两种数据类型set 场景存储单个 key如int、stringkey 不可修改map 场景存储 pairconst Key, Valuekey 不可修改因此红黑树的模板参数需抽象为 3 个templateclass K, class T, class KeyofT class RBTree { // Kfind/erase时的key类型统一接口参数 // T红黑树节点存储的实际数据类型set为 Kmap为 pairconst K, V // KeyofT仿函数从T中提取K解决T类型不统一的比较问题 };2、仿函数 KeyofT统一 key 的提取逻辑由于 T 的类型不固定K 或 pairK, V红黑树插入 / 查找在比较大小时无法直接获取 key虽然 pairK, V 自带比较大小的接口但是比较逻辑不是我们想要的所以我们需通过手动实现仿函数KeyofT统一提取由 map 和 set 分别实现适配set 的仿函数直接返回 keyT Kmap 的仿函数返回 pair 的 first 成员T pairconst K, V。3、核心约束key 不可修改set 的 key 是唯一标识需禁止修改红黑树存储const Kmap 的 key 是索引需禁止修改pair 的 first 设为 const Kvalue 可正常修改。三. 基础组件实现红黑树、仿函数、迭代器iterator、map支持[]1、红黑树节点结构节点存储模板类型 T包含左右子指针、父指针和颜色标记// 枚举结点颜色 enum Color { BLACK, // 黑色结点 RED // 红色结点 }; // 红黑树结点结构 templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _father; // 父节点指针回溯平衡需用到 RBTreeNodeT* _left; // 左子节点指针 RBTreeNodeT* _right; // 右子节点指针 Color _col; // 节点颜色 RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _father(nullptr) , _col(RED) //将初始化的结点颜色为红色满足插入要求(不能插入黑色结点) { } };2、仿函数实现map/set 层2.1 set 的仿函数直接返回 key#includeRBTree.h namespace xiaoye { templateclass K class Myset { // 仿函数从Tconst K中提取key struct SetKeyofT { const K operator()(const K key) { return key; } }; private: RBTreeK, const K, SetKeyofT _tree; //因为set的iterator迭代器是不支持修改的不管是普通迭代器还是const迭代器 //const本来就不支持修改那普通迭代器怎么实现呢 //我们可以把RBTree的第二个参数用const修饰 //这样RBTree的模板参数T就会变成const K //而T就是来影响迭代器interator的实例化的(typedef RBTreeInteratorT, T, T* Iterator;) }; }2.2 map 的仿函数提取 pair 的 first#includeRBTree.h namespace xiaoye { templateclass K, class V class Mymap { //仿函数从Tpairconst K, V中提取key struct MapKeyofT { const K operator()(const pairK, V kv) { return kv.first; } }; //因为RBTree中的insert需要比较大小虽然pair自带比较大小的接口但是比较逻辑不是我们想要的 //pair自带的比较大小逻辑是先比较first的大小如果相等还会比较 private: RBTreeK, pairconst K, V, MapKeyofT _tree; //虽然map的迭代器支持Value的修改但是不支持Key的修改不管是普通迭代器还是const迭代器 //所以我们只需要将RBTree的第二个参数修改为pairconst K, V即可 }; }3、迭代器iterator3.1 iterator 实现思路分析iterator 实现的大框架跟 list 的 iterator 思路是一致的用一个类型封装结点的指针再通过重载运算符实现迭代器像指针一样访问的行为。这里的难点是operator和operator–的实现之前使用部分我们分析了map和set的迭代器走的是中序遍历左子树-根结点-右子树那么begin()会返回中序第一个结点的iterator也就是10所在结点的迭代器。迭代器的核心逻辑就是不看全局只看局部只考虑当前中序局部要访问的下一个结点。迭代器时如果it指向的结点的右子树不为空代表当前结点已经访问完了要访问下一个结点是右子树的中序第一个一棵树中序第一个是最左结点所以直接找右子树的最左结点即可。迭代器时如果it指向的结点的右子树空代表当前结点已经访问完了且当前结点所在的子树也访问完了要访问的下一个结点在当前结点的祖先里面所以要沿着当前结点到根的祖先路径向上找。如果当前结点是父亲的左根据中序左子树-根结点-右子树那么下一个访问的结点就是当前结点的父亲如下图it指向2525右为空25是30的左所以下一个访问的结点就是30。如果当前结点时父亲的右根据中序左子树-根结点-右子树当前结点所在的子树访问完了当前结点所在父亲的子树也已经访问完了那么下一个访问的需要继续往根的祖先中去找直到找到孩子是父亲左的那个祖先就是中序要走的下一个结点。如下图it指向1515为空15是10的右15所在子树访问完了10所在的子树也访问完了继续往上找10是18的左那么下一个访问的结点就是18。end()如何表示呢如下图当it指向50时it时50是40的右40是30的右30是18的右18到根没有父亲没有找到孩子是父亲左的那个祖先这时父亲为空了那么我们就把it 中的结点指针置为nullptr我们用去充当end。需要注意的是stl源空红黑树增加了一个哨兵位头结点做为end()这哨兵位头结点和根互为父亲左指向最左结点右指向最右结点。相比我们用nullptr作为end()差别不大他能实现的我们也能实现。只是–end()判断到结点是空特殊处理一下让迭代器结点指向最右结点。具体参考迭代器一个个实现。迭代器–的实现跟的思路完全类似逻辑正好反过来即可因为他访问顺序是右子树-根结点-左子树。但是需要一个_root。set的iterator也不支持修改我们把set的第⼆个模板参数改成const K即可 RBTreeK,const K, SetKeyofT _t;map的iterator不支持修改key但是可以修改value我们把map的第二个模板参数pair的第⼀个参数改成const K即可 RBTreeK, pairconst K, V, MapKeyofT _t;支持完整的迭代器还有很多细节需要考虑具体参考下面的代码3.2 迭代器iterator的实现templateclass T, class Ref, class Ptr struct RBTreeInterator { typedef RBTreeInteratorT, Ref, Ptr Self; typedef RBTreeNodeT Node; Node* _node; Node* _root;//_root的作用就是为了辅助实现operator--的功能 //因为当特殊情况迭代器it为end()也就是_node为nullptr时 //我们原本想法是获取这棵树的最右结点但是此时_node为nullptr我们访问不了 //所以我们利用_root来获取这棵树的根节点 RBTreeInterator(Node* node, Node* root) :_node(node) ,_root(root) { } Self operator() { if (_node-_right) { //结点右子树不为空则中序下一个访问结点就是右子树的最左(最小)结点 Node* minright _node-_right; while (minright-_left) { minright minright-_left; } _node minright; return *this; } else { //结点右子树为空则我们需要一直往上查找直到孩子在父亲的左边停止此时的父亲就是中序下一个访问结点 Node* cur _node; Node* father cur-_father; while (father father-_right cur) { cur father; father cur-_father; } _node father; return *this; } } Self operator--() { if(_node nullptr) // end() { // --end()特殊处理走到中序最后一个结点整棵树的最右结点 Node* rightMost _root; while (rightMost rightMost-_right) { rightMost rightMost-_right; } _node rightMost; return *this; } else if (_node-_left) { //结点左子树不为空则中序上一个访问结点就是左子树的最右(最大)结点 Node* minleft _node-_left; while (minleft-_right) { minleft minleft-_right; } _node minleft; return *this; } else { //结点左子树为空则我们需要一直往上查找直到孩子在父亲的右边停止此时的父亲就是中序上一个访问结点 Node* cur _node; Node* father cur-_father; while (father father-_left cur) { cur father; father cur-_father; } _node father; return *this; } } Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node ! s._node; } }; // RBTreeK, pairK, V _tree; - // map // RBTreeK, K _tree; - // set4、map支持[]之前我们实现 insert 函数的返回类型为 bool即只考虑了是否插入成功但是无法获取插入失败的存在结点/插入成功的插入结点的位置。而如果map要支持[ ]就需要修改 insert 返回值支持修改 RBtree 中的 insert 返回值为pairIterator,bool Insert(const T data)这样我们就可以通过insert函数来辅助实现map的operator[]//利用Insert接口实现operator[] V operator[](const K Key) { pairiterator, bool ret _tree.Insert({ Key, V() }); return ret.first-second; //ret.first为迭代器iterator //通过迭代器来获取value值 }四. 封装红黑树、mySet 与 myMap 完整实现RBTree.h#include iostream using namespace std; // 枚举结点颜色 enum Color { BLACK, // 黑色结点 RED // 红色结点 }; // 红黑树结点结构 templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _father; // 父节点指针回溯平衡需用到 RBTreeNodeT* _left; // 左子节点指针 RBTreeNodeT* _right; // 右子节点指针 Color _col; // 节点颜色 RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _father(nullptr) , _col(RED) //将初始化的结点颜色为红色满足插入要求(不能插入黑色结点) { } }; templateclass T, class Ref, class Ptr struct RBTreeInterator { typedef RBTreeInteratorT, Ref, Ptr Self; typedef RBTreeNodeT Node; Node* _node; Node* _root;//_root的作用就是为了辅助实现operator--的功能 //因为当特殊情况迭代器it为end()也就是_node为nullptr时 //我们原本想法是获取这棵树的最右结点但是此时_node为nullptr我们访问不了 //所以我们利用_root来获取这棵树的根节点 RBTreeInterator(Node* node, Node* root) :_node(node) ,_root(root) { } Self operator() { if (_node-_right) { //结点右子树不为空则中序下一个访问结点就是右子树的最左(最小)结点 Node* minright _node-_right; while (minright-_left) { minright minright-_left; } _node minright; return *this; } else { //结点右子树为空则我们需要一直往上查找直到孩子在父亲的左边停止此时的父亲就是中序下一个访问结点 Node* cur _node; Node* father cur-_father; while (father father-_right cur) { cur father; father cur-_father; } _node father; return *this; } } Self operator--() { if(_node nullptr) // end() { // --end()特殊处理走到中序最后一个结点整棵树的最右结点 Node* rightMost _root; while (rightMost rightMost-_right) { rightMost rightMost-_right; } _node rightMost; return *this; } else if (_node-_left) { //结点左子树不为空则中序上一个访问结点就是左子树的最右(最大)结点 Node* minleft _node-_left; while (minleft-_right) { minleft minleft-_right; } _node minleft; return *this; } else { //结点左子树为空则我们需要一直往上查找直到孩子在父亲的右边停止此时的父亲就是中序上一个访问结点 Node* cur _node; Node* father cur-_father; while (father father-_left cur) { cur father; father cur-_father; } _node father; return *this; } } Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node ! s._node; } }; // RBTreeK, pairK, V _tree; - // map // RBTreeK, K _tree; - // set // 封装红黑树 templateclass K, class T, class KeyofT // Kfind/erase时的key类型统一接口参数 // T红黑树节点存储的实际数据类型set为 Kmap为 pairconst K, V // KeyofT仿函数从T中提取K解决T类型不统一的比较问题 class RBTree { public: typedef RBTreeNodeT Node; typedef RBTreeInteratorT, T, T* Iterator; typedef RBTreeInteratorT, const T, const T* ConstIterator; Iterator Begin() { Node* cur _root; while (cur cur-_left) { cur cur-_left; } return Iterator(cur, _root); } Iterator End() { return Iterator(nullptr, _root); } ConstIterator Begin() const { Node* cur _root; while (cur cur-_left) { cur cur-_left; } return ConstIterator(cur, _root); } ConstIterator End() const { return ConstIterator(nullptr, _root); } //bool Insert(const T data) pairIterator, bool Insert(const T data)//为了实现map的[]我们需要修改Insert的返回类型 { if (_root nullptr) { _root new Node(data); _root-_col BLACK; //return true; //return pairIterator, bool(Iterator(_root, _root), true); return { Iterator(_root, _root), true };//隐式类型转换 } KeyofT kof; //创建一个比较对象将对象像函数一样使用( 重载operator() ) Node* cur _root; Node* father nullptr; while (cur) { //根据是map还是set来调用对应的仿函数获取比较大小的值 //map就是获取kv.firstset就是获取key if(kof(cur-_data) kof(data)) { father cur; cur cur-_right; } else if(kof(cur-_data) kof(data)) { father cur; cur cur-_left; } else { //return false; return { Iterator(cur, _root), false }; } } cur new Node(data); Node* newnode cur; //提前记录cur(插入数据)的位置后续旋转等操作cur会发生变化为了返回的时候能找到插入数据的位置 if (kof(father-_data) kof(data)) { father-_right cur; } else { father-_left cur; } cur-_father father; while (father father-_col RED) { Node* grandfather father-_father; if (grandfather-_left father) { // g // p u Node* uncle grandfather-_right; if (uncle uncle-_col RED) { // 情况一uncle存在且为红色 // 变色继续向上处理 father-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; father cur-_father; //若此时grandfather为根节点则father为空需要结束判断则可以在循环条件中加上father判空 } else { if (father-_left cur) // 单旋变色 { // g // p u // c //cur在father左边则进行右单旋 RotateR(grandfather); father-_col BLACK; grandfather-_col RED; } else // 双旋变色 { // g // p u // c //cur在father右边则进行左右双旋 RotateL(father); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } else { //uncle结点在father左侧的核心操作和上面基本一致 // g // u p Node* uncle grandfather-_left; if (uncle uncle-_col RED) { uncle-_col father-_col BLACK; grandfather-_col RED; cur grandfather; father cur-_father; } else { if (father-_right cur) // 单旋变色 { // g // u p // c //cur在father右边则进行左单旋 RotateL(grandfather); father-_col BLACK; grandfather-_col RED; } else // 双旋变色 { // g // u p // c //cur在father左边则进行右左单旋 RotateR(father); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_col BLACK; //return true; return { Iterator(newnode, _root), true }; } //红黑树的查找Find Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; // 找到返回节点指针 } } return nullptr; // 未找到 } //红黑树的结点总数size() int size() { return _size(_root); } //红黑树的高度height() int height() { return _height(_root); } private: //右单旋 void RotateR(Node* father) { Node* subL father-_left; Node* subLR subL-_right; Node* prev_father father-_father; subL-_right father; father-_father subL; father-_left subLR; if (subLR) { subLR-_father father; } if (prev_father nullptr) { _root subL; _root-_father nullptr; } else { if (prev_father-_left father) { prev_father-_left subL; subL-_father prev_father; } else { prev_father-_right subL; subL-_father prev_father; } } } //左单旋 void RotateL(Node* father) { Node* subR father-_right; Node* subRL subR-_left; Node* prev_father father-_father; subR-_left father; father-_father subR; father-_right subRL; if (subRL) { subRL-_father father; } if (prev_father nullptr) { _root subR; _root-_father nullptr; } else { if (prev_father-_left father) { prev_father-_left subR; subR-_father prev_father; } else { prev_father-_right subR; subR-_father prev_father; } } } int _size(const Node* root) { if (root nullptr) { return 0; } return _size(root-_left) _size(root-_right) 1; } int _height(const Node* root) { if (root nullptr) { return 0; } int left_h _height(root-_left); int right_h _height(root-_right); return left_h right_h ? left_h 1 : right_h 1; } private: Node* _root nullptr; };Mymap.h:#includeRBTree.h namespace xiaoye { templateclass K, class V class Mymap { //仿函数从Tpairconst K, V中提取key struct MapKeyofT { const K operator()(const pairK, V kv) { return kv.first; } }; //因为RBTree中的insert需要比较大小虽然pair自带比较大小的接口但是比较逻辑不是我们想要的 //pair自带的比较大小逻辑是先比较first的大小如果相等还会比较 public: typedef typename RBTreeK, pairconst K, V, MapKeyofT::Iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyofT::ConstIterator const_iterator; //一定要注意下面的成员变量类型为了使迭代器不支持修改Key加上const修饰 //则这里也需要同步修改否则下面begin/end函数的返回类型会不匹配。 //如果这里不修改则会导致 return _tree.Begin()返回类型是 RBTreeK, pairconst K, V, MapKeyofT //而函数返回类型iterator为 RBTreeK, pairconst K, V, MapKeyofT iterator begin() { return _tree.Begin(); } iterator end() { return _tree.End(); } const_iterator begin() const { return _tree.Begin(); } const_iterator end() const { return _tree.Begin(); } pairiterator, bool insert(const pairK, V kv) { return _tree.Insert(kv); } //利用Insert接口实现operator[] V operator[](const K Key) { pairiterator, bool ret _tree.Insert({ Key, V() }); return ret.first-second; //ret.first为迭代器iterator //通过迭代器来获取value值 } private: RBTreeK, pairconst K, V, MapKeyofT _tree; //虽然map的迭代器支持Value的修改但是不支持Key的修改不管是普通迭代器还是const迭代器 //所以我们只需要将RBTree的第二个参数修改为pairconst K, V即可 }; }Myset.h:#includeRBTree.h namespace xiaoye { templateclass K class Myset { // 仿函数从Tconst K中提取key struct SetKeyofT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyofT::Iterator iterator; typedef typename RBTreeK, const K, SetKeyofT::ConstIterator const_iterator; //一定要注意下面的成员变量类型为了使迭代器不支持修改加上const修饰 //则这里也需要同步修改否则下面begin/end函数的返回类型会不匹配。 //如果这里不修改则会导致 return _tree.Begin()返回类型是 RBTreeK, const K, SetKeyofT //而函数返回类型iterator为 RBTreeK, const K, SetKeyofT iterator begin() { return _tree.Begin(); } iterator end() { return _tree.End(); } const_iterator begin() const { return _tree.Begin(); } const_iterator end() const { return _tree.Begin(); } pairiterator, bool insert(const K key) { return _tree.Insert(key); } private: RBTreeK, const K, SetKeyofT _tree; //因为set的iterator迭代器是不支持修改的不管是普通迭代器还是const迭代器 //const本来就不支持修改那普通迭代器怎么实现呢 //我们可以把RBTree的第二个参数用const修饰 //这样RBTree的模板参数T就会变成const K //而T就是来影响迭代器interator的实例化的(typedef RBTreeInteratorT, T, T* Iterator;) }; }Test.cpp:#includeMymap.h #includeMyset.h void test_set() { xiaoye::Mysetint s; s.insert(5); s.insert(1); s.insert(3); s.insert(4); s.insert(2); xiaoye::Mysetint::iterator it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; for (auto e : s) { cout e ; } cout endl; //利用正向迭代器实现反向迭代器的逻辑(operator--) xiaoye::Mysetint::iterator rit s.end(); while (rit ! s.begin()) { //这里非常巧妙因为一开始rit为 s.end() 也就是空空是不能解引用的 //所以我们可以先--rit获取到set中序的最后一个位置避免访问空 //当rit为 s.begin() 的前一个位置时先--rit就可以获取到set中序的第一个位置的数据了 --rit; cout *rit ; } } void test_map() { xiaoye::Mymapstring, string dict; dict.insert({ sort, 排序 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); xiaoye::Mymapstring, string::iterator mit dict.begin(); while (mit ! dict.end()) { cout mit-first : mit-second endl; mit; } cout endl; dict[left] 左边、剩余; dict[insert] 插入; for (auto e : dict) { cout e.first : e.second endl; } } int main() { cout 测试set: endl; test_set(); cout endl; cout ------------------ endl; cout 测试map: endl; test_map(); return 0; }结束语到此通过封装红黑树来模拟实现 myMap 和 mySet 就讲解完了。myMap 和 mySet 的封装核心是红黑树的泛型复用通过模板参数 T 适配不同数据类型用仿函数KeyofT统一 key 提取逻辑再通过迭代器封装实现双向遍历。其中key 不可修改的约束、map 的 [] 运算符重载、迭代器的 /-- 实现都是 STL 容器设计的经典细节。掌握这套封装逻辑不仅能理解 STL 容器的底层实现更能学会 “泛型编程 接口抽象” 的设计思想。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/