de风——【从零开始学C++】（二十）红黑树封装map和set

【从零开始学习C++】第 20 篇 系列定位：写给新手小白的 C++ 进阶之路。前面我们已经手撕完了 map / set 的底层数据结构——红黑树，这一篇我们就把它包一层皮，真正做出属于我们自己的 mymap 和 myset。

📌 全文思维导图

建议先把上面这张图保存下来，读到哪一步忘了就回头看哪一支。

一、先回答一个灵魂问题：为什么 map 和 set 能共用一棵树？

1.1 简介作用

set 是 key 搜索场景，存进去的就是一个 key，只关心"在不在"。

map 是 key/value 搜索场景，存进去的是一个 pair<const K, V>，关心"key 对应的 value 是多少"。

按理说这是两个完全不同的东西，但你看 STL 源码会发现一个惊人的事实：它们底层用的是同一棵红黑树。

那它是怎么做到"一棵树干两份活"的？答案就俩字：泛型。

1.2 例子一：从 STL 源码看它怎么复用的

（1）源码里 set 和 map 各自的定义

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key value_type; // set 的 value 就是 key 本身
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 一棵红黑树
};

// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type; // map 的 value 是 pair
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 还是一棵红黑树
};

💡 一句话看懂：set 和 map 里面都只有一个成员 —— 一棵红黑树 t。它们自己几乎不干活，全是"转发"给这棵树。

（2）关键差异只在第二个模板参数

第二个模板参数决定了结点里到底存什么，所以同一份红黑树代码，喂 K 进去就变成 set，喂 pair<const K, V> 进去就变成 map。

（3）那个"多余的"第一个模板参数 K 是干嘛的？

很多同学到这儿都懵：既然第二个参数已经决定存什么了，set 里俩参数还写成一样的，那第一个参数是不是废话？

不是废话。因为 find / erase 的形参类型是 key，不是结点里存的那个整体：

// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
public:
// insert 用第二个模板参数 Value 做形参
pair<iterator, bool> insert_unique(const value_type& x);

// 而 erase / find 用的是第一个模板参数 Key
size_type erase(const key_type& x);
iterator find(const key_type& x);
};

对 set 来说 key 和 value 是同一个东西，看起来"重复"；但对 map 来说就完全不一样了：插入时给的是 pair，查找时给的是 key。所以第一个参数必须留着。

（4）顺手吐槽一下

源码里命名风格其实很乱：set 用 Key，map 用 Key 和 T，到了 rb_tree 又变成 Key 和 Value。而且源码里的 value_type 指的是结点里真实存储的类型，跟我们平时说的"key/value 里的 value"完全不是一回事。大佬写代码也不一定规整，所以看源码时一定要以实际定义为准，别被名字骗了。

二、KeyOfT 仿函数：整个封装最核心的一步

2.1 简介作用

我们自己的红黑树是泛型的，模板参数 T 到底是 K 还是 pair<K, V>，红黑树自己不知道。

那么问题来了：插入的时候要比较大小，如果 T 是 pair<K, V>，pair 默认的 < 是把 first 和 second 一起比的：

template <class T1, class T2>
bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs)
{
return lhs.first < rhs.first ||
(!(rhs.first < lhs.first) && lhs.second < rhs.second);
}

而我们希望的是：任何时候都只比较 key。

解决办法就是大名鼎鼎的 KeyOfT 仿函数：让 map 和 set 各自提供一个"从 T 里抠出 key"的小工具，传给红黑树用。

2.2 例子二：给 set 和 map 各写一个 KeyOfT

（1）SetKeyOfT：要的就是它自己

struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key; // set 里 K 就是 key，直接返回
}
};

（2）MapKeyOfT：把 pair 的 first 抠出来

struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first; // map 里取 pair 的第一个
}
};

（3）红黑树拿到它之后怎么用

template<class K, class T, class KeyOfT> // T 是结点存的数据类型
class RBTree
{
public:
bool Insert(const T& data)
{
// …
KeyOfT kot; // 造一个仿函数对象
Node* parent = nullptr;
Node* cur = _root;

while (cur)
{
if (kot(cur->_data) < kot(data)) // 只比 key
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data)) // 只比 key
{
parent = cur;
cur = cur->_left;
}
else
{
return false; // key 相同，不允许重复插入
}
}
// …
}
};

看到没？红黑树里所有比较都变成了 kot(…) < kot(…)，它彻底不关心 T 到底是什么了。这就是解耦。

2.3 经典 Bug：直接比较 pair 会怎样？

如果你偷懒不写 KeyOfT，插入时直接 cur->_data < data，会发生两件事：

struct Date { int y, m, d; }; // 没有重载 <
map<string, Date> m;
m.insert({ "生日", {2025, 9, 14} });
// 编译报错：no match for 'operator<' (operand types are 'Date' and 'Date')

🐛 避坑结论：KeyOfT 不是一个可选项，它是 map 能用的前提。

三、搭框架：让 mymap / myset 第一次跑起来

3.1 简介作用

有了 KeyOfT，我们就可以把 set 和 map 的"外壳"搭起来了。这一步目标很简单：能插入、能按 key 查。

先规定好我们自己的命名（比源码干净一点）：

• 红黑树模板参数：K（key 类型）、T（结点真实存储类型）、KeyOfT（取 key 的仿函数）；

• 结点类：RBTreeNode<T>；容器在 bit 命名空间里。

3.2 例子三：Myset.h 的第一版

// Myset.h
#pragma once
#include "RBTree.h"

namespace bit
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

public:
bool insert(const K& key)
{
return _t.Insert(key);
}

private:
RBTree<K, K, SetKeyOfT> _t; // 第二个参数给 K
};
}

3.3 例子四：Mymap.h 的第一版

// Mymap.h
#pragma once
#include "RBTree.h"

namespace bit
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};

public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}

private:
RBTree<K, pair<K, V>, MapKeyOfT> _t; // 第二个参数给 pair
};
}

3.4 例子五：配套的红黑树结点

// RBTree.h
enum Colour
{
RED,
BLACK
};

template<class T>
struct RBTreeNode
{
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)
, _col(RED) // 新结点默认给红色，插入逻辑才好处理
{}
};

3.5 整件事的实现步骤清单

① 实现红黑树（前面已经搞定）
② 封装 map / set 框架，解决 KeyOfT
③ 给红黑树加 iterator
④ 加上 const_iterator
⑤ 解决 key 不支持修改的问题
⑥ 给 map 加 operator[]

四、迭代器 iterator：让容器能被 for 循环

4.1 简介作用

要能用范围 for，容器就得提供 begin() 和 end()。红黑树迭代器的思路和 list 完全一致：用一个类把结点指针包起来，再重载运算符，让它用起来像指针。

难点只有一个：++ 和 –。因为 map / set 的遍历顺序是中序（左子树 → 根 → 右子树），所以：

• begin() 返回的是整棵树的最左结点（中序第一个）；

• end() 我们用一个特殊值表示"走完了"。

4.2 例子六：迭代器类的骨架（Ref / Ptr 分离）

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;

Node* _node;
Node* _root; // 额外存一份根，为了支持 –end()

RBTreeIterator(Node* node, Node* root)
: _node(node)
, _root(root)
{}

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; }
};

💡 为什么要 Ref / Ptr 两个额外参数？ iterator 传 T& 和 T*，const_iterator 传 const T& 和 const T*——同一份代码，自动生成两个版本。这就是泛型的甜头。

4.3 例子七：operator++ 的两种走法（本文最烧脑的一段）

核心心法只有一句：不看全局，只看局部——只关心"当前中序的下一个结点是谁"。

情况一：右子树不为空

说明当前结点已经访问完了，下一个是右子树的中序第一个，也就是右子树的最左结点。

情况二：右子树为空

说明当前结点和它所在的子树都访问完了，得往上找祖先：

• 如果当前结点是父亲的左（比如 25 是 30 的左），那下一个就是父亲（30）；

• 如果当前结点是父亲的右（比如 15 是 10 的右），说明连父亲那棵子树也结束了，继续往上爬，直到找到"孩子是父亲左"的那个祖先（15 → 10 → 18，18 就是 10 的父亲且 10 是左孩子，所以下一个是 18）；

• 如果一直爬到根都没找到，说明整棵树走完了，把结点指针置为 nullptr，我们用 nullptr 充当 end()。

// ++it —— 中序的下一个结点
Self& operator++()
{
if (_node->_right)
{
// 情况一：右子树不为空 -> 右子树的最左结点
Node* leftMost = _node->_right;
while (leftMost->_left)
{
leftMost = leftMost->_left;
}
_node = leftMost;
}
else
{
// 情况二：右子树为空 -> 往上找"孩子是父亲左"的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

💡 顺带一提：STL 源码里并没有用 nullptr 做 end()，而是在红黑树顶上挂了一个哨兵位头结点（它和根互为父亲，左指向最左、右指向最右）。不过实力告诉我们：它能的我们也能，用 nullptr 只是 –end() 要特殊处理一下而已。

4.4 例子八：operator– 与 –end() 的特殊处理

— 的逻辑和 ++ 完全对称，反过来想就行（顺序变成 右子树 → 根 → 左子树）：

// –it —— 中序的上一个结点
Self& operator–()
{
if (_node == nullptr) // 处理 –end()
{
// end() 是空，–end() 应该走到整棵树的最右结点
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_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;
}

4.5 例子九：红黑树里的 Begin() / End()

typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

Iterator Begin()
{
Node* leftMost = _root;
while (leftMost && leftMost->_left) // 一路向左，就是中序第一个
{
leftMost = leftMost->_left;
}
return Iterator(leftMost, _root); // 记得把 _root 传进去
}

Iterator End()
{
return Iterator(nullptr, _root); // 用 nullptr 表示 end
}

const 版本同理，只是换成 ConstIterator。

4.6 经典 Bug：迭代器里的坑

Bug 1：–end() 直接崩溃

end() 里结点的指针是 nullptr，如果你在 operator– 里不加 _node == nullptr 的判断，第一件事就是解引用空指针 —— 程序当场去世。

Bug 2：忘记把 _root 传给迭代器

–end() 需要靠 _root 去找最右结点。如果你的迭代器构造函数只传了结点指针，_root 就是野指针，运行起来时好时坏（典型的"玄学 Bug"）。记住 Iterator(node, _root) 两个参数都要传。

Bug 3：Begin() 不判空树

空树时 _root 就是 nullptr，上面的 while (leftMost && leftMost->_left) 里的判空不能少，否则空树 begin() 直接崩。

五、不让改 key：const K 的妙用

5.1 简介作用

红黑树是排序结构，它靠 key 的大小关系维持平衡。如果允许用户随手改 key，整棵树的有序性瞬间就乱了 —— 之后再查找就会找不到本来存在的元素。

所以在设计上必须从类型层面直接锁死：

• set 的 key 就是 value，全都不许改；

• map 的 key 是 pair 的 first，只锁死 first，second 随便改。

5.2 例子十：改一行模板参数就搞定了

// Myset.h —— 第二个参数加 const
RBTree<K, const K, SetKeyOfT> _t;

// Mymap.h —— 把 first 变成 const
RBTree<K, pair<const K, V>, MapKeyOfT> _t;

就这么简单！ 加上 const 之后：

• iterator 的 Ref 变成 const T&，通过 *it / it-> 拿到的东西天然带 const；

• 想改 key？编译器第一个不答应。

5.3 例子十一：同时提供 iterator 和 const_iterator

// Myset.h
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::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& key)
{
return _t.Insert(key);
}

iterator find(const K& key)
{
return _t.Find(key);
}

5.4 例子十二：倒着打印一个 set

void Print(const set<int>& s)
{
set<int>::const_iterator it = s.end();
while (it != s.begin())
{
–it; // 从 end 往前退，正好是降序
// *it += 2; // ❌ 编译报错：read-only，说明 const 生效了
cout << *it << " ";
}
cout << endl;
}

void test_set()
{
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) // 范围 for 走中序，天然升序
{
cout << e << " ";
}
cout << endl;

Print(s); // 降序输出
}

运行结果：

1 2 3 4 5 6 7 14 15 16
16 15 14 7 6 5 4 3 2 1

5.5 经典 Bug：it->first += 'x' 编译不过

map<string, string>::iterator it = dict.begin();
// it->first += 'x'; // ❌ 报错：assignment of read-only member
it->second += 'x'; // ✅ 没问题，value 可以随便改

🐛 提示：如果你发现 it->first 居然能改，说明你在 Mymap.h 里第二参数写的是 pair<K, V>，漏了 const，赶紧补上。

六、map 的 operator[]：一行代码干两件事

6.1 简介作用

map 最爽的功能就是 operator[]，它是"有则返回，无则插入"：

dict["left"] = "左边，剩余"; // left 已存在 -> 改它的 value
dict["insert"] = "插入"; // insert 不存在 -> 插入后再赋值
dict["string"]; // 不存在 -> 插入默认值 ""

要支持它，前提是 Insert 得把"插入结果"告诉外面：既想知道有没有插入成功，又想拿到那个结点的迭代器。所以返回值要从 bool 升级成 pair<iterator, bool>。

6.2 例子十三：把 Insert 的返回值升级

pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(Iterator(_root, _root), true); // 新根，插成功
}

KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
// key 已存在：把"已有结点"的迭代器返回去，bool 给 false
return make_pair(Iterator(cur, _root), false);
}
}

cur = new Node(data); // 到这儿 cur 才真正被接上
Node* newnode = cur;
cur->_col = RED;

if (kot(parent->_data) < kot(data))
parent->_right = cur;
else
parent->_left = cur;

cur->_parent = parent;

// ……中间是红黑树的旋转 + 变色调整（前面文章已详解，这里略）

_root->_col = BLACK; // 根永远是黑的
return make_pair(Iterator(newnode, _root), true);
}

💡 注意最后一行用的是 newnode。因为在调整过程中 cur 可能已经被改成了祖先结点，而我们要返回的是新插入的那个结点的迭代器。

6.3 例子十四：operator[] 的实现

有了上面这个返回值，operator[] 只有三行：

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second; // 直接返回 value 的引用
}

拆开看就是：

所以 operator[] 返回的是引用，既能读也能写。

6.4 例子十五：跑一遍 map

void test_map()
{
map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });

dict["left"] = "左边，剩余"; // 修改已有
dict["insert"] = "插入"; // 插入新的
dict["string"]; // 插入默认值 ""

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// it->first += 'x'; // ❌ key 不能改
it->second += 'x'; // ✅ value 可以改
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}

运行结果（key 自动升序，因为中序遍历）：

insert:插入x
left:左边，剩余x
right:右边x
sort:排序x
string:x

6.5 经典 Bug：Insert 只返回 bool

如果你前面的 Insert 写的是：

bool Insert(const T& data); // ❌ 没有迭代器

那 operator[] 就完全没法实现了 —— 你既不知道新结点在哪，也不知道到底插入没有：

V& operator[](const K& key)
{
bool ret = insert(make_pair(key, V()));
// ret.first -> ❌ 编译报错，bool 没有 first
return ???; // 卡死在这里
}

🐛 避坑结论：map 想要 operator[]，Insert 必须返回 pair<iterator, bool>。这也是为什么 STL 的 insert 要返回 pair<iterator, bool> 的真正原因。

七、完整代码汇总

7.1 RBTree.h

#pragma once
#include <iostream>
#include <utility>
using namespace std;

enum Colour
{
RED,
BLACK
};

template<class T>
struct RBTreeNode
{
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)
, _col(RED)
{}
};

// 迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
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; }

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* leftMost = _node->_right;
while (leftMost->_left)
{
leftMost = leftMost->_left;
}
_node = leftMost;
}
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()
{
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_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;
}
};

template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;

public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

RBTree() = default;

~RBTree()
{
Destroy(_root);
_root = nullptr;
}

Iterator Begin()
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Iterator(leftMost, _root);
}

Iterator End()
{
return Iterator(nullptr, _root);
}

ConstIterator Begin() const
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return ConstIterator(leftMost, _root);
}

ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}

pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(Iterator(_root, _root), true);
}

KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(Iterator(cur, _root), false);
}
}

cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;

if (kot(parent->_data) < kot(data))
parent->_right = cur;
else
parent->_left = cur;

cur->_parent = parent;

// 平衡调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
// 叔叔存在且为红 -> 变色继续往上处理
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// 单旋：g 左，p 左，c 左
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 双旋：左右
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// 单旋：右右
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 双旋：右左
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}

_root->_col = BLACK;
return make_pair(Iterator(newnode, _root), true);
}

Iterator Find(const K& key)
{
KeyOfT kot; // 用 KeyOfT 取 key，不要直接写 _kv.first！
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return Iterator(cur, _root);
}
}
return End();
}

private:
void RotateL(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;
}
}

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;

if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subL;
else
parentParent->_right = subL;

subL->_parent = parentParent;
}
}

void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}

private:
Node* _root = nullptr;
};

7.2 Myset.h

#pragma once
#include "RBTree.h"

namespace bit
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::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& key)
{
return _t.Insert(key);
}

iterator find(const K& key)
{
return _t.Find(key);
}

private:
RBTree<K, const K, SetKeyOfT> _t; // 第二个参数加 const，key 不可改
};
}

7.3 Mymap.h

#pragma once
#include "RBTree.h"

namespace bit
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};

public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::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);
}

iterator find(const K& key)
{
return _t.Find(key);
}

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

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t; // 只锁死 first
};
}

7.4 test.cpp

#include "RBTree.h"
#include "Myset.h"
#include "Mymap.h"

void test_set()
{
bit::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;
}

void test_map()
{
bit::map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });

dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];

bit::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}

int main()
{
test_set();
test_map();
return 0;
}

八、本篇小结

把整件事捋一遍，其实就只有 6 步：

最容易踩的三个坑，再强调一次：

到这里，map 和 set 的底层对我们来说就不再是黑盒了 —— 它们不过是一棵红黑树 + 一层薄薄的封装而已。

前面我们手撕了红黑树的旋转与变色，这一篇把"外壳"补齐。下一篇我们继续往前推进，别忘了把思维导图存下来随时复习～

如果这篇帮你理清了思路，欢迎点赞 + 收藏 + 关注，你的支持是我持续更新的最大动力！ 🔥