目录引言源码及框架分析头文件依赖stl_set.h 源码核心stl_map.h 源码核心stl_tree.h 红黑树底层源码框架核心思想解读常见疑问既然 Value 控制节点存储类型为什么还需要第一个模板参数 Key模拟实现map和set1.实现出可复用红黑树的框架并支持insert和find一初始版本耦合 pair 的红黑树仅支持 map二搭建初始 set、map 外层框架三修改红黑树节点与类模板四修改 set 与 map新增 key 提取仿函数五扩展红黑树模板参数接收 KeyOfT 仿函数2.支持iterator实现2.1.iterator核心源代码2.2.iterator实现思路分析3.map支持[]4.qiu::map和qiu::set实现RBTree.hmap.hset.htest.h结语引言提示阅读本文前需要掌握红黑树————C 高阶数据结构红黑树万字详解完整原理推导 插入实现 完整性校验【STL 底层】-CSDN博客序列式容器vector/list/deque底层依托连续空间、双向链表实现而关联式容器 map、set 依靠平衡搜索树完成数据管理。SGI-STL 选择红黑树作为底层结构借助泛型与仿函数设计用一套红黑树同时支撑 set /map/multiset /multimap这套复用思想非常值得拆解学习。本篇将对照 SGI-STL 原始源码从零模拟实现可复用红黑树逐层封装出简易版 map 与 set理清底层设计思路。那么话不多说接下来进入正文——————————​源码及框架分析在讲解序列式容器时我多次提到过阅读 STL 源码的方式本篇直接提取 SGI-STL 核心源码进行分析。头文件依赖//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从头文件依赖可以看出map和set底层共用同一套数据结构核心实现都放在stl_tree.h也就是红黑树。stl_set.h 源码核心#ifndef __STL_LIMITED_DEFAULT_TEMPLATES template class Key, class Compare lessKey, class Alloc alloc #else template class Key, class Compare, class Alloc alloc #endif class set { public: // 类型别名 typedef Key key_type; typedef Key value_type; private: typedef rb_treekey_type, value_type, identityvalue_type, Compare, Alloc rep_type; rep_type t; // 承载set的红黑树 };这里对 Key 设置两个别名key_type和value_type目的是和 map 的设计保持统一。key_type用于查找、删除接口value_type用于插入接口。stl_map.h 源码核心#ifndef __STL_LIMITED_DEFAULT_TEMPLATES template class Key, class T, class Compare lessKey, class Alloc alloc #else template class Key, class T, class Compare, class Alloc alloc #endif class map { public: // 类型别名 typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pairconst Key, T value_type; private: typedef rb_treekey_type, value_type, select1stvalue_type, Compare, Alloc rep_type; rep_type t; // 承载map的红黑树 };重点map 的 value_type 并不是 T而是pairconst Key, T。const Key保证外部无法修改 pair 中的 key避免破坏红黑树有序性这也是最关键的设计约束。 set 与 map 采用这套统一范式是为了方便上层泛型编程。stl_tree.h 红黑树底层源码// 红黑树颜色定义 typedef bool __rb_tree_color_type; const __rb_tree_color_type __rb_tree_red false; const __rb_tree_color_type __rb_tree_black true;补充SGI-STL 使用 bool 常量标记颜色我们自己实现时常选用枚举只是编码风格差异。// 红黑树节点基类只保存指针关系不存储业务数据 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 Value struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_nodeValue* link_type; Value value_field; };采用基类 派生模板节点的分离设计把指针拓扑和存储数据解耦。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 simple_allocrb_tree_node, Alloc rb_tree_node_allocator; typedef __rb_tree_color_type color_type; public: typedef Key key_type; typedef Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type reference; typedef const value_type const_reference; typedef rb_tree_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; public: // 插入、删除接口 pairiterator,bool insert_unique(const value_type x); size_type erase(const key_type x); // 查找接口 iterator find(const key_type x); };框架核心思想解读​结合上图的调用链路可以清晰看到 SGI-STL 的rb_tree依靠泛型实现高度复用没有把 “纯 key 场景” 和 “key-value 场景” 写死在代码内部。第二个模板参数 Value决定__rb_tree_node内部存储的数据类型set实例化 rb_treeValue Keymap实例化 rb_treeValue pairconst Key, T同一套红黑树底层同时支撑 set、map这是整套封装最巧妙的地方。重要概念区分STL 源码里的value_type≠ 日常口语中 map 的 value。源码中的value_type指节点上完整存储的实体setvalue_type 就是 keymapvalue_type 是完整的 pairconst K,T常见疑问既然 Value 控制节点存储类型为什么还需要第一个模板参数 Key很多人学到这里都会产生疑惑set 场景下 Key 和 Value 完全相同为什么要额外多出 Key 参数核心原因find()、erase()这类接口接收的参数类型是Key。set插入元素类型 查找元素类型都是 Keymap插入的是完整pairconst K,T但查找、删除只需要传入 Key。如果不单独抽离 Key 作为模板参数底层红黑树无法统一处理两种场景的查找入参。附我们基于手写红黑树封装 set 与 map 时可以先实现最简版本暂时只支持基础 key/value 模型、暂不开放自定义排序仿函数。只要理解这套分层思想后续拓展自定义比较器、multiset/multimap 只是增量开发。模拟实现map和set1.实现出可复用红黑树的框架并支持insert和find我们先实现基础版本红黑树节点内部直接存储pairK,V。该版本红黑树强绑定键值对结构只能给 map 使用无法适配只存储单个 key 的 set。后续借助模板 仿函数抽取 key的思路进行改造让同一套红黑树底层同时支撑 set 和 map。一初始版本耦合 pair 的红黑树仅支持 mapRBTree.h#pragma once #include iostream #includeutility//pair头文件 enum Color { Red, Black }; templateclass K, class V struct RBTreeNode { using Node RBTreeNodeK, V; RBTreeNode() default; RBTreeNode(const std::pairK, V kv) :_kv(kv) , _col(Red) { } std::pairK, V _kv; Node* _left nullptr; Node* _right nullptr; Node* _parent nullptr; Color _col; }; templateclass K, class V class RBTree { using Node RBTreeNodeK, V; public: bool insert(const std::pairK, V kv); void RotateLL(Node* parent); void RotateRR(Node* parent); Node* find(const K key); bool isRBTree(); void InOrder(); private: bool _isRBTree(Node* root, int tmp, int Blen); void _InOrder(Node* cur); Node* _root nullptr; }; templateclass K, class V bool RBTreeK, V::insert(const std::pairK, V kv) { if (_root nullptr) { _root new Node(kv); _root-_col Black; return true; } Node* cur _root; Node* parent nullptr; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else return false; } cur new Node(kv); if (parent-_kv.first kv.first) parent-_left cur; else parent-_right cur; cur-_parent parent; while (cur-_col Red parent-_col Red) { Node* u; Node* grand parent-_parent; if (grand-_left parent) { u grand-_right; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_left cur) { RotateLL(grand); grand-_col Red; parent-_col Black; } else { RotateRR(parent); RotateLL(grand); cur-_col Black; grand-_col Red; } break; } } else { u grand-_left; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_right cur) { RotateRR(grand); grand-_col Red; parent-_col Black; } else { RotateLL(parent); RotateRR(grand); cur-_col Black; grand-_col Red; } break; } } if (_root cur) break; } _root-_col Black; return true; } templateclass K, class V void RBTreeK, V::RotateLL(Node* parent) { Node* grand parent-_parent; Node* subL parent-_left; Node* subLR subL-_right; if (grand nullptr) _root subL; else { if (grand-_left parent) grand-_left subL; else grand-_right subL; } subL-_parent grand; subL-_right parent; parent-_parent subL; parent-_left subLR; if (subLR) subLR-_parent parent; } templateclass K, class V void RBTreeK, V::RotateRR(Node* parent) { Node* grand parent-_parent; Node* subR parent-_right; Node* subRL subR-_left; if (grand nullptr) _root subR; else { if (grand-_left parent) grand-_left subR; else grand-_right subR; } subR-_parent grand; subR-_left parent; parent-_parent subR; parent-_right subRL; if (subRL) subRL-_parent parent; } templateclass K, class V typename RBTreeK, V::Node* RBTreeK, V::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; } templateclass K, class V bool RBTreeK, V::isRBTree() { if (_root nullptr) return true; if (_root-_col Red) return false; int Blen 0; Node* cur _root; while (cur) { if (cur-_col Black) Blen; cur cur-_left; } return _isRBTree(_root, 0, Blen); } templateclass K, class V bool RBTreeK, V::_isRBTree(Node* root, int tmp, int Blen) { if (root nullptr) { if (tmp ! Blen) { std::cout 黑高异常 std::endl; return false; } return true; } if (root-_col Red root-_parent-_col Red) { std::cout 双红节点 std::endl; return false; } if (root-_col Black) tmp; return _isRBTree(root-_left, tmp, Blen) _isRBTree(root-_right, tmp, Blen); } templateclass K, class V void RBTreeK, V::InOrder() { _InOrder(_root); } templateclass K, class V void RBTreeK, V::_InOrder(Node* cur) { if (cur nullptr) return; _InOrder(cur-_left); std::cout cur-_kv.first cur-_kv.second std::endl; _InOrder(cur-_right); }二搭建初始 set、map 外层框架map.h#pragma once #include RBTree.h namespace qiu { templateclass K,class V class map { public: bool insert(const std::pairK, V kv) { _t.insert(kv);; } private: RBTreeK, std::pairconst K, V _t; }; }set.h#pragma once #include RBTree.h namespace qiu { templateclass K class set { public: bool insert(const K kv) { _t.insert(kv); } private: RBTreeK, K _t; }; }观察上面的代码可以发现问题set 存储单个 Kmap 存储pairK,V两者需要复用同一套红黑树底层。原有红黑树模板参数是K,V结构固定无法兼容两种存储类型。 因此我们对红黑树模板参数进行重构将存储的数据类型统一命名为KV保留 K 类型用于 find 查找接口。三修改红黑树节点与类模板RBTree.htemplateclass KV struct RBTreeNode { using Node RBTreeNodeKV; RBTreeNode() default; RBTreeNode(const KV kv) :_kv(kv) , _col(Red) { } KV _kv; Node* _left nullptr; Node* _right nullptr; Node* _parent nullptr; Color _col; }; templateclass K, class KV class RBTree { using Node RBTreeNodeKV; public: bool insert(const KV kv); void RotateLL(Node* parent); void RotateRR(Node* parent); Node* find(const K key); bool isRBTree(); void InOrder(); private: bool _isRBTree(Node* root, int tmp, int Blen); void _InOrder(Node* cur); Node* _root nullptr; };现在产生新问题红黑树底层不知道 KV 到底是 set 的 K还是 map 的pairK,V。 我们insert和find函数内如果直接使用类型默认比较规则pair 会同时对比 key 和 value而我们容器的要求是只根据 key 比较大小、判断重复。解决方案在 set 和 map 内部各自定义一个仿函数专门负责从存储对象 KV 中提取 key再将这个仿函数传入红黑树。红黑树内部统一依靠仿函数获取 key 进行比较不再硬编码kv.first。四修改 set 与 map新增 key 提取仿函数map.h#pragma once #include RBTree.h namespace qiu { templateclass K, class V class map { class MapKeyOfT { public: const K operator()(const std::pairconst K, V kv) { return kv.first; } }; public: bool insert(const std::pairK, V kv) { return _t.insert(kv); } private: RBTreeK, std::pairK, V, MapKeyOfT _t; }; }set.h#pragma once #include RBTree.h namespace qiu { templateclass K class set { class SetKeyOfT { public: const K operator()(const K k) { return k; } }; public: bool insert(const K kv) { return _t.insert(kv); } private: RBTreeK, K, SetKeyOfT _t; }; }五扩展红黑树模板参数接收 KeyOfT 仿函数给 RBTree 增加模板参数KeyOfT接收上层传入的 key 提取仿函数把代码里所有硬编码_kv.first全部替换为仿函数调用。重点改造 insert 和 fiind 函数其余接口同步适配模板参数。RBTree.htemplateclass K, class KV,class KeyOfT bool RBTreeK, KV, KeyOfT::insert(const KV kv) { if (_root nullptr) { _root new Node(kv); _root-_col Black; return true; } Node* cur _root; Node* parent nullptr; KeyOfT key; while (cur) { if (key(cur-_kv) key(kv)) { parent cur; cur cur-_left; } else if (key(cur-_kv) key(kv)) { parent cur; cur cur-_right; } else return false; } cur new Node(kv); if (key(parent-_kv) key(kv)) parent-_left cur; else parent-_right cur; cur-_parent parent; while (cur-_col Red parent-_col Red) { Node* u; Node* grand parent-_parent; if (grand-_left parent) { u grand-_right; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_left cur) { RotateLL(grand); grand-_col Red; parent-_col Black; } else { RotateRR(parent); RotateLL(grand); cur-_col Black; grand-_col Red; } break; } } else { u grand-_left; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_right cur) { RotateRR(grand); grand-_col Red; parent-_col Black; } else { RotateLL(parent); RotateRR(grand); cur-_col Black; grand-_col Red; } break; } } if (_root cur) break; } _root-_col Black; return true; } templateclass K, class V, class KeyOfT typename RBTreeK, V, KeyOfT::Node* RBTreeK, V, KeyOfT::find(const K key) { Node* cur _root; KeyOfT Key; while (cur) { if (Key(cur-_kv) key) cur cur-_right; else if (Key(cur-_kv) key) cur cur-_left; else return cur; } return nullptr; }至此支持 insert 和 find 的泛型红黑树改造完成实现了一套底层同时供给 set 与 map 使用。2.支持iterator实现为了避免代码冗余、保证阅读流畅我会先完整讲解迭代器实现思路最后统一展示最终代码2.1.iterator核心源代码struct __rb_tree_base_iterator { typedef __rb_tree_node_base::base_ptr base_ptr; base_ptr node; 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; } } }; template class Value, class Ref, class Ptr struct __rb_tree_iterator : public __rb_tree_base_iterator { typedef Value value_type; typedef Ref reference; typedef Ptr pointer; typedef __rb_tree_iteratorValue, Value, Value* iterator; __rb_tree_iterator() {} __rb_tree_iterator(link_type x) { node x; } __rb_tree_iterator(const iterator it) { node it.node; } reference operator*() const { return link_type(node)-value_field; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self operator() { increment(); return *this; } self operator--() { decrement(); return *this; } inline bool operator(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node y.node; } inline bool operator!(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node ! y.node; }观察 STL 源码可以发现红黑树迭代器的整体架构和 list 迭代器非常相似都是通过封装节点指针、重载运算符让迭代器具备类似指针的访问行为。二者最大的区别在于红黑树迭代器的、--遍历逻辑更加复杂。2.2.iterator实现思路分析map 与 set 的迭代器遍历遵循二叉树中序遍历规则左子树 → 根节点 → 右子树因此begin()返回的是整棵树中序遍历的第一个节点。迭代器自增的核心思想不依赖全局树结构只依靠当前节点的局部关系以此找到中序遍历的下一个节点如果当前节点的右子树不为空说明当前节点及其左子树已经遍历完毕下一个节点是右子树的最左节点也就是右子树中序遍历的首个节点。如果当前节点的右子树为空说明当前节点所在子树已经完全遍历完成需要向上回溯祖先节点寻找下一个遍历节点。若当前节点是父节点的左孩子按照中序规则下一个遍历节点就是其父节点。若当前节点是父节点的右孩子说明父节点所在子树也已经遍历完成需要持续向上回溯直到找到当前节点是父节点左孩子的祖先节点该节点即为下一个遍历节点。对于end()的实现当遍历到树的最右节点后继续执行迭代器自增会一直向上回溯直至父节点为空此时将迭代器节点置为nullptr以此作为end()位置。需要说明的是原生 SGI-STL 并没有使用nullptr作为尾后迭代器而是额外维护一个哨兵头节点作为end()该哨兵节点与根节点互置父子关系分别指向整棵树的最左、最右节点。为了兼容我们此前手写的红黑树整体架构、避免大规模代码重构本实现选择用nullptr充当end()。功能上与原生 STL 完全等价仅在--end()反向遍历时需要特殊处理当迭代器为空时直接跳转至整棵树的最右节点保证反向遍历正常执行。迭代器自减的逻辑与自增完全对称遍历顺序反向为右子树 → 根节点 → 左子树整体回溯思路同理反向推导即可。最后补充 set 与 map 的迭代器常量属性设计set 容器不允许修改元素因此底层红黑树存储类型为const K从根源禁止迭代器修改数据。map 容器允许修改 value、禁止修改 key因此底层存储pairconst K, V保证键值不可变、映射值可修改。另外需要注意迭代器绝对不能通过数值比较的方式更新节点。如果依靠大小比较寻找下一个节点在multiset、multimap等支持重复 key 的容器中会出现遍历错乱。因此迭代器遍历必须完全依靠节点父子关系回溯保证适配所有场景。​附上述是 SGI-STL 原生迭代器实现逻辑。原生依靠哨兵头节点实现统一遍历无需特殊判断空节点但该方案需要对整棵红黑树结构大改为了保证学习代码连贯性本文不采用哨兵方案。3.map支持[]map 想要实现[]运算符核心前提是修改红黑树的 Insert 接口将返回值调整为pairIterator, bool Insert(const KV kv)在红黑树 Insert 具备该返回形式后[]的实现逻辑会变得十分简洁具体实现参考下方代码。4.qiu::map和qiu::set实现RBTree.h#pragma once #include iostream #includeutility//pair头文件 enum Color { Red, Black }; templateclass KV struct RBTreeNode { using Node RBTreeNodeKV; RBTreeNode() default; RBTreeNode(const KV kv) :_kv(kv) , _col(Red) { } KV _kv; Node* _left nullptr; Node* _right nullptr; Node* _parent nullptr; Color _col; }; templateclass KV,class Ptr,class Ref struct RBTreeIterator { using Self RBTreeIteratorKV, Ptr, Ref; using Node RBTreeNodeKV; RBTreeIterator(Node* node, Node* root) :_node(node) , _root(root) {} Ref operator*() { return _node-_kv; } Ptr operator-() { return _node-_kv; } bool operator(const Self s) const { return _node s._node; } bool operator!(const Self s) const { return _node ! s._node; } Self operator() { if (_node-_right) { _node _node-_right; while (_node-_left) _node _node-_left; } else { Node* parent _node-_parent; while (parent _node parent-_right) { _node parent; parent _node-_parent; } _node parent; } return *this; } Self operator(int) { Self tmp *this; (*this); return tmp; } Self operator--() { if (_root nullptr) return *this; if (_node nullptr) { _node _root; while (_node-_right) _node _node-_right; return *this; } if (_node-_left) { _node _node-_left; while (_node-_right) _node _node-_right; } else { Node* parent _node-_parent; while (parent _node parent-_left) { _node parent; parent _node-_parent; } _node parent; } return *this; } Self operator--(int) { Self tmp *this; --(*this); return tmp; } Node* _root; Node* _node; }; templateclass K, class KV, class KeyOfT class RBTree { using Node RBTreeNodeKV; public: using Iterator RBTreeIteratorKV, KV*, KV; using const_Iterator RBTreeIteratorKV, const KV*, const KV; Iterator begin() { Node* leftmost _root; while (leftmost leftmost-_left) leftmost leftmost-_left; return Iterator(leftmost, _root); } Iterator end() { return Iterator(nullptr, _root); } const_Iterator begin() const { Node* leftmost _root; while (leftmost leftmost-_left) leftmost leftmost-_left; return const_Iterator(leftmost, _root); } const_Iterator end() const { return const_Iterator(nullptr, _root); } RBTree() default; ~RBTree() { Destory(_root); _root nullptr; } std::pairIterator,bool insert(const KV kv); void RotateLL(Node* parent); void RotateRR(Node* parent); Iterator find(const K key); private: void Destory(Node* root) { if (root nullptr) return; Destory(root-_left); Destory(root-_right); delete root; } Node* _root nullptr; }; templateclass K, class KV,class KeyOfT std::pairtypename RBTreeK, KV, KeyOfT::Iterator, bool RBTreeK, KV, KeyOfT::insert(const KV kv) { if (_root nullptr) { _root new Node(kv); _root-_col Black; return std::make_pair(Iterator(_root, _root), false); } Node* cur _root; Node* parent nullptr; KeyOfT key; while (cur) { if (key(cur-_kv) key(kv)) { parent cur; cur cur-_left; } else if (key(cur-_kv) key(kv)) { parent cur; cur cur-_right; } else return std::make_pair(Iterator(cur, _root), false); } cur new Node(kv); if (key(parent-_kv) key(kv)) parent-_left cur; else parent-_right cur; cur-_parent parent; Node* newcur cur; while (cur-_col Red parent-_col Red) { Node* u; Node* grand parent-_parent; if (grand-_left parent) { u grand-_right; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_left cur) { RotateLL(grand); grand-_col Red; parent-_col Black; } else { RotateRR(parent); RotateLL(grand); cur-_col Black; grand-_col Red; } break; } } else { u grand-_left; if (u u-_col Red) { u-_col parent-_col Black; grand-_col Red; cur grand; parent cur-_parent; } else { if (parent-_right cur) { RotateRR(grand); grand-_col Red; parent-_col Black; } else { RotateLL(parent); RotateRR(grand); cur-_col Black; grand-_col Red; } break; } } if (_root cur) break; } _root-_col Black; return std::make_pair(Iterator(newcur, _root), true); } templateclass K, class KV, class KeyOfT void RBTreeK, KV, KeyOfT::RotateLL(Node* parent) { Node* grand parent-_parent; Node* subL parent-_left; Node* subLR subL-_right; if (grand nullptr) _root subL; else { if (grand-_left parent) grand-_left subL; else grand-_right subL; } subL-_parent grand; subL-_right parent; parent-_parent subL; parent-_left subLR; if (subLR) subLR-_parent parent; } templateclass K, class KV, class KeyOfT void RBTreeK, KV, KeyOfT::RotateRR(Node* parent) { Node* grand parent-_parent; Node* subR parent-_right; Node* subRL subR-_left; if (grand nullptr) _root subR; else { if (grand-_left parent) grand-_left subR; else grand-_right subR; } subR-_parent grand; subR-_left parent; parent-_parent subR; parent-_right subRL; if (subRL) subRL-_parent parent; } templateclass K, class KV, class KeyOfT typename RBTreeK,KV,KeyOfT::Iterator RBTreeK,KV,KeyOfT::find(const K key) { Node* cur _root; KeyOfT Key; while (cur) { if (Key(cur-_kv) key) cur cur-_right; else if (Key(cur-_kv) key) cur cur-_left; else return Iterator(cur, _root); } return Iterator(nullptr, _root); }map.h#pragma once #include RBTree.h namespace qiu { templateclass K, class V class map { class MapKeyOfT { public: const K operator()(const std::pairconst K, V kv) { return kv.first; } }; using Node RBTreeK, std::pairconst K, V, MapKeyOfT; using KV std::pairconst K, V; public: using iterator typename RBTreeK, KV, MapKeyOfT::Iterator; using const_iterator typename RBTreeK, KV, MapKeyOfT::const_Iterator; std::pairiterator, bool insert(const std::pairK, V kv) { return _t.insert(kv); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } V operator[](const K key) { std::pairiterator, bool ret insert(std::make_pair(key, V())); return ret.first-second; } iterator find(const K k) { return _t.find(k); } private: Node _t; }; }set.h#pragma once #include RBTree.h namespace qiu { templateclass K class set { class SetKeyOfT { public: const K operator()(const K k) { return k; } }; using Node RBTreeK,const K, SetKeyOfT; public: using iterator typename RBTreeK, const K, SetKeyOfT::Iterator; using const_iterator typename RBTreeK, const K, SetKeyOfT::const_Iterator; std::pairiterator, bool insert(const K kv) { return _t.insert(kv); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } iterator find(const K k) { return _t.find(k); } private: Node _t; }; }test.h#define _CRT_SECURE_NO_WARNINGS #include iostream #include string #include map.h #include set.h using namespace std; int main() { qiu::mapstring, string dict; dict.insert({ sort, 排序 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); dict[left] 左边剩余; dict[insert] 插入; dict[string]; qiu::mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { // 不能修改first可以修改second //it-first x; it-second x; cout it-first : it-second endl; it; } cout endl; qiu::setint s; int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { s.insert(e); } for (auto e : s) { cout e ; } cout endl; return 0; }结语那么Cset和map底层实现部分的内容就全部讲解完毕啦希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。