1. 项目背景与核心价值1.1 为什么讲 set/map 模拟实现这次写 set/map 的模拟实现其实不是心血来潮。很多学 C 的朋友在刷算法题和做业务开发时set/map 都是高频使用的容器但大部分人停留在会用的层面一旦追问底层原理就含糊了。有人觉得不就是一棵红黑树吗插入删除旋转背背模板就完事了。真正自己动手写一遍就会发现红黑树只是最基础的部分set/map 封装层的很多细节才是真正磨人的地方。比如迭代器怎么设计、find 和 insert 返回什么、map 的 operator[] 底层怎么实现这些才是面试里最容易被追问的点。模拟实现的价值有三个层面理解 set/map 的时间复杂度承诺从哪来看透红黑树节点和迭代器内部的结构设计熟练掌握模板泛型编程、仿函数提取键值这类高级玩法这个项目适合两类人一类是学完红黑树但没串起来的人另一类是想搞清楚 STL 设计思路但没时间读源码的人。下面我直接按自己的实现过程来讲尽量把每一步背后的为什么顺带说清楚。2. 技术选型底层容器为什么是红黑树2.1 哈希表、平衡树、红黑树的取舍set/map 底层容器选型其实是个很有意思的话题。很多人会问既然有哈希表为什么 map 不用哈希表当底层哈希表查找 O(1) 明明更快。原因在于 map 的接口承诺了有序遍历这个语义。你在 map 上做中序遍历拿到的是按 key 有序排列的结果这是哈希表做不到的。哈希表虽然有 unordered_map 这个选项但它牺牲了有序性来换常数时间。那为什么不是 AVL 树AVL 树也是平衡树也支持有序遍历。问题的关键在于平衡的代价。AVL 树对平衡的要求非常严格任意节点的左右子树高度差不能超过 1这导致插入删除后的旋转调整频率很高。红黑树则放宽到了最长路径不超过最短路径的 2 倍旋转次数明显减少。同样是 logN 级别的复杂度红黑树把调整成本摊薄到了插入删除操作里整体表现更平滑。STL 选红黑树坐镇 set/map本质上是写操作性能优先的设计选择。2.2 迭代器语义对底层结构的要求set/map 迭代器要求支持 和 -- 操作而且最关键的语义是自增自减后的元素仍然保持有序。这直接排除了哈希表因为哈希表迭代器的顺序依赖桶的排列元素在迭代器看来是乱序的。红黑树天然就是一棵二叉搜索树中序遍历结果天然有序。迭代器 设计成寻找中序序列的后继节点就顺理成章。所以选红黑树不只是性能取舍更是语义匹配的结果。2.3 为什么不直接拿库里的红黑树模拟实现的最大价值在于亲手造轮子。直接调标准库的 set/map 当然方便但这样一来你对迭代器失效规则、移动语义、异常安全的理解还是停留在背接口阶段。自己写 RBTree 类模板把它改造成 set 和 map 的底层我才能体会到 STL 里两层设计的精妙第一层是通用的红黑树模板负责维护平衡和树形结构第二层是 set/map 的封装负责屏蔽细节、暴露容器的语义接口。这个分层思想本身就是 C 封装的高级玩法。3. 实现设计从红黑树节点到 set/map 外壳3.1 基础节点设计与哨兵节点红黑树节点我设计成带颜色标记的二叉搜索树节点。enum Color { RED, BLACK }; template typename T struct RBTreeNode { T data; Color color; RBTreeNodeT* left; RBTreeNodeT* right; RBTreeNodeT* parent; RBTreeNode(const T val T()) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };这里有个关键设计新节点默认是 RED。为什么插入红色节点可能违反不能有连续红色节点这一条只涉及局部修复。插入黑色节点会直接破坏每条路径黑色节点数相同这个全局性质修复起来涉及整棵树代价大得多。所以默认红色把麻烦留给调整函数。哨兵节点我用 nullptr 处理。但很多标准库实现会用单独的 nil 节点这样可以让 end() 迭代器指向这个哨兵而不是 nullptr。模拟实现里用 nullptr 也够用只是 end() 迭代器内部指针为空operator 到 end() 时要特殊判断后面讲迭代器时细说。3.2 红黑树类模板的设计要点红黑树我写成一个三个模板参数的类模板template typename Key, typename Value, typename KeyOfValue class RBTree { // ... };Key 是键的类型Value 是存储数据类型KeyOfValue 是一个仿函数负责从 Value 里取出 Key。为什么要第三个参数因为 set 里 Value 和 Key 是同一个类型而 map 里 Value 是 pairconst Key, T。底层红黑树插入删除时都要比较键值如果红黑树直接假设 Value 里有个 first 字段那 set 就没法用了。用仿函数做适配器红黑树只需要调 KeyOfValue()(data) 取键完全不关心 Value 具体长什么样。set 传的 KeyOfValue 是这样struct SetKeyOfValue { const K operator()(const K key) const { return key; } };map 传的 KeyOfValuestruct MapKeyOfValue { const K operator()(const pairconst K, V kv) const { return kv.first; } };这一层抽象看懂了后面 set/map 封装就非常简单了。3.3 set 和 map 的外壳封装set 的定义template typename K class set { struct KeyOfValue { const K operator()(const K key) const { return key; } }; RBTreeK, K, KeyOfValue tree; public: // 接口转发 };map 的定义template typename K, typename V class map { struct KeyOfValue { const K operator()(const pairconst K, V kv) const { return kv.first; } }; // 注意这里 Key 类型用 const K保证 key 不被修改 RBTreeK, pairconst K, V, KeyOfValue tree; public: // 接口转发 };map 的 Value 为什么是 pairconst K, V因为 map 的迭代器解引用返回的是 pairconst K, V也就是你不能通过迭代器修改 key只能修改 value。const K 保证了这一点是编译器帮你把关防止破坏树的有序性。底层红黑树所有接口函数我建议都做成公有的因为 set/map 就是一层很薄的转发壳没必要给 RBTree 再搞一套复杂访问控制。实际项目里可以直接把 RBTree 的接口统一命名然后在 set/map 里逐个映射。4. 核心算法插入与旋转的完整实现4.1 插入的框架逻辑红黑树的插入分两个阶段普通二叉搜索树插入然后修复颜色。bool Insert(const Value val) { if (root_ nullptr) { root_ new Node(val); root_-color BLACK; return true; } Node* cur root_; Node* parent nullptr; KeyOfValue ko; while (cur) { parent cur; if (ko(cur-data) ko(val)) cur cur-right; else if (ko(cur-data) ko(val)) cur cur-left; else return false; // 键值重复插入失败 } cur new Node(val); cur-parent parent; if (ko(parent-data) ko(val)) parent-right cur; else parent-left cur; InsertFixUp(cur); // 调整颜色和旋转 return true; }这里有一个容易被忽略的细节插入失败返回 false重复键不插入。这个行为要跟标准库对齐标准库的 insert 对重复键是静默失败的只影响返回结果。4.2 三条调整路线详解Case 1父节点是红色叔叔节点是红色父节点红叔叔节点红祖父节点必黑。此时把父和叔都变黑祖变红把 cur 指针向上移到祖父节点继续循环。这相当于把冲突往上推了一层。void InsertFixUp(Node* cur) { while (cur ! root_ cur-parent-color RED) { Node* parent cur-parent; Node* grandparent parent-parent; if (parent grandparent-left) { Node* uncle grandparent-right; if (uncle uncle-color RED) { parent-color BLACK; uncle-color BLACK; grandparent-color RED; cur grandparent; } else { // Case 2 / Case 3 旋转处理 } } else { // 镜像对称的处理 } } root_-color BLACK; }Case 2叔叔是黑色cur 是父的右孩子左右双旋这种形态需要先对父节点做一次左旋转换成 Case 3再做右旋处理。为什么要先旋一次因为调整逻辑要求 cur、parent、grandparent 处于直线形态cur 是 parent 的哪一侧孩子parent 就是 grandparent 的哪一侧孩子折线形态必须先捋直。Case 3叔叔是黑色cur 是父的左孩子右单旋直接对祖父节点做右旋然后 parent 变黑、grandparent 变红。旋转完成后这棵子树已经满足红黑树性质可以跳出循环。旋转本身不复杂就是指针重连但要注意 parent 指针也必须同步更新。初学最容易忘的就是这一步导致后续找祖先节点时空指针崩溃。4.3 左旋右旋代码实现左旋的具体代码void RotateLeft(Node* parent) { Node* subR parent-right; Node* subRL subR-left; parent-right subRL; if (subRL) subRL-parent parent; Node* pparent parent-parent; subR-left parent; parent-parent subR; if (pparent nullptr) { root_ subR; root_-parent nullptr; } else { if (pparent-left parent) pparent-left subR; else pparent-right subR; subR-parent pparent; } }右旋完全对称不再贴完整代码。我的经验是写旋转函数一定要先把 oldParent 的父节点存下来因为旋转会让它失去当前父节点这个引用后面重新连线时你可能已经找不到这个变量了。旋转完后如果能画一棵树验证一遍会更稳强烈建议在纸上画几个 case别只靠脑补。4.4 删除操作的调整思路删除是红黑树里最头疼的部分模拟实现时我的取舍是先把删除流程整体跑通重点处理调整逻辑不必追求和标准库一根行都不差。删除的核心是找到顶替删除节点的节点。如果被删节点有两个孩子就找它的中序后继右子树最左节点把后继的 data 复制到被删点然后删除后继。这样一来真正物理删除的节点最多只有一个孩子问题就简化了。如果被删节点是红色直接删不影响黑高。如果被删节点是黑色就破坏了性质需要调用 DeleteFixUp。调整的核心思路是把少了一个黑的问题转移到被删节点原来的位置通过兄弟节点和父节点的颜色组合逐层往上修复。这一块写起来代码很长我建议模拟实现时先把删除节点 顶替节点这部分写对调整部分可以只处理部分典型场景比如兄弟红的情形、兄弟黑且有红孩子的情形。完整覆盖所有 case 需要很长的篇幅初学者容易写着写着把自己绕晕。5. 迭代器实现中序遍历的指针艺术5.1 迭代器为什么不能是普通指针红黑树的节点在内存里不是连续排布的天然不支持原生指针的 / --。所以必须自己封装一个迭代器类重载运算符让它表现得像指针。我设计的迭代器template typename T, typename Ref, typename Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; Node* node; RBTreeIterator(Node* n nullptr) : node(n) {} Ref operator*() const { return node-data; } Ptr operator-() const { return (node-data); } bool operator!(const RBTreeIterator other) const { return node ! other.node; } // 关键是 和 -- 的实现 };模板参数 Ref 和 Ptr 用来适配普通迭代器和 const 迭代器。set 里 T 是 Kmap 里 T 是 pairconst K, V同一个迭代器模板就能复用。5.2 operator 找后继的规则中序后继的定义是中序遍历序列中当前节点的下一个节点。分两种情况当前节点右孩子不为空去右子树的最左节点右孩子为空向上回溯直到当前节点是父节点的左孩子父节点就是后继Self operator() { if (node-right) { node node-right; while (node-left) node node-left; } else { Node* parent node-parent; while (parent parent-right node) { node parent; parent node-parent; } node parent; } return *this; }这个逻辑我建议不要背代码而是拿一棵树自己走一遍。本质是当前节点已经是某个左子树的根它的下一个节点在中序序列里就是它的父节点或更远的祖先。忘了这条规则就很容易写错比如向左走到最左其实是找最小元素不是继承。类似地operator-- 是找前驱左孩子不为空就往左子树的最右节点走反之向上找第一个当前节点是父节点右孩子的拐点。5.3 begin() 和 end() 的实现begin() 要返回树中最小元素对应的迭代器就是最左节点iterator begin() { Node* leftmost root_; while (leftmost leftmost-left) leftmost leftmost-left; return iterator(leftmost); } iterator end() { return iterator(nullptr); }关键问题来了如果一棵树为空树begin() 返回什么leftmost 就是 nullptrbegin() 和 end() 是同一个迭代器这恰好符合空容器的 begin() end() 语义。但如果树非空普通 操作从最大节点继续自增时会走到 nullptr也就是 end()这也符合逻辑。但有个坑从 end() 往前 -- 应该得到最大元素这个操作标准库是支持的。模拟实现里如果 end() 是 nullptr-- 就没法实现。标准库用哨兵节点就是为了让 end() 指向一个真实的节点可以支持 --。模拟实现如果想支持 rbegin()/rend()建议引入 nil 哨兵。我这个简化版就不做了把 end() 的 -- 留作扩展。6. map 和 set 的差异化接口6.1 operator[] 与 Insert 的默契配合map 的 operator[] 是一个非常高频的操作V operator[](const K key) { pairiterator, bool ret Insert(make_pair(key, V())); return ret.first-second; }它先尝试插入如果 key 已存在Insert 返回已有节点位置不会覆盖 value。然后不管插入成功与否都返回那个节点里 second 的引用。这样m[key] value既能覆盖已有值又能初始化新键的值语义完全贴合直觉。这里有个细节Insert 的返回值设计成 pairiterator, booliterator 指向插入位置或已存在的相同键位置bool 表示是否插入成功。这个设计不是拍脑袋定的标准库就是这样用户在调用 insert 时可以根据 bool 判断到底写入没有。6.2 set 的迭代器为什么没有 operator[]set 的键值不可修改迭代器解引用返回 const 类型引用所以刻意不提供 operator[]避免用户通过 set[k] 去写值破坏有序性。编译器层面已经通过 const 限制挡掉一部分接口层面再挡一层双保险。6.3 find、erase 和 clear 的转发细节find 是容器的高频操作iterator find(const K key) { return tree_.Find(key); }底层就是标准二叉搜索树的查找路径从根开始比较小于往左、大于往右。返回 nullptr 就代表找不到对应 end()。erase 要注意返回值语义。标准库 C11 后的 erase(key) 返回删除个数0 或 1。模拟实现可以让底层删除函数返回 bool转发时转成整数。clear 则递归释放整棵树我用后序遍历销毁节点这样儿子没了再去释放父节点不会出现访问已释放内存的问题void Destroy(Node* root) { if (root nullptr) return; Destroy(root-left); Destroy(root-right); delete root; }7. 实战调试与常见问题7.1 插入后验证红黑树性质的测试策略模拟实现写完第一件事不是跑性能测试而是验证性质。我建议写一个 CheckValid 函数递归验证四条性质bool CheckValid(Node* root, int blackCount, int benchmark) { if (root nullptr) { if (benchmark -1) benchmark blackCount; return blackCount benchmark; } if (root-color RED root-parent root-parent-color RED) return false; if (root-color BLACK) blackCount; return CheckValid(root-left, blackCount, benchmark) CheckValid(root-right, blackCount, benchmark); }重点检查连续红色和黑高一致性。连续红色用父节点是红时父节点的父节点必须存在且为黑来判定。黑高一致性是在递归过程中统计黑色节点数拿最左路径的黑色数当基准其他路径必须一致。我之前调试时遇到过一个神奇现象插入上千个随机数后性质还是对的但插入某个特定序列就崩了。后来定位发现是旋转函数里忘了更新 parent 的 parent 指针导致某条路径上 parent 链断裂上面提到的检查函数在那种情况下根本遍历不到所有节点。所以验证函数本身也要足够严谨遍历要保证覆盖整棵子树。7.2 典型编译错误set 里 Key 类型到底是 const 还是非 const一个非常容易踩的坑是 set 的 Key 类型。如果 set 的模板参数是 K那么 insert 的参数类型应该是 const K读取数据时返回 const K。如果你不小心把 insert 定义成 K 传参那么调用 set.insert(5) 就会出问题因为整型字面量 5 绑定不到非常量引用上编译直接报错。这也是为什么很多容器的插入参数都设计成 const T 的原因。7.3 内存泄漏与迭代器失效问题红黑树的销毁必须走后序遍历我之前偷懒写过先 delete 根节点再递归释放子节点的野代码调试时出现地址访问冲突才意识到问题。内存泄漏在模拟实现里很难直接暴露建议配合 Valgrind 或者编译器自带的 AddressSanitizer 检查。迭代器失效是另一个微妙点。红黑树的 insert 不涉及节点的物理移动所以插入操作后所有迭代器都有效。但 erase 后被删除节点的迭代器必然失效这个语义要记清楚。模拟实现时如果 erase 函数内部直接 delete 节点外部还握着的迭代器就变成野指针这种问题跑起来才惊悚理解原理后就知道它本来就是失效状态。7.4 标准库对比还有哪些差距模拟实现和真实 STL 还有不少差距说几个我自查时发现的点内存分配用的 new/delete真实 STL 用 allocator 模板做内存管理没有实现移动语义相关的优化没有实现 C11 以后提供的节点式接口比如 extract、mergeend() 的 -- 操作支持不够依赖哨兵节点这些不写在代码里不代表不用知道面试时你主动说出来这些差距反而显得你对源码有更深入的理解。8. 基于多次重构的个人体会写这个模拟实现我前后换过三版设计最大的感悟是要先把红黑树整体跑通再考虑 set/map 封装千万别一上来就两边一起写。第一版我试图一步到位同时写好底层树和上层容器结果在迭代器的 const 语义上报了一堆类型不匹配的错调试了两天才分清是迭代器类型问题还是树结构问题。第二版我把红黑树完全独立出来所有接口用 bool 返回先把树内部调整逻辑验证通过再往上层封装。这一版虽然多写了一些转发代码但逻辑清晰排查问题容易多了。另外想提醒一点插入调整的三个 Case 一定要拆开写清楚注释别贪图代码短把逻辑揉在一起。写旋转时一定要配图示哪怕是简笔画都行。只靠记忆去调红黑树的 bug十个有九个在旋转的 parent 指针重连上栽跟头。我最后调试阶段就养成了习惯每次旋转完都立刻跑一遍 CheckValid性质不对就一步步打印节点颜色来定位。代码写完之后再去翻一眼标准库头文件的源码结构你会发现很多东西都是相通的仿函数适配那套设计尤其精妙。这个模拟实现项目做到最后最大的收获不只是会写红黑树了而是学会了怎么用模板和仿函数把一套底层逻辑优雅地复用到两个不同语义的容器上。这层理解靠背知识点是真的背不出来。