有段时间我一直在琢磨一个事：C++ 的标准库容器我用得很熟，可一旦被人问到“std::map 底层到底是怎么组织的”，我只能含糊地回一句“红黑树”。含糊就意味着没真正掌握。后来我决定不再背结论，而是动手用 C++ 模拟实现一套自己的 map 和 set。做完之后最大的感受是：容器封装只是薄薄一层，难点几乎全在底层树的结构维护和迭代器设计上。这篇文章就把整个实现过程中的选型、设计、踩坑和验证思路记录下来，适合已经学过二叉搜索树、想真正弄懂关联容器内部机制、或者面试前想彻底搞清红黑树的人。
先交代一下项目范围：不追求完整复刻标准库，而是实现一个功能闭环——支持构造、insert、find、erase、begin/end 迭代遍历，map 额外支持 operator[]。set 保证元素不可修改，map 允许修改 value 不允许修改 key。底层共用同一棵红黑树模板。这套东西做完，你对 map/set 的认知会从“会调用”变成“敢解释”。
1. 从“会用容器”到“动手造容器”：手写 map/set 到底在写什么
1.1 项目目标与最终交付物
这个项目本质上不是“写两个类”，而是“写一棵树，再做两件衣服”。我给自己定的目标非常明确：
- 实现一棵可复用的红黑树模板，内部完成插入、查找、删除、平衡维护；
- 基于这棵树封装出 map 和 set，对外暴露符合直觉的接口；
- 迭代器必须支持 for (auto& x : container) 这种范围遍历，且遍历结果严格有序；
- 插入返回 pair<iterator, bool>，真实表达“是否插入成功”和“指向的位置”两层信息；
- set 的迭代器解引用后是常量，map 的迭代器解引用后可以修改 second，但不能修改 first。
标准库里 map 和 set 的底层不同吗？其实在主流实现里，它们底层都是红黑树，只是节点存储的数据类型、比较时提取 key 的方式不一样。这也是本项目最核心的设计点：底层树必须做到“一套代码，两种容器”，不能在树里面写死 set 还是 map。
1.2 一句话结论：容器只是树的两层外衣
如果你直接按“set 是红黑树”和“map 是红黑树”分别写两份实现，那这个项目就失去了意义。真正的做法是抽象出三个模板参数：
- Value：节点里实际存的数据。set 时是 key 本身，map 时是 pair<const Key, Value>；
- KeyOfValue：从 Value 中取 key 的函数对象；
- Compare：比较 key 时使用的比较器。
树的查找、插入、删除流程，只认 KeyOfValue 提取出来的 key，完全不关心 Value 长什么样。这样 map 和 set 就真的成了树的“外观层”，各自只需要做接口适配。理解了这条主线，整体实现就不会乱。迭代器、平衡修复、哨兵节点这些复杂细节，全部集中在树的内部，封装层反而很简单。
2. 树形底层选型与数据组织：为什么是红黑树，怎么设计“一套代码两种容器”
2.1 红黑树与 AVL、哈希表的取舍
动笔之前肯定要回答一个问题：为什么标准库选择红黑树，而不是 AVL 树或者哈希表？我用一个实际需求倒推一下就明白了。
set/map 必须满足三个点：查询 O(log n)、插入删除 O(log n)、遍历有序。哈希表虽然平均查询 O(1)，但无序，直接出局；普通二叉搜索树实现简单，但插入有序数据会退化成链，也出局。剩下就是 AVL 和红黑树二选一。
| 方案 | 查找复杂度 | 插入后平衡维护 | 有序遍历 | 平衡标准 |
|---|---|---|---|---|
| 普通BST | 最坏 O(n) | 无 | 支持 | 无 |
| AVL 树 | O(log n) | 旋转频繁，严格控制高度差 <= 1 | 支持 | 严格 |
| 红黑树 | O(log n) | 旋转相对少，允许高度差放宽到 2 倍 | 支持 | 宽松 |
| 哈希表 | O(1) 平均 | 扩容、冲突处理 | 不支持 | 无 |
红黑树的平衡标准是“任意路径长度不超过最短路的两倍”，比 AVL 的“左右子树高度差最多 1”宽松。代价是树略高一点，查询常数稍大；好处是插入时不做那么多旋转，整体写入性能更平稳。标准库选红黑树，本质是实践里校验过的综合最优解。所以模拟实现时直接跟标准库走，不折腾。
2.2 节点只存“有效载荷”：用模板参数化解 set 和 map 的差异
红黑树的节点结构应该是整棵树的基石。节点里需要的东西只有四样：左右孩子指针、父亲指针、颜色、数据本身。
enum Color { RED, BLACK }; template <class Value> struct RBNode { RBNode* left; RBNode* right; RBNode* parent; Color color; Value data; RBNode(const Value& v) : left(nullptr), right(nullptr), parent(nullptr), color(RED), data(v) {} };注意颜色枚举我放在全局命名域里，因为树的实现和迭代器可能都需要引用颜色。初始化时新节点默认 RED，这一点后面会专门讲为什么。
这套结构很通用：set 实例化时 Value 就是 key 类型，比如 int 或 string；map 实例化时 Value 就是 pair<const Key, V>。由于 pair 的第一个模板参数带了 const，map 的外部用户拿到引用后也无法修改 first，从类型层面直接锁死 key 不可变。这是一个小小的设计红利，封装层省了不少事。
2.3 KeyOfValue：让比较器不用关心完整数据类型
树中最常见的操作是“给定一个 key，找到对应节点”。但节点里的数据是 Value，不是 key。如果树的比较逻辑直接写死成比较 Value，那 map 就没法用了。所以我引入 KeyOfValue 这个函数对象：
template <class Key> struct SetKeyOfValue { const Key& operator()(const Key& k) const { return k; } }; template <class Key, class Value> struct MapKeyOfValue { const Key& operator()(const pair<const Key, Value>& kv) const { return kv.first; } };set 里面取 key 就是取自己；map 里面取 key 就取 pair 的 first。树中的所有比较语句统一写成：
bool less = cmp(keyOfValue(data), key);这样的好处是树完全不去区分 set 还是 map。它只知道“我用 Compare 比较 KeyOfValue 提取出来的 key”。哈希表失误时你可能需要单独写两份逻辑，而红黑树不会出现这种精神分裂。这个抽象是整套实现最值得借鉴的部分，也是后面封装层能保持简短的前提。
3. 插入流程的完整拆解：变色、左旋右旋与三种必经情形
3.1 新节点为什么一定要标红
红黑树的五个性质可以浓缩成三条实用约束：根是黑的；没有连续的红色节点；从任意节点到每个空叶子节点的路径上，黑色节点数量相同。
插入一个新节点时，如果把它标成黑色，最麻烦的事就发生了——这条路径比别的路径多一个黑节点，直接违反“黑高相等”这条全局约束。要让整棵树重新满足性质，得从根到叶子整体调整，代价极大。反过来，如果新节点标红，它最多只可能破坏“不能连续红”这一条局部性质。修复这种局部问题，只需要顺着祖先往上走，变色、旋转几下就能解决。
所以标准做法是：新插入节点一律标红，插入结束后再做修复。
3.2 叔叔为红与叔叔为黑：两条完全不同的修复路线
插入修复的循环条件是“当前节点的父亲是红色”。因为根是黑的，父亲是红节点时祖父必然存在。根据父亲和祖父的位置关系，以及叔叔的颜色，分成三类情况处理。
先明确左右旋的基本逻辑。左旋就是把当前节点的右孩子提上来，原右孩子的左子树挂回当前节点的右侧；右旋是镜像。旋转永远不改变中序遍历的顺序，它只是重新分配局部父子关系。
| 情形 | 判定条件 | 处理动作 |
|---|---|---|
| 情形一 | 叔叔存在且为红 | 父亲、叔叔变黑，祖父变红，当前节点升到祖父继续循环 |
| 情形二 | 叔叔黑或空，且当前节点位于父亲的内侧 | 先对父亲旋转，把“内侧”扭成“外侧”，转入情形三 |
| 情形三 | 叔叔黑或空，且当前节点位于父亲的外侧 | 对祖父旋转，父亲和祖父交换颜色，直接结束 |
所谓内侧，举个例子：祖父的左孩子是父亲，父亲的右孩子是当前节点，那当前节点就是“内侧”的 LR 形态。此时直接对祖父右旋，会得到仍然不平衡的结构。必须先对父亲左旋，让父亲变成当前节点的左孩子，当前节点变成祖父的直接左孩子，就扭转成了外侧 LL 形态，然后再对祖父右旋。
简化后的伪代码逻辑如下：
while (parent && parent->color == RED) { Node* grand = parent->parent; if (parent == grand->left) { Node* uncle = grand->right; if (uncle && uncle->color == RED) { parent->color = BLACK; uncle->color = BLACK; grand->color = RED; cur = grand; parent = cur->parent; } else { if (cur == parent->right) { rotateLeft(parent); cur = parent; // 原来的父亲变成当前节点的孩子 parent = cur->parent; // 新的父亲就是原来的当前节点 } rotateRight(grand); std::swap(parent->color, grand->color); break; } } else { // 镜像逻辑 } } root->color = BLACK;镜像那一大段就是把 left/right 全部对调，逻辑完全对称，不重复贴了。这里强烈建议你按“先左后右”的对称思路在纸上画一遍，而不是死记代码。
3.3 旋转时最容易踩的指针更新坑
旋转本身代码量不大，但指针顺序错了真的非常难查。最典型的问题有两个。
第一个坑：更新父亲指针时，不管当前节点原来是根。根节点没有 parent 指向某个普通节点，它可能指向哨兵或者 nullptr。如果不先判断当前节点是不是根，直接想去改 parent 的 left/right，就会把根节点的父亲（哨兵）的子节点误改掉，树莫名其妙少一片。安全写法是先判断：
if (x == root) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y;第二个坑：旋转里先断后挂的顺序。左旋时，如果先执行 x->right = y->left，而 y 还指着 x->right，中间状态会丢掉 y 的整棵左子树。每次旋转必须先把 y 的左子树挂到 x 的右孩子位置，然后再去动 y 的其他指针。这句话说起来简单，实际调试时丢子树的问题十有八九就出在这里。
4. 迭代器与哨兵：中序遍历如何变成 begin/end/++/--
4.1 迭代器的有序性从哪里来
红黑树本身还是一棵二叉搜索树，中序遍历天然能得到有序序列。set/map 的迭代器顺序，本质上就是红黑树中序遍历的顺序。begin 对应整棵树最左边的节点，也就是中序遍历第一个元素；每执行一次 ++，就走到当前节点的中序后继。
这个设计让“有序性”完全靠树的性质白送，不需要额外维护链表。代价是实现 ++ 和 -- 时需要靠父子关系来回回溯，而不是像链表那样直接跳 next。
4.2 后继查找：右子树为空时，向上回溯的终止条件
迭代器内部的 operator++ 是这套实现里最值得花时间理解的地方。它分两种情况。
第一种，当前节点有右孩子。那后继就是右子树里的最左节点，这个没有悬念。
第二种，当前节点没有右孩子。此时后继必须往祖先方向找。规则是：从当前节点开始，不断向上回溯，直到“当前节点是父节点的左孩子”为止。停下来的那个父节点，就是当前节点的后继；如果一直回溯到根都没有满足条件，说明当前节点是整棵树的最右节点，++ 之后应该到达哨兵 end()。
用代码写就是这样：
Self& operator++() { if (node->right) { Node* p = node->right; while (p->left) p = p->left; node = p; } else { Node* p = node->parent; Node* c = node; while (p && c == p->right) { c = p; p = p->parent; } node = p; } return *this; }这里最难理解的是：为什么回溯到“当前节点是父节点的左孩子”就停？可以这样想，中序遍历的顺序是左根右。一个节点没有右子树时，它的整个子树已经走完了。接下来要去哪一个祖先？答案是：第一个把当前节点当成“左边内容”的祖先，也就是第一个“当前节点在其左子树里”的祖先。这个祖先一定是后继。
operator-- 是它的镜像对称，原则完全一样。你可以在纸上画一棵树，按中序遍历把节点序号标出来，再对着序号检查 ++ 的跳转，一遍就能验证逻辑。
4.3 哨兵节点与 end() 的关系
迭代器不能只有普通节点指针，必须有一个“越界”的表示。我的做法是在树内部维护一个哨兵节点 header，让 end() 直接返回 header 的迭代器。
哨兵节点的组织方式是：
- header->parent 指向根节点；
- 根节点 root->parent 指向 header；
- header->left 始终指向最左节点，header->right 始终指向最右节点。
这样 begin() 返回 header->left 对应的迭代器，end() 返回 header。当 ++ 走到最右节点时，回溯最终会回到 header，因为根不是任何节点的右孩子，回溯到根的那一步会自然落到 header 上，迭代器就停在 end() 了。同时，因为 header->right 指向最右节点，--end() 就能直接跳到整个序列的最后一个元素。
这里有一个必须注意的细节：erase 节点时，如果删掉了当前最左节点或最右节点，必须同步更新 header->left / header->right。这个环节我调试时漏过好几次，症状是删除之后迭代器边界错乱，范围 for 循环跑到野指针。
5. 封装接口的细节：insert 返回值、set 只读迭代器与 operator[]
5.1 去重语义与 pair<iterator, bool>
set 和 map 都是不重复 key 的容器，insert 时如果 key 已经存在，不能创建新节点，也不能覆盖原数据。标准库的语义是：返回 pair<iterator, bool>，bool 代表是否新插入，iterator 指向要么是新节点、要么是已经存在的旧节点。
树的 insert 返回值设计成 pair<Node*, bool>，封装层再转换成 pair<iterator, bool>。判断“是否存在”只需要在查找过程中记录最后经过的节点：
template <class Value, class KeyOfValue, class Compare> pair<typename RBTree<Value, KeyOfValue, Compare>::Node*, bool> RBTree<Value, KeyOfValue, Compare>::insert(const Value& v) { if (!root) { root = new Node(v); root->color = BLACK; header->left = root; header->right = root; return {root, true}; } Node* parent = nullptr; Node* cur = root; bool goLeft = false; while (cur) { parent = cur; if (cmp(keyOfValue(v), keyOfValue(cur->data))) { cur = cur->left; goLeft = true; } else if (cmp(keyOfValue(cur->data), keyOfValue(v))) { cur = cur->right; goLeft = false; } else { return {cur, false}; } } Node* n = new Node(v); if (goLeft) parent->left = n; else parent->right = n; n->parent = parent; // 插入后的变色旋转修复 insertFixUp(n); updateHeader(); return {n, true}; }注意比较不要只判断一次就认为 key 相等。正确做法是用“小于”判断两次：value 小于当前节点，往左走；当前节点小于 value，往右走；两个方向都不满足，说明等于，才判定重复。这样即使比较器只定义 operator< 也能正常工作。
5.2 set 不能改 key，map 可以改 value 的封装差异
树内部的迭代器模板可以带 Ref 和 Ptr 两个模板参数：
template <class Value, class Ref, class Ptr> class RBTreeIterator { Ref operator*() const { return node->data; } Ptr operator->() const { return &node->data; } // ... };普通迭代器用 Value& / Value*，const 迭代器用 const Value& / const Value*。map 对外暴露普通迭代器，这样 *it 得到 pair<const Key, V>&，用户改 second 没问题，改 first 会被编译期拒绝。
set 的做法更巧妙：直接把 const 迭代器当作自己的 iterator。也就是说，set 底层实例化红黑树时，公开的 iterator 类型是 const_iterator。这样用户即使写 *sit = 4，编译器也会报错。这个设计非常关键，如果 set 使用了普通迭代器，用户就能绕过规则修改元素，而 set 的内部排序会被破坏，后续查找结果全是错的。
5.3 operator[] 到底做了什么
map 的 operator[] 是个有点“危险”的接口，因为它同时兼具读和写两重语义。内部实现其实很直接：
V& operator[](const K& key) { return insert({key, V()}).first->second; }也就是无条件先调用 insert，插入一个用 key 和 Value 默认构造组成的 pair。如果 key 原本不存在，insert 创建了新节点，operator[] 返回新节点的 second 引用；如果 key 本来就在，insert 返回已有节点，operator[] 就相当于查找。
这个设计意味着 operator[] 不能用于 const map。const 版本应该走 find，找不到就返回容器的 end()。也是因为这一点，很多风格指南要求“只读场景用 find，写场景才用 operator[]”，避免无意间插入大量默认值。我的习惯是：需要修改 map 的值时用 operator[]，只是想查询时用 find。
6. 验证手段与删除修复的进阶笔记
6.1 自检红黑树性质的三板斧
写完树之后，最怕的一件事就是“表面正常，实际上不满足红黑树性质”。很多 bug 在插入一两百个随机数后才会暴露，纯肉眼根本看不出来。我给自己写了一套检查逻辑，在测试阶段每次插入删除后都跑一遍。
int validate(Node* n) { if (!n) return 1; if (isRed(n) && (isRed(n->left) || isRed(n->right))) { throw std::runtime_error("red-red violation"); } int l = validate(n->left); int r = validate(n->right); if (l != r) { throw std::runtime_error("black-height mismatch"); } return l + (isBlack(n) ? 1 : 0); }这个递归函数同时检查了“没有连续红节点”和“每条路径黑高相同”。再配合中序遍历打印出来验证有序性，三件套齐了。测试时我用随机数生成器插入大量元素，每插入一批就调用 validate，跑个几万次都没崩，才敢说插入逻辑基本可信。
6.2 删除为什么比插入难一个量级
插入只需要处理三种情形，删除却是另一个故事。删除时如果删掉的是一个红色节点，黑高不会变，直接结束；如果删掉的是黑色节点，它所在路径就少了一个黑色节点，必须做“双黑修复”。双黑修复需要看兄弟节点的颜色、兄弟孩子的颜色，拆出五六种带镜像的情形。
删除流程的主干是这样：先找到要删的节点；如果它有两个孩子，就找中序后继节点来替换节点，真正删除的变成后继节点；如果被删节点只有一个孩子，直接用孩子顶替；如果被删节点是黑，且顶替上来的孩子是黑，就进入双黑修复循环。
这段逻辑写起来长，调试更麻烦。我自己的经验是：不要试图一口气把删除写完，先把“找到、替换、顶替”这三个步骤输出日志确认节点关系正确，再单独调修复函数。每实现一个情形就构造一个对应形态的小树去测。想偷懒的话，可以用随机插入随机删除配合 validate 反复跑，这种压力测试往往能暴露你想不到的组合形态。
6.3 后续可以继续加什么功能
一套基础版实现跑通之后，可以按自己的兴趣继续加东西：multimap/multiset 支持重复 key，只需要把等于判定改成继续往右走的策略；lower_bound/upper_bound 接口补充区间查询能力；C++11 的移动构造和移动赋值能显著优化插入大对象时的拷贝开销；甚至可以把 allocator 抽成模板参数，让容器支持自定义内存策略。
不过扩展功能之前，我建议你一定先把插入、查找、删除、迭代器这四块跑得足够稳，尤其是验证函数连续跑十万次随机操作不报错。树的核心稳了，之后加什么都只是工作量问题。
做这个项目给我最大的体会是：写红黑树不能靠背诵那些旋转情形，而是每次修改前先问三句话——刚才这个操作破坏了哪条性质？是哪一层的哪条路径出了问题？到底要改变颜色还是旋转，才能把问题限制在局部？顺着这个思路，哪怕记不住所有代码，现场也能把修复过程推出来。map 和 set 本身从来不复杂，复杂的是它们底下那棵树；而把那棵树真正拆开看一遍以后，你会发现很多看似神奇的容器行为，其实都是几十行指针操作堆出来的朴素结果。
