企业官网建设流程全解析

目录

引言：

源码及框架分析

头文件依赖

stl_set.h 源码核心

stl_map.h 源码核心

stl_tree.h 红黑树底层源码

框架核心思想解读

常见疑问：既然 Value 控制节点存储类型，为什么还需要第一个模板参数 Key？

模拟实现map和set

1.实现出可复用红黑树的框架并支持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.h

map.h

set.h

test.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 = less<Key>, 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_tree<key_type, value_type, identity<value_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 = less<Key>, 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 pair<const Key, T> value_type; private: typedef rb_tree<key_type, value_type, select1st<value_type>, Compare, Alloc> rep_type; rep_type t; // 承载map的红黑树 };

重点：map 的 value_type 并不是 T，而是pair<const 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_node<Value>* 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_node<Value> rb_tree_node; typedef simple_alloc<rb_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: // 插入、删除接口 pair<iterator,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内部存储的数据类型：

1. set实例化 rb_tree：Value = Key
2. map实例化 rb_tree：Value =pair<const Key, T>

同一套红黑树底层，同时支撑 set、map，这是整套封装最巧妙的地方。

重要概念区分：

STL 源码里的value_type≠ 日常口语中 map 的 value。

源码中的value_type指节点上完整存储的实体：

• set：value_type 就是 key
• map：value_type 是完整的 pair<const K,T>

常见疑问：既然 Value 控制节点存储类型，为什么还需要第一个模板参数 Key？

很多人学到这里都会产生疑惑：set 场景下 Key 和 Value 完全相同，为什么要额外多出 Key 参数？

核心原因：find()、erase()这类接口接收的参数类型是Key。

• set：插入元素类型 = 查找元素类型（都是 Key）；
• map：插入的是完整pair<const K,T>，但查找、删除只需要传入 Key。

如果不单独抽离 Key 作为模板参数，底层红黑树无法统一处理两种场景的查找入参。

附：我们基于手写红黑树封装 set 与 map 时，可以先实现最简版本：暂时只支持基础 key/value 模型、暂不开放自定义排序仿函数。只要理解这套分层思想，后续拓展自定义比较器、multiset/multimap 只是增量开发。

模拟实现map和set

1.实现出可复用红黑树的框架并支持insert和find

我们先实现基础版本红黑树，节点内部直接存储pair<K,V>。该版本红黑树强绑定键值对结构，只能给 map 使用，无法适配只存储单个 key 的 set。后续借助模板 + 仿函数抽取 key的思路进行改造，让同一套红黑树底层同时支撑 set 和 map。

一：初始版本：耦合 pair 的红黑树（仅支持 map）

RBTree.h

#pragma once #include <iostream> #include<utility>//pair头文件 enum Color { Red, Black }; template<class K, class V> struct RBTreeNode { using Node = RBTreeNode<K, V>; RBTreeNode() = default; RBTreeNode(const std::pair<K, V>& kv) :_kv(kv) , _col(Red) { } std::pair<K, V> _kv; Node* _left = nullptr; Node* _right = nullptr; Node* _parent = nullptr; Color _col; }; template<class K, class V> class RBTree { using Node = RBTreeNode<K, V>; public: bool insert(const std::pair<K, 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; }; template<class K, class V> bool RBTree<K, V>::insert(const std::pair<K, 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; } template<class K, class V> void RBTree<K, 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; } template<class K, class V> void RBTree<K, 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; } template<class K, class V> typename RBTree<K, V>::Node* RBTree<K, 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; } template<class K, class V> bool RBTree<K, 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); } template<class K, class V> bool RBTree<K, 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); } template<class K, class V> void RBTree<K, V>::InOrder() { _InOrder(_root); } template<class K, class V> void RBTree<K, 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 { template<class K,class V> class map { public: bool insert(const std::pair<K, V>& kv) { _t.insert(kv);; } private: RBTree<K, std::pair<const K, V>> _t; }; }

set.h

#pragma once #include "RBTree.h" namespace qiu { template<class K> class set { public: bool insert(const K& kv) { _t.insert(kv); } private: RBTree<K, K> _t; }; }

观察上面的代码可以发现问题：set 存储单个 K，map 存储pair<K,V>，两者需要复用同一套红黑树底层。原有红黑树模板参数是K,V，结构固定，无法兼容两种存储类型。 因此我们对红黑树模板参数进行重构：将存储的数据类型统一命名为KV；保留 K 类型，用于 find 查找接口。

三：修改红黑树节点与类模板

RBTree.h

template<class KV> struct RBTreeNode { using Node = RBTreeNode<KV>; RBTreeNode() = default; RBTreeNode(const KV& kv) :_kv(kv) , _col(Red) { } KV _kv; Node* _left = nullptr; Node* _right = nullptr; Node* _parent = nullptr; Color _col; }; template<class K, class KV> class RBTree { using Node = RBTreeNode<KV>; 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 的pair<K,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 { template<class K, class V> class map { class MapKeyOfT { public: const K& operator()(const std::pair<const K, V>& kv) { return kv.first; } }; public: bool insert(const std::pair<K, V>& kv) { return _t.insert(kv); } private: RBTree<K, std::pair<K, V>, MapKeyOfT> _t; }; }

set.h

#pragma once #include "RBTree.h" namespace qiu { template<class 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: RBTree<K, K, SetKeyOfT> _t; }; }

五：扩展红黑树模板参数，接收 KeyOfT 仿函数

给 RBTree 增加模板参数KeyOfT接收上层传入的 key 提取仿函数，把代码里所有硬编码_kv.first全部替换为仿函数调用。重点改造 insert 和 fiind 函数，其余接口同步适配模板参数。

RBTree.h

template<class K, class KV,class KeyOfT> bool RBTree<K, 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; } template<class K, class V, class KeyOfT> typename RBTree<K, V, KeyOfT>::Node* RBTree<K, 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_iterator<Value, 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()返回的是整棵树中序遍历的第一个节点。

迭代器自增的核心思想不依赖全局树结构，只依靠当前节点的局部关系，以此找到中序遍历的下一个节点：

1. 如果当前节点的右子树不为空，说明当前节点及其左子树已经遍历完毕，下一个节点是右子树的最左节点，也就是右子树中序遍历的首个节点。
2. 如果当前节点的右子树为空，说明当前节点所在子树已经完全遍历完成，需要向上回溯祖先节点寻找下一个遍历节点。
   • 若当前节点是父节点的左孩子，按照中序规则，下一个遍历节点就是其父节点。
   • 若当前节点是父节点的右孩子，说明父节点所在子树也已经遍历完成，需要持续向上回溯，直到找到当前节点是父节点左孩子的祖先节点，该节点即为下一个遍历节点。

对于end()的实现：当遍历到树的最右节点后，继续执行迭代器自增，会一直向上回溯直至父节点为空，此时将迭代器节点置为nullptr，以此作为end()位置。

需要说明的是，原生 SGI-STL 并没有使用nullptr作为尾后迭代器，而是额外维护一个哨兵头节点作为end()，该哨兵节点与根节点互置父子关系，分别指向整棵树的最左、最右节点。

为了兼容我们此前手写的红黑树整体架构、避免大规模代码重构，本实现选择用nullptr充当end()。功能上与原生 STL 完全等价，仅在--end()反向遍历时需要特殊处理：当迭代器为空时，直接跳转至整棵树的最右节点，保证反向遍历正常执行。

迭代器自减的逻辑与自增完全对称，遍历顺序反向为：右子树 → 根节点 → 左子树，整体回溯思路同理反向推导即可。

最后补充 set 与 map 的迭代器常量属性设计：

• set 容器不允许修改元素，因此底层红黑树存储类型为const K，从根源禁止迭代器修改数据。
• map 容器允许修改 value、禁止修改 key，因此底层存储pair<const K, V>，保证键值不可变、映射值可修改。

另外需要注意：迭代器绝对不能通过数值比较的方式更新节点。如果依靠大小比较寻找下一个节点，在multiset、multimap等支持重复 key 的容器中会出现遍历错乱。因此迭代器遍历必须完全依靠节点父子关系回溯，保证适配所有场景。

​

附：上述是 SGI-STL 原生迭代器实现逻辑。原生依靠哨兵头节点实现统一遍历，无需特殊判断空节点；但该方案需要对整棵红黑树结构大改，为了保证学习代码连贯性，本文不采用哨兵方案。

3.map支持[]

map 想要实现[]运算符，核心前提是修改红黑树的 Insert 接口，将返回值调整为：

pair<Iterator, bool> Insert(const KV& kv)

在红黑树 Insert 具备该返回形式后，[]的实现逻辑会变得十分简洁，具体实现参考下方代码。

4.qiu::map和qiu::set实现

RBTree.h

#pragma once #include <iostream> #include<utility>//pair头文件 enum Color { Red, Black }; template<class KV> struct RBTreeNode { using Node = RBTreeNode<KV>; RBTreeNode() = default; RBTreeNode(const KV& kv) :_kv(kv) , _col(Red) { } KV _kv; Node* _left = nullptr; Node* _right = nullptr; Node* _parent = nullptr; Color _col; }; template<class KV,class Ptr,class Ref> struct RBTreeIterator { using Self = RBTreeIterator<KV, Ptr, Ref>; using Node = RBTreeNode<KV>; 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; }; template<class K, class KV, class KeyOfT> class RBTree { using Node = RBTreeNode<KV>; public: using Iterator = RBTreeIterator<KV, KV*, KV&>; using const_Iterator = RBTreeIterator<KV, 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::pair<Iterator,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; }; template<class K, class KV,class KeyOfT> std::pair<typename RBTree<K, KV, KeyOfT>::Iterator, bool> RBTree<K, 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); } template<class K, class KV, class KeyOfT> void RBTree<K, 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; } template<class K, class KV, class KeyOfT> void RBTree<K, 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; } template<class K, class KV, class KeyOfT> typename RBTree<K,KV,KeyOfT>::Iterator RBTree<K,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 { template<class K, class V> class map { class MapKeyOfT { public: const K& operator()(const std::pair<const K, V>& kv) { return kv.first; } }; using Node = RBTree<K, std::pair<const K, V>, MapKeyOfT>; using KV = std::pair<const K, V>; public: using iterator = typename RBTree<K, KV, MapKeyOfT>::Iterator; using const_iterator = typename RBTree<K, KV, MapKeyOfT>::const_Iterator; std::pair<iterator, bool> insert(const std::pair<K, 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::pair<iterator, 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 { template<class K> class set { class SetKeyOfT { public: const K& operator()(const K& k) { return k; } }; using Node = RBTree<K,const K, SetKeyOfT>; public: using iterator = typename RBTree<K, const K, SetKeyOfT>::Iterator; using const_iterator = typename RBTree<K, const K, SetKeyOfT>::const_Iterator; std::pair<iterator, 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::map<string, string> dict; dict.insert({ "sort", "排序" }); dict.insert({ "left", "左边" }); dict.insert({ "right", "右边" }); dict["left"] = "左边，剩余"; dict["insert"] = "插入"; dict["string"]; qiu::map<string, 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::set<int> 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; }

结语：

那么，C++set和map底层实现部分的内容就全部讲解完毕啦，希望以上内容对你有所帮助，感谢观看，若觉得写的还可以，可以分享给朋友一起来看哦，毕竟一起进步更有动力嘛，当然能关注一下就更好啦。