前阵子重新啃 STL 源码把map和set的封装彻底捋了一遍越看越觉得这两个容器就是“一棵红黑树换了几张皮”。很多人在学的时候把map、set、multimap、multiset当成四个独立容器去背实际在底层它们共用同一棵红黑树模板只是通过模板参数做了不同的封装配置。这篇笔记就是记录我自己的拆解过程核心解决三个问题——树节点里存什么、怎么从存储的数据里提取出用于比较的 key、以及迭代器如何在中序遍历规则下正确工作。适合已经会基本使用map/set、想进一步搞明白底层封装原理或者正在自己实现一个红黑树容器的朋友参考。1. 为什么 map 和 set 必须“封装”而不是各写各的先看一个很多人忽略的事实标准库里的std::map、std::set、std::multimap、std::multiset底层都是同一棵红黑树。以 SGI STL 的实现为例内部核心类叫_Rb_tree它的模板定义大概长这样template class Key, class Value, class KeyOfValue, class Compare, class Alloc allocatorValue class _Rb_tree;注意这五个模板参数缺一个都不行Key用于排序和查找的键类型。Value节点里真正存储的数据类型。KeyOfValue从Value中取出Key的函数对象这是整个封装里最巧妙的一环。Compare比较规则默认lessKey。Alloc空间配置器。1.1 四个容器的配置差异其实只有三处把四个容器的配置摆在一起看封装逻辑就非常清楚了。我画过一张对照表每次看都觉得很直观容器KeyValue节点存的数据提取方式插入语义setKKK直接返回 key 本身唯一插入multisetKKK直接返回 key 本身多重插入mapK, VKpairconst K, V返回kv.first唯一插入multimapK, VKpairconst K, V返回kv.first多重插入发现没有红黑树的核心算法、旋转逻辑、颜色调整、查找路径四个容器全部一样。真正不同的地方只有三个维度节点里装的是什么set装的是裸的 keymap装的是pairconst K, V。怎么从节点数据中拿到参与比较的 key一个是“自取”一个是“取 pair 的第一个字段”。插入时允不允许 key 重复set/map走insert_uniquemultiset/multimap走insert_multi。这就是封装的本质把公共的树形结构、平衡算法下沉到基类/底层的RBTree把数据类型的差异通过模板参数暴露出来。容器类只是薄薄的一层适配壳用户看到的map、set接口背后全部转发给底层树。1.2 单靠继承实现不了这种复用有人会问“这种复用为什么不写成红黑树基类让 map 和 set 继承它”继承不是不行但会有一个很别扭的问题基类的节点类型暴露的是Value而map的Value是pairconst K, Vset的Value是K。如果基类直接写死Value那么插入、查找、删除这些函数返回类型就会五花八门。继承的方案会让接口变成虚函数运行时多态消耗性能而且红黑树节点是值语义根本不需要虚函数。用模板参数封装则完全没有这个问题。编译器在实例化RBTreeK, V, KeyOfT时会为map和set各自生成一份独立代码节点类型、查找逻辑全部静态确定没有任何虚表开销。STL 设计者把这种思想叫“泛型编程式的封装”本质上就是面向接口编程只是这个“接口”不是虚函数而是编译期模板约束。这个阶段给我的启发是好的封装不是把一堆功能堆在一个类里而是把稳定的算法层和易变的数据层切开让算法层不关心业务字段。2. 第一个核心封装点键值提取器 KeyOfT这是整个封装里我最想先展开的部分因为绝大多数人第一次尝试自己封装红黑树都会卡在同一个问题上map的节点存的是pair但红黑树做比较时比较的是 key不能直接拿两个pair去比。2.1 直接比较 pair 会出什么问题假设红黑树模板把节点数据当成一个普通类型 T直接if (data1 data2)。对setK来说data 就是 key没问题。对mapK, V来说data 是pairconst K, V而pair的operator是字典序比较先比 firstfirst 相等再比 second。这会带来两个致命问题排序规则错了。map要求按 key 排序不是按pair整体排序。两个 key 相同但 value 不同的pair字典序会认为它们“不相等”于是同一个 key 就能插入两次。查找也会乱。find一个 key 时拿什么去和树里的节点比如果拿 key 和pair比类型都对不上。所以红黑树必须知道“如何从 T 中提取出 K”。这就是KeyOfT这个模板参数的来历。2.2 KeyOfT 仿函数的标准写法封装的时候我习惯先定义两个提取器template class K struct SetKeyOfT { const K operator()(const K key) const { return key; } }; template class K, class V struct MapKeyOfT { const K operator()(const pairK, V kv) const { return kv.first; } };然后在红黑树模板里加一个模板参数class KeyOfT内部所有需要比较 key 的地方都统一通过这个仿函数把T转成Ktemplate class K, class T, class KeyOfT class RBTree { // ... bool Insert(const T data) { KeyOfT kot; // 函数对象 const K key kot(data); // 取出本次插入的 key Node* cur _root; Node* parent nullptr; while (cur) { const K curKey kot(cur-_data); if (key curKey) { parent cur; cur cur-_left; } else if (curKey key) { parent cur; cur cur-_right; } else { return false; // 唯一插入key 已存在 } } // 新建节点、链接、向上调整颜色和旋转 // ... } };这样写set实例化时传SetKeyOfTmap实例化时传MapKeyOfT。底层树完全不用关心 T 的内部结构它只知道“给我一个 T我能还你一个可以比较的 K”。2.3 这里最容易忽视的细节const 引用很多新手写KeyOfT时喜欢写K operator()(...)按值返回看起来没毛病但红黑树每次查找都会调好几次提取函数按值返回意味着每取一次 key 就拷贝一次。set还好拷贝的只是 keymap里如果 value 很大或者 key 是string性能差距就非常明显了。更关键的是提取函数必须是const成员函数返回的也必须是const K。因为红黑树在查找过程中不能允许外部修改 key一旦 key 变了整棵树的排序结构就破坏了。用 const 引用既防止误改又避免拷贝。还有一点map的节点数据我上面写的是pairK, V但 STL 里实际用的是pairconst K, V。这里的const K也是封装的一部分pair 里的 key 一旦构造就不允许被修改无论是通过迭代器还是通过节点访问都改不了 key。红黑树保证排序结构不变靠的就是这个 const 约束。3. 第二个核心封装点迭代器与解引用树结构本身封装好了但如果只提供Insert、Find、Erase这三个接口那这棵树还只能算一个数据结构工具不是容器。容器必须提供迭代器让用户能够像遍历数组一样遍历整棵树。而红黑树的迭代器不是简单的指针它需要封装中序遍历的移动规则。3.1 begin 和 end 分别指的是谁红黑树是二叉搜索树中序遍历的结果刚好是 key 从小到大排列。所以要满足“begin 指向最小元素end 指向最后一个元素的下一个位置”迭代器设计就必须遵守中序遍历顺序。begin()指向整棵树最左边的节点也就是最小 key。end()的逻辑位置是最后一个节点的“下一个位置”。STL 里用 header 节点来实现这个哨兵位简化版可以用nullptr代表 end。这里的关键是迭代器遍历的顺序不是物理存储顺序而是逻辑顺序。红黑树的节点在内存里并不连续迭代器必须靠 parent、left、right 三个指针在树里“爬”。3.2 手写 operator 的完整逻辑迭代器最核心的接口就是operator。如果不理解红黑树结构这一步很容易写成递归中序遍历但迭代器不能递归必须用循环沿着指针走。operator的逻辑分两种情况当前节点有右子树下一个节点是右子树里最左边的节点也就是右子树中序遍历的第一个节点。当前节点没有右子树沿着 parent 向上走直到“当前节点是父节点的左孩子”为止那个父节点就是下一个节点。如果走到根都没有满足条件说明当前节点是中序遍历的最后一个节点end。Self operator() { if (_node-_right) { // 右子树不为空找右子树的最左节点 Node* subLeft _node-_right; while (subLeft-_left) { subLeft subLeft-_left; } _node subLeft; } else { // 右子树为空向上回溯 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { cur parent; parent parent-_parent; } _node parent; } return *this; }operator--完全对称当前节点有左子树找左子树最右节点否则向上找“当前节点是父节点右孩子”的第一个祖先。3.3 解引用返回什么map 的迭代器为什么不能改 key迭代器的operator*返回的是节点数据T。对set来说返回K但标准库规定set::iterator其实和const_iterator一样不允许通过迭代器修改 key。对map来说迭代器返回的是pairconst K, Vkey 字段是 const因此改不了 key但可以改 valuemapstring, int m; m[hello] 1; auto it m.begin(); it-second 2; // 合法value 可以改 // it-first world; // 非法first 是 const string要在封装层面实现这个效果迭代器模板不能只有一个类型参数需要把引用类型也模板化template class T, class Ref, class Ptr struct __TreeIterator { typedef __TreeIteratorT, T, T* iterator; typedef __TreeIteratorT, const T, const T* const_iterator; Ref operator*() const { return _node-_data; } Ptr operator-() const { return (_node-_data); } // 普通迭代器到 const 迭代器的转换 __TreeIterator(const iterator it) : _node(it._node) {} };这个模板设计很经典Ref和Ptr在实例化时被确定map::iterator和map::const_iterator实际上是同一个模板的不同实例化结果。封装的意义在这里体现得特别明显——迭代器的行走逻辑全部复用只把“返回可变引用还是不可变引用”这个差异交给模板参数决定。4. 第三个核心封装点插入语义、operator[] 与返回值设计树、提取器、迭代器都有了接下来要解决的是接口层的设计问题。map的operator[]看起来简单实际是多种封装能力叠加出来的结果。4.1 Insert 返回 pairiterator, bool 的原因红黑树底层的Insert返回值不能只是 bool因为使用方经常需要知道“如果插入成功新节点在哪里”“如果插入失败已有节点在哪里”。STL 选择了返回pairiterator, boolpairiterator, bool Insert(const T data) { KeyOfT kot; const K key kot(data); // ... 查找 插入 ... if (插入失败) return make_pair(iterator(已有节点), false); // ... 旋转调整 ... return make_pair(iterator(新节点), true); }为什么不用“插入成功返回新节点迭代器、失败返回 end”这种设计因为那样用户想拿到已有节点还得再调用一次 find多一次 O(logN) 查找。而pairiterator, bool一次调用就同时返回位置和结果效率最高。4.2 map 的 operator[] 三层复用map::operator[]本质上是Insert的语法糖。它的签名是V operator[](const K key);实现思路是调用底层树的 Insert构造一个 value 默认值为V()的节点。如果 key 不存在插入成功返回新节点的 value 引用如果 key 已存在插入失败返回已有节点的 value 引用。V operator[](const K key) { pairiterator, bool ret _tree.Insert(make_pair(key, V())); return ret.first-second; }这里的封装精妙之处在于“三层复用”map复用RBTree的插入逻辑operator[]复用Insert的返回结果用户只需要一行代码就能完成“查找或插入再取值”。而且整个过程只做一次树搜索不会像“先 find 再 insert”那样搜索两次。正是因为operator[]有这种“没有就创建”的特性用m[key]做查询时要特别小心它会把原本不存在的 key 插进去。只想查询时应该用find或at。4.3 multimap 为什么没有 operator[]multimap允许同 key 之前存在多个不同 valueoperator[]的语义本身就模糊了如果 key 重复应该返回哪一个 value标准库干脆不提供operator[]只提供insert和equal_range。这给封装提了个醒不是所有便捷接口都适合所有语义场景接口设计必须匹配容器本身的数学性质。如果自己封装时想给multimap加一个类似功能唯一的合理实现是返回V并引用插入成功的新节点但这样无法通过m[key]访问已有数据与map的使用习惯不一致。所以不加反而是正确的设计。4.4 插入后的颜色调整和旋转要不要暴露红黑树插入后要处理双红节点、要变色、要旋转这些逻辑对上层完全不可见。封装时最重要的原则之一就是旋转、变色这些“内部器官”绝对不能成为公开接口。map的用户不需要知道LL型旋转还是RR型旋转他只需要知道插入后树依然是平衡的。在一个完整封装里Insert的流程大致是查找插入位置 → 新建红色节点 → 链接到父节点 → 循环处理颜色冲突 → 必要时旋转 → 最后根节点置黑。这一整套动作都在RBTree内部完成对外只暴露“插入成功或失败”的结果。我第一次自己实现的时候把旋转函数写成 public结果上层到处乱调后来才发现旋转是维持不变量红黑性质的手段不是容器功能必须私有化。5. 封装之外的边界问题深浅拷贝、比较器和分配器很多手写红黑树的人会把注意力放在插入删除的旋转逻辑上却忽略了封装类作为“类类型”最基本的三大件析构、拷贝构造、赋值重载。这三个函数如果写不好整个封装就是纸糊的。5.1 一棵树的“三大件”必须自定义不能依赖浅拷贝红黑树的节点是new出来的内部指针关系复杂。如果让编译器默认生成拷贝构造只是把根节点指针复制一份两个对象会指向同一棵树的节点。任何一个对象析构时把节点释放掉另一个对象就变成悬空指针后续访问必然崩溃。正确的做法是在RBTree内部把复制逻辑写完整// 析构后序遍历释放所有节点 void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } // 拷贝递归复制每个节点 Node* Copy(Node* root) { if (root nullptr) return nullptr; Node* newRoot new Node(root-_data); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); if (newRoot-_left) newRoot-_left-_parent newRoot; if (newRoot-_right) newRoot-_right-_parent newRoot; return newRoot; } // 赋值现代 C 用 copy-and-swap RBTree operator(RBTree other) { swap(_root, other._root); return *this; }这里有个经验拷贝时不要忘了重新设置子节点的 parent 指针。我写过一版代码第一次拷贝后遍历没问题但调用operator时向上回溯就找不到父节点全乱了。红黑树的每个节点都有 parent 字段复制时必须让新树的 parent 关系和原树一致。5.2 比较器参与排序的传递路径红黑树封装中的Compare不能写死。如果代码里直接写key curKey那树就只能支持升序用户想自定义排序规则比如按字符串长度就完全办不到。正确的做法是把比较器作为模板参数传入内部统一通过_comp(a, b)判断template class K, class T, class KeyOfT, class Compare lessK class RBTree { Compare _comp; // 比较器对象 bool Insert(const T data) { const K key kot(data); if (_comp(key, curKey)) // key curKey cur cur-_left; else if (_comp(curKey, key)) // curKey key cur cur-_right; else return false; } };这样map和set都暴露出第三个模板参数用户使用mapstring, int, StringLengthLess就能把排序规则传进去。这个设计本质上是依赖注入把“算法如何比较两个 key”这个策略从树结构里剥离出来让树结构只负责平衡。提一个常见坑自定义比较器必须满足严格弱排序strict weak ordering即_comp(a, a)必须返回 false。如果相等元素之间比较也返回 true插入和查找会进入死循环而且很难排查。我自己曾经写过一个忽略大小写的字符串比较器漏掉了“大小写不同但内容相同”的判定结果红黑树里同时插入两个等价值查找时表现诡异。5.3 分配器的透传逻辑最后提一下 allocator。红黑树的节点创建不是直接new Node而是通过 allocator 分配内存否则无法支持用户自定义内存池。STL 的模式是_Rb_tree持有allocator_type在get_node()里调用_M_get_node()在put_node()里释放内存。封装成泛型容器时这个 allocator 参数也要透传给底层树不能自己内部藏着。在实际项目中除非有明确的内存池需求绝大多数场景使用默认的std::allocator就足够了。学到这一层主要是为了理解 STL 的扩展性所有“可配置策略”都是通过模板参数传递而不是通过硬编码或继承重写。6. 自己动手封装时最容易踩的坑我把整个封装学习过程里遇到的坑整理了一下前三个几乎是每个手写者都会踩的最后两个是我看别人代码时经常发现的隐患。6.1 Search 和 Insert 的查找分支不一致手写Insert时很容易复制Find的代码改一改但Find只需要返回 bool 或迭代器Insert却需要记住 parent 节点。如果Insert的循环里忘了更新 parent或者更新时机不对插入后新节点的 parent 是错的后面的旋转直接崩。我在调试时最有效的方法不是单步跟踪而是插入一组随机数据后写一个IsValidRBTree()校验函数分别检查根节点是否为黑、红色节点是否有红色孩子、每条路径黑色节点数是否相同、中序遍历是否有序。把这个校验函数封装成公共接口所有测试用例都跑一遍大多数问题都能快速定位。6.2 迭代器失效的理解不能套用顺序容器顺序容器里插入元素可能导致内存搬移迭代器失效。但红黑树的插入不会移动已有节点它只是调整指针方向所以已获取的迭代器指向的节点依然存在数据也不变。这个特性让map和set在频繁插入删除时比vector稳定得多。但要注意如果删除某个节点指向该节点的迭代器必然失效因为节点内存被释放了。这和链表的删除行为一致。封装类如果要提供 Erase返回值是下个迭代器还是 void需要在设计时就确定。STL 的map::erase(iterator)在 C11 后返回下一个迭代器这对循环删除非常友好例如for (auto it m.begin(); it ! m.end();) { if (需要删除) it m.erase(it); else it; }6.3 header 节点和 end 迭代器的关系简化版红黑树可以用nullptr表示 end但 STL 真正的实现里还有一个 header 节点。它不存储真实数据专门用来让end()能安全地--回退到最后一个真实节点也就是让迭代器满足双向遍历的 closed-range 语义。如果自己封装时不用 headerend()返回 nullptr那么--end()就是未定义行为每次用reverse_iterator之前都要小心判断。我最初图省事选择 nullptr后面写反向迭代器时发现很不顺手又回头补了 header 节点。建议直接按 STL 的 header 方案来虽然初始化复杂一点但后续实现rbegin、rend会轻松很多。6.4 不要把 map 的 Value 写成 pairK, V 而不是 pairconst K, V如果一个 key 在插入后还能被修改整个二叉搜索树的排序性质就毁了。封装中必须用pairconst K, V作为节点数据类型同时给map的迭代器返回pairconst K, V。如果你在练习时偷懒写pairK, V虽然大多数场景看起来能运行但只要用户通过迭代器修改 first 字段树的搜索逻辑就不可信了。6.5 复用时的“最小接口”原则封装红黑树的目的是复用但复用时也要克制不要把所有内部方法都设成public。我踩过的一个典型问题是把LeftRotate和RightRotate设为 public后来测试代码在插入过程中手动调了一次旋转把一个原本合法的红黑树旋转成了违反性质的树排查了很久才发现不是红黑树算法的错而是“正确的不变量”被外部破坏了。好的封装应该只暴露以下接口Insert、Erase、Find、Begin、End、Size、Empty以及用于调试的校验函数。旋转、变色、提取 key、递归销毁全部作为内部实现细节。最后说点个人体会。把map和set的封装完整实现一遍收获最大的不是红黑树的旋转细节而是“参数化隔离变化”的设计能力树的结构是稳定的节点数据是变化的提取规则是变化的比较策略是变化的。STL 通过五个模板参数把稳定和变化衔接在一起而map和set只是这棵模板树面向用户的两种外观。理解了这一层再回头看unordered_map的哈希桶封装或者看其他语言里的关联容器的设计很多思路都是相通的。建议有空也去试试自己写一版最小红黑树模板然后把它分别适配成map和set踩过那几个坑之后你对“封装”二字的理解会完全不一样。