手写红黑树封装 mymap/myset：理解 STL 容器底层设计

学了半个月红黑树又花了两天把它封装成 mymap 和 myset 之后我才算真正理解 STL 里 map 和 set 那些看着不起眼的接口设计到底有多讲究。这个项目如果只用一句话概括就是手写一棵红黑树再用模板封装出两个对外表现完全不同、底层却共用同一套代码的容器。它适合那些已经掌握了红黑树旋转和变色原理、但想看看这东西在工程里怎么落地的人也适合想搞懂 STL 源码但又啃不下整本源码剖析的 C 学习者。读完这篇你能复现出一套结构清晰、迭代器完备、支持范围 for 的 mymap 和 myset更重要的是搞明白为什么一定要这么封装。1. 为什么非要自己封装红黑树STL 容器的底层真相很多人用 map 和 set 用得飞起但从来没想过它们底层长什么样。标准库里的 map、set、multimap、multiset 这四兄弟底层几乎全是红黑树只有少数实现比如某些新版的 std::map换成了更复杂的结构但绝大多数教科书和面试场景下红黑树就是它们的标准答案。1.1 红黑树到底解决了什么问题红黑树是一棵近似平衡的二叉搜索树它不追求绝对平衡而是通过节点颜色和五条性质约束保证任意路径的长度差不会超过一倍。这个弱平衡策略带来的直接收益是插入、删除、查找的时间复杂度都能稳定在 O(log n)而且插入删除后的调整代价比 AVL 树小得多。我一开始也想偷懒觉得既然只是学习直接用二叉搜索树不行吗结果插入一个有序序列树直接退化成链表查找变成 O(n)性能惨不忍睹。后来试了 AVL 树平衡是平衡了但插入删除需要大量的旋转编码复杂度高而且对查询多、修改少的场景才算划算。红黑树的旋转次数比 AVL 少整体实用性更高这也是 C STL 选它而不是选 AVL 树的根本原因。1.2 封装的核心难点不是红黑树本身说实话红黑树的插入调整、删除调整这些算法网上一搜一大把背下来都不是难事。真正的难点在于封装二字同一个底层红黑树怎么做到既能存 key又能存 pairkey, value怎么让红黑树的迭代器支持 和 --从而让 map 和 set 能走范围 for怎么处理 const 迭代器和普通迭代器的隐式转换怎么让红黑树内部的节点类型对外不可见不泄露实现细节这些问题如果没想透写出来的所谓 mymap 和 myset 大概率只是把红黑树的插入删除包了一层壳迭代器、const 正确性、operator[] 这些 STL 容器的核心体验全都缺失。提示封装的意义不只是把代码藏起来而是让外部使用者和内部实现之间形成一堵稳定的墙。这堵墙设计得好不好直接决定了你的容器能不能像标准库一样好用。2. 先花二十分钟把红黑树机制捋顺动手封装之前必须把红黑树本身的机制复习一遍。这里不展开推导所有情况只把插入和删除调整的核心原则说透。如果这部分不熟后面调试会非常痛苦。2.1 五条性质速记与失衡场景红黑树的五条性质用一句话记忆就是节点非红即黑根黑叶黑空节点视为黑红节点的孩子必黑任意节点到其所有叶子节点的路径上黑色节点数相同。插入新节点默认染红因为染红不会破坏路径上黑色节点数相同这一条。但染红可能引入红红冲突也就是红节点的孩子不能是红。一旦冲突就要通过变色和旋转来修复。调整时主要看叔叔节点的颜色叔叔为红直接变色祖父变红父和叔变黑然后把祖父当作新节点继续向上处理。叔叔为黑或不存在单旋或双旋然后变色调结构。2.2 删除调整的记忆锚点删除比插入麻烦得多因为删除一个黑色节点会破坏黑色节点数相同的性质。STL 的删除实现用了哨兵节点和统一的替换逻辑但自己手写时我更推荐一个简化路径先按普通二叉搜索树删除节点如果删的是红色节点直接完事如果删的是黑色节点把少了一个黑色的问题沿着树向上传递。兄弟为红先旋转让兄弟变黑转化成兄弟为黑的情况。兄弟为黑兄弟的两个孩子都为黑把兄弟变红问题向上传递。兄弟为黑兄弟的左孩子为红右孩子为黑先对兄弟做右旋变成兄弟的右孩子为红的情况。兄弟为黑兄弟的右孩子为红对父节点左旋调整颜色问题终结。这四个 case 是删除调整的核心建议画图理解不要死记。封装的时候我给每个 case 都写了注释方便自己后来回看。3. 底层节点设计三叉链和哨兵节点红黑树的节点设计决定了迭代器能不能高效地做 和 --。市面上很多教程写红黑树节点只存左右孩子和父节点也就是三叉链。三叉链是必须的因为没有父节点指针迭代器的自增自减根本没法回溯。3.1 节点结构代码节点里需要存颜色、左右孩子指针、父节点指针以及用户的数据。数据用模板参数 T 表示对于 mymap 来说 T 是 pairconst Key, Value对于 myset 来说 T 就是 Key 本身。enum Colour { RED, BLACK }; template class T struct RBTreeNode { T _data; // 节点存储的数据 RBTreeNodeT *_left; // 左孩子 RBTreeNodeT *_right; // 右孩子 RBTreeNodeT *_parent; // 父节点三叉链 Colour _col; RBTreeNode(const T data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) { } };这里有个细节新节点默认染红。为什么因为插入红色节点最多违反红节点的孩子不能是红这一条而插入黑色节点会直接破坏黑色节点数相同这一条修复成本完全不同。所以默认染红是共识。3.2 为什么需要 header 哨兵节点STL 里的红黑树实现会在树的顶部加一个 header 节点它不存真实数据但它的左孩子指向树的最左节点右孩子指向树的最右节点父节点指向根而根的父节点又指回 header。这样做的直接好处是迭代器找 begin 和 end 非常快begin 就是 header 的左孩子end 就是 header 本身。双向迭代器的 和 -- 在边界处理上不会出现空指针。我一直觉得这个设计是整个封装里最巧妙的地方。没有哨兵节点begin() 要一直往左走到空end() 还要额外判断而且迭代器自增到 nullptr 时的行为很难处理。有了 headerend() 就指向一个固定的逻辑尾逻辑统一了代码大幅简化。3.3 节点如何同时服务 map 和 set这就是泛型编程最精彩的地方。我刚开始写的时候天真地打算写两棵红黑树一棵存 pair一棵存 key代码重复得亲妈都不认识。后来才意识到只要往红黑树的模板参数里传入一个萃取器仿函数告诉树怎么从 T 里取出 key 来比较大小问题就迎刃而解。// 红黑树的模板参数K 是 key 的类型T 是节点数据类型KeyOfValue 是从 T 中取 key 的仿函数 template class K, class T, class KeyOfValue class RBTree;对于 mysetT 就是 KKeyOfValue 返回 T 本身对于 mymapT 是 pairconst K, VKeyOfValue 返回 T.first。这个设计是 STL 里最值得反复咀嚼的部分我会在后面专门展开。4. 模板参数的艺术KeyOfValue 仿函数与统一比较很多人封装容器失败就是死在怎么让一套红黑树代码同时服务 map 和 set这一步。这里面的关键不是黑魔法而是一个看起来平平无奇的仿函数。4.1 从 T 里取出 K假设我写了这样的函数用于插入Node *newnode new Node(data); Node *parent nullptr; Node *cur _root; while (cur) { parent cur; if (kv.key(cur-_data) data) // 需要知道怎么比较 cur cur-_right; else if (kv.key(cur-_data) data) cur cur-_left; else return false; // 重复键插入失败 }这个 kv 是一个仿函数对象负责从节点的 _data 中取出用于比较的键。如果 _data 是 pairkv 就返回 .first如果 _data 就是 keykv 就返回它自己。mymap 中的 KeyOfValue 可以写成struct MapKeyOfValue { const K operator()(const pairK, V data) const { return data.first; } };myset 中的 KeyOfValue 就简单得多struct SetKeyOfValue { const K operator()(const K data) const { return data; } };这样一来红黑树的代码只需要写一份。查找时调用 _keyofvalue(cur-_data)插入时调用 _keyofvalue(data)所有比较操作都经过这层萃取。这就是泛型编程中的策略萃取思想也是 STL 里 accumulate、sort 等算法使用自定义比较器的方式。4.2 map 为什么要存 pairconst K, V之前我试过直接存 pairK, V结果用户可以通过迭代器修改 key树的结构就被破坏了。红黑树作为二叉搜索树它的有序性完全依赖 key 的比较关系一旦 key 被改树的正确性就坍塌了。标准库的 set 的 iterator 和 const_iterator 的 operator* 都返回 const Tmap 的 iterator 的 operator* 返回 pairconst K, V本质上都在限制用户修改 key。我把 key 声明成 const 也是同样道理从类型系统层面保证不能改。4.3 比较器也要放进类模板如果你只打算支持 key 类型自带 operator 的场景那可以不用模板比较器。但为了通用性应该给红黑树增加一个 Compare 模板参数。我在实际封装时把比较器和 KeyOfValue 都传进了 RBTree 的模板参数这样 mymap 和 myset 未来可以轻松支持自定义排序规则。注意在类内部要声明一个 Compare 类型的成员对象并在构造函数中初始化。5. 迭代器实现红黑树封装的灵魂如果红黑树只是插入删除那点事它充其量是个数据结构练习题。封装成容器最提档次的环节就是迭代器。迭代器是连接容器和算法的桥梁没有迭代器范围 for 全是空中楼阁。5.1 迭代器类的骨架template class T, class Ref, class Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; typedef RBTreeIteratorT, Ref, Ptr Self; Node * _node; RBTreeIterator(Node *node nullptr) : _node(node) {} Ref operator*() const { return _node-_data; } Ptr operator-() const { return _node-_data; } };这个模板参数的设计我吃了很多亏才明白。Ref 和 Ptr 用于区分普通迭代器和 const 迭代器普通迭代器传 T 和 T*const 迭代器传 const T 和 const T*。同一个迭代器模板实例化两次就能让同一套 operator 和 operator-- 逻辑被两种迭代器复用不用写两遍。5.2 operator 的三种情况迭代器自增的本质是找到中序后继。中序遍历的顺序是左子树、根、右子树所以当前节点如果有右子树下一个访问的节点就是右子树的最左节点如果没有右子树就要沿着父节点向上找直到找到第一个自己是父节点的左孩子的祖先这个祖先就是中序后继。Self operator() { if (_node-_right) { _node _node-_right; while (_node-_left) _node _node-_left; } else { Node *cur _node; Node *parent cur-_parent; while (parent cur parent-_right) { cur parent; parent cur-_parent; } _node parent; } return *this; }注意那个 while (parent cur parent-_right) 的条件。我第一次写的时候判断方向写反了导致迭代器在递增到根节点时直接宕机这个坑后面还会细说。5.3 operator-- 与 header 的配合自减逻辑正好是自增的镜像如果当前节点有左子树下一个节点是左子树的最右节点如果没有左子树就向上找直到找到第一个自己是父节点的左孩子的祖先。但有个边界问题当迭代器指向 end()也就是 header时执行 -- 应该回到整棵树的中序最后一个节点也就是最右节点。没有 header 的话这个操作很难处理有了 header直接让 _node _node-_left也就是树的最右节点不对header 的左孩子是最左节点——这里细节要写清楚其实标准实现里迭代器自减需要特殊处理 end() 的情况。我的做法是在 operator-- 里先判断 _node 是不是 header如果是直接返回最右节点。判断方式就是 _node-_parent-_parent _node 之类的循环条件或者给迭代器额外传入 header 指针。为了简化我直接在 RBTree 内部提供了 begin() 和 end() 的实现end() 返回 header 的迭代器operator-- 第一行判断当前节点右孩子是不是 header 的类似逻辑。这里如果偷懒最简单的方案是给节点加一个 _isHeader 标记但这个多少有点脏。STL 的妙处在于它利用 header 的左右孩子指向最左和最右节点来巧妙处理我最终也采用了类似思路。5.4 普通迭代器到 const 迭代器的转换这是很多新手封装时最容易漏掉的一环。set 的 iterator 本质上应该就是 const_iterator因为 key 不能被修改。map 的 iterator 可以修改 value但不能修改 key。但在实现层面红黑树对外提供的 begin() 和 end() 一般是普通迭代器。如果 mymap 的 const 版本 begin() 需要返回 const_iterator而普通版本的 begin() 返回 iterator这两者之间如果没有转换关系代码会非常难写。解决办法是给迭代器模板增加一个带参构造函数template class T, class Ref, class Ptr struct RBTreeIterator { // 支持普通迭代器向 const 迭代器的转换 RBTreeIterator(const RBTreeIteratorT, T, T* it) : _node(it._node) { } };这个构造函数存在的意义是当 Ref 和 Ptr 恰好是 const T 和 const T* 时可以从普通迭代器隐式构造出 const 迭代器。反过来则不行因为参数类型不匹配。这一招和 C 里允许 const 引用绑定非 const 对象的设计异曲同工。6. mymap 和 myset 的封装让红黑树对外隐身底层红黑树写完封装 mymap 和 myset 反而成了最轻松的部分。但这里也有不少决定容器手感的细节。6.1 mymap 的核心接口实现我实现的 mymap 支持了 insert、erase、find、operator[]、begin、end、size 这几个核心接口。其中 insert 的返回值是一个 pairiterator, bool这比只返回 bool 要实用得多。pairiterator, bool insert(const pairK, V data) { return _t.Insert(data); }operator[] 的实现是重头戏它依赖 insert 的返回值。标准库的 operator[] 的逻辑是如果 key 存在返回对应的 value 引用如果不存在先插入一个默认构造的 value再返回引用。V operator[](const K key) { pairiterator, bool ret _t.Insert(make_pair(key, V())); return ret.first-second; }这段代码只有三行但信息量很大。ret.first 是迭代器ret.first-second 是 value 的引用。如果 key 之前不存在Insert 会自动插入一个值初始化的 V然后返回指向新节点的迭代器。正因为 insert 返回了迭代器operator[] 才能写得这么干净。6.2 myset 的接口与防修改设计myset 的 insert 返回的也是 pairiterator, bool这点和 map 类似但 iterator 的 operator* 返回的是 const K用户不能修改集合里的元素。pairiterator, bool insert(const K key) { return _t.Insert(key); }myset 的 begin() 和 end() 我直接返回了红黑树的 const_iterator这样在外部即使通过非 const 对象拿到迭代器也不能改动元素内容。这个设计看起来有点过度防御但正是 set 语义的要求集合元素顺序依赖 key一旦修改就无法保证有序性。6.3 构造、析构与拷贝控制很多初学者封装容器时只写了构造函数和析构函数忽略了拷贝构造和赋值重载结果容器被拷贝时直接浅拷贝两个对象共享同一棵树的节点析构时造成二次释放。我给 RBTree 实现了深拷贝RBTree(const RBTree t) { _root CopyTree(t._root); }CopyTree 递归复制每个节点同时维护新的父指针。析构函数用后序遍历销毁所有节点然后用 header 独立申请。拷贝赋值用经典的拷贝并交换思路先传值再 swap异常安全且代码简洁。7. 实操中的坑与问题排查实录这部分才是真正的实战经验。封装过程中我踩了不少坑每一个都花了不少时间排查写出来帮大家少走弯路。7.1 迭代器 死循环和段错误我最早实现的 operator 里没有处理好从右子树回到根的情况。调试时发现当迭代器指向某个节点的右子树中最右节点时继续 会一直向上回溯到根然后 parent 变成空访问空指针的 _right 直接段错误。排查方法在 while 循环里打日志输出当前节点的地址和数据很快发现是 cur parent-_right 的条件写成了 cur parent-_left导致回溯条件完全相反。这一点和二叉搜索树中序后继的定义有关自增找祖先时是找第一个不是右孩子的祖先所以判断当前节点是不是右孩子很关键。7.2 insert 返回值引发的编译错误我第一次实现 insert 时返回的是 bool后来改成 pairiterator, bool 后红黑树的 Insert 和 mymap 的 insert 签名都要一起改。改 redblacktree 里的实现时漏改了一处递归调用的返回逻辑编译直接报 cannot convert bool to pair。排查思路先在红黑树层把所有返回路径统一成 pairiterator, bool再在 mymap 层适配最后才写 operator[]。从底层往上层逐层改不容易漏。7.3 const 迭代器报 access violation 的教训我在 mymap 的 const 版本 begin() 里直接返回了 iterator没有构造 const_iterator。调用范围 for 时编译器优先绑定 const_iterator结果和我底层返回的 iterator 类型不匹配运行时报了 access violation c0000005 这样的错误。根本原因是迭代器的普通到 const 转换没有做或者做了一半。后来补上了带参构造的转换函数并且 const begin() 显式返回 const_iterator问题就消失了。这个错表面看是运行时崩溃其实是类型系统上的缺口。7.4 拷贝构造没写导致的双重释放这个是最典型的临时变量析构时把树的节点全删了原对象再析构时又删一遍直接崩。排查方式是启用地址消毒器AddressSanitizer编译时加 -fsanitizeaddress它能明确标出 double free 的两次调用栈。发现问题后补了深拷贝构造整个容器才稳定。注意写容器类拷贝控制三件套必须想清楚。凡是拥有裸指针资源的类默认拷贝构造函数基本都是错的。8. 性能验证与后续扩展方向封装完成后我写了一个简单的测试程序往 mymap 里插入 100 万个随机键再随机查找 100 万次耗时比 std::map 大约慢 10%~15%。这个差距主要来自我的红黑树没有做内存池优化每次插入都走系统 new。加一个简单的节点池分配器这个差距可以缩到 5% 以内。后续可以考虑的扩展方向有不少给红黑树增加 lower_bound 和 upper_bound让 mymap 和 myset 支持区间查找。仿照 std::multimap 和 std::multiset修改插入逻辑去掉去重限制。增加空间配置器参数支持自定义内存分配。用红黑树实现一个简单的定时器管理模块把学到的知识挪到真实项目中。我个人在实际操作中的体会是封装红黑树这个过程最大的收获不是会写红黑树本身而是通过让同一棵树同时服务两种容器这件事真正理解了模板、仿函数、迭代器、const 正确性这些平时分散在不同章节的知识点是怎么拧成一股绳的。很多知识点单个拿出来都不难但组合在一起就变成了 STL 源码面前那一堵看似高不可攀的墙。自己亲手拆一次、搭一次这堵墙就塌了。最后再分享一个小技巧调试红黑树调整逻辑时不要只在脑子里模拟旋转写一个递归的打印函数把整棵树的节点颜色和子树结构打出来每个 case 验证一遍。我当时打印函数写了二十分钟后来帮我省了不止两小时。红黑树的代码写对了是福分写错了能调出验证逻辑才是真功夫。