红黑树写完别急着把它丢一边真正的进阶题目是怎么用同一棵自底向上改出来的红黑树把标准库里的map和set同时造出来。这篇就是传说中的“28.C进阶map和set封装”核心围绕三点insert的返回值设计、迭代器的中序遍历封装、map的operator[]。这几个点一旦打通你对模板复用、仿函数、迭代器适配的理解会直接上一个台阶。这不是一篇讲map和set怎么用的入门笔记而是实打实的源码设计思路。适合已经学过红黑树、想把容器底层看透的读者也适合准备面试时被问到“map底层是什么”“operator[]为什么能插入”这类问题的同学。跟着文中的代码走一遍你会看到STL里那种“一棵树服务两个容器”的精妙设计是怎么落地的。1. 为什么map和set能共用一个底层红黑树很多人第一次接触封装map和set时最直观的想法是map是KV结构set是K结构底层红黑树存的节点都不一样那肯定得写两棵树。但STL里的真实做法恰恰相反底层只有一棵泛型红黑树节点保存类型完全由模板参数T决定。map实例化时T存pairconst K, Vset实例化时T直接存K。1.1 STL源码里的核心设计在SGI STL里红黑树类叫_Rb_tree它有三个关键模板参数Key、Value、KeyOfValue。Key是键类型Value是节点保存的数据类型KeyOfValue是一个函数对象负责从Value里取出Key。map传进来的是“从pair里取first”set传进来的是“直接返回自身”。这样设计的好处非常明显插入、查找、删除的时候树不关心你存的具体是什么它只关心“怎么从数据里拿到用于比较的键”。这个比较键的过程被抽出来之后旋转和变色逻辑就完全不需要写第二遍。你要做的只是给map和set各写一个薄薄的封装层内部塞一个红黑树对象然后把接口暴露出去。1.2 关键点为什么要用仿函数而不是函数指针有人可能会问从T里取键这件事直接传一个函数指针不行吗可以但性能差。仿函数是在编译期就确定的类型编译器可以内联它每次比较时不会有函数调用的额外开销。而函数指针是在运行期通过地址跳转的虽然在红黑树这种比较次数不算极端的场景下差别也许不大但作为底层泛型组件能压的内联一定要压。另外仿函数还可以携带状态虽然这里用不到但template参数的方式让整个红黑树成为一个“半通用组件”以后如果你想再封一个multimap或者multiset只需要调整封装层和比较逻辑红黑树本体一行都不用动。1.3 一棵树怎么服务两个容器红黑树本体只需要关心“节点里存的是T类型的数据”T可以是任何东西。map和set的区别仅仅在于map的RBTreeK, pairK, V, MapKeyOfTset的RBTreeK, K, SetKeyOfT代码里看起来只是模板参数不同但最终呈现出来的行为完全不同。map的insert返回pairiterator, bool迭代器解引用拿到pair然后通过first/second访问键值set的insert返回值同样签名但迭代器解引用拿到的是K本身。这个抽象过程很像一条分拣流水线流水线不在乎包裹里装的是衣服还是书只关心快递单号能不能被扫描枪识别。MapKeyOfT和SetKeyOfT就是两把不同的扫描枪。2. 核心改造把KV红黑树变成半通用红黑树前面我们可能写过一版红黑树节点里直接存pairK, V比较的时候直接比较kv.first。现在要把它改造成通吃的版本实际上只需要动三处节点模板、模板参数、比较逻辑。2.1 节点模板调整原来的节点我猜长这样templateclass K, class V struct RBTreeNode { RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; pairK, V _kv; Color _col; };改成通用版本templateclass T struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; T _data; Color _col; RBTreeNode(const T data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} };T是什么完全由外部决定。set传入Kmap传入pair。这里注意一个细节map的K也就是pair.first应该用const K修饰不然迭代器会允许外部修改键红黑树的有序性就毁了。STL里map的键也是const的set的键同样不能改。2.2 仿函数怎么提取键红黑树比较的时候需要键但T可以是任意类型那就交给仿函数处理。这里给出两个典型的仿函数// 给map用从pair中取出first作为键 templateclass K, class V struct MapKeyOfT { const K operator()(const pairK, V kv) const { return kv.first; } }; // 给set用键就是数据本身 templateclass K struct SetKeyOfT { const K operator()(const K key) const { return key; } };这两个仿函数都提供一个重载了operator()的类红黑树内部只要拿到这个仿函数对象调用keyOf(data)就能得到const K。红黑树比较的时候只用这个键来比较完全不关心data里还有没有其他信息。我在最初写封装的时候踩过一个坑在MapKeyOfT里返回的是K不是const K结果每次比较都会发生一次拷贝性能看着不舒服更重要的是在泛型场景下可能触发奇怪的编译错误。规范写法是返回const引用因为红黑树内部不会修改键也没有理由拷贝一份。2.3 比较逻辑被抽出来之后旋转和变色完全不用动改造之前红黑树查找插入位置时是这么写的if (cur-_kv.first kv.first)这是写死比较first的。现在改成KeyOfT kot; if (kot(cur-_data) kot(data))但这里有个坑如果每次比较都重新构造一个KeyOfT对象理论上没问题因为仿函数没有状态构造一个实例几乎零成本。不过更优雅的做法是在红黑树类里直接定义一个成员变量_KeyOfT _kot然后用它来比较。这样语义更清晰后续如果要给仿函数传参也更方便。旋转和变色关心的只是“哪个节点是左孩子”“哪个节点是右孩子”以及节点的颜色跟data里存什么没关系。所以旋转函数、变色函数、红黑树性质维护逻辑把比较部分抽走之后是百分之百原样保留的。3. insert从插入到去重一气呵成在封装时insert的返回值是一个特别关键的设计点。STL里map和set的insert都返回pairiterator, bool第一个参数指向“新插入的节点”或者“已经存在的那个节点”第二个参数是一个bool表示本次是否真的插入了。3.1 insert返回值为什么必须是pair如果你只是实现一个普通的红黑树insert返回Node*就够了。但map的operator[]需要知道一件事如果键不存在我要先插入它再返回值的引用如果键已经存在我直接返回现有值的引用。没有bool标志调用方就得自己再find一次白白多一次O(logN)查找。所以insert返回pairiterator, bool一次操作把“插没插进去”和“节点在哪里”都带回来。这个设计是后面所有高级用法的基石。3.2 完整的insert实现框架下面是一棵半通用红黑树的insert核心逻辑注意比较的地方已经全部换成了KeyOfTtemplateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef RBTreeIteratorT, T, T* iterator; pairiterator, bool Insert(const T data) { KeyOfT kot; if (_root nullptr) { _root new Node(data); _root-_col BLACK; return make_pair(iterator(_root), true); } 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), false); } } cur new Node(data); cur-_col RED; Node* newNode cur; if (kot(parent-_data) kot(data)) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 红黑树调整变色旋转 // ... 此处省略调色和旋转代码核心逻辑与标准红黑树完全一致 _root-_col BLACK; return make_pair(iterator(newNode), true); } private: Node* _root nullptr; KeyOfT _kot; };注意我标注“省略调色和旋转”的位置。这块不是不重要而是因为文中重点在“封装”旋转代码在前面实现红黑树时已经写好了移到这个类里时只需要把“比较键”的地方替换成kot()即可结构上一行都不用改。3.3 去重是怎么实现的map和set的key都是唯一的这个去重不是set自己额外做的而是红黑树Insert逻辑里的“键相等就返回false”天然带来的。在STL的set里同样的key没办法插入两次在map里同样first的pair也插不进去只会让迭代器指向已存在的那个节点。这也是为什么multimap和multiset内部不能用同一棵红黑树直接改的原因它们用的是另一个版本插入时遇到相同键会走“右子树方向”继续找位置保证相同键的多个值都能存进去。封装的思路到这里就已经开始往额外里延伸了。3.4 关于调整逻辑的提示红黑树的调整无非分三种情况叔叔节点是红色、叔叔节点是黑色且自己在内侧、叔叔节点是黑色且自己在外侧。无论哪种都只跟“cur、parent、grandfather、uncle”的位置和颜色有关不涉及具体数据内容。所以哪怕你的红黑树之前是写死了pair的现在只需要把键提取方式替换成kot其他逻辑原样粘贴。如果调整代码是你自己写的建议在替换后先用明显的用例做一次红黑树性质校验后面第6部分我会给出具体的验证方法。4. 迭代器让红黑树能被范围for遍历容器封装出来后如果没有迭代器连范围for都用不了那封装的意义就少了一大半。红黑树迭代器和其他容器迭代器最大不同在于它不是像vector那样用数组下标就能直接推进的它要顺着中序遍历的规则一棵树一棵树地走。4.1 迭代器类的骨架红黑树的迭代器本质上就是“包了一个节点指针”的对象但通过一个类把指针的运算进行了重载。templateclass 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*() { return _node-_data; } Ptr operator-() { return (_node-_data); } bool operator!(const Self s) const { return _node ! s._node; } // 前置 Self operator(); // 前置-- Self operator--(); };模板参数里的Ref和Ptr是为了兼容const迭代器。普通迭代器实例化时Ref是TPtr是T*const迭代器实例化时Ref是const TPtr是const T*。这样一套代码就能同时支持iterator和const_iterator不需要为const版本再写一遍迭代器类。4.2 operator 的中序遍历规则这是整个迭代器封装里最考验思维的一环。红黑树作为搜索树中序遍历的结果是“从小到大有序的”。迭代器时要去的地方就是当前节点的中序后继。分两种情况第一种当前节点的右子树不为空。那么下一个节点就是右子树的最左节点。因为中序遍历的顺序是“左子树、根、右子树”当根已经访问完后下一站就是右子树部分而右子树里最先访问的是它的左子树的最左节点。第二种右子树为空。这时候要向上走一直走到某个节点它是其父亲的左孩子为止这个父亲就是后继节点。如果走到根节点都找不到这样的节点说明已经遍历到end了返回nullptr的迭代器。核心代码Self operator() { if (_node-_right) { Node* cur _node-_right; while (cur-_left) { cur cur-_left; } _node cur; } else { Node* cur _node; Node* parent cur-_parent; while (parent parent-_right cur) { cur parent; parent cur-_parent; } _node parent; } return *this; }你可以拿一棵简单的搜索树在纸上跑一遍根是5左子树是3右子树是8。当迭代器指向3时右子树为空往上走3是5的左孩子于是下一个节点是55的右子树存在走到8的最左节点也就是8本身8再时右子树为空往上走到根发现parent为空迭代器变成end。4.3 begin和end怎么接上红黑树容器的begin应该指向树中最小的节点也就是最左节点。end用nullptr就可以迭代器走到最后再时operator里的循环会返回nullptr这就和end对齐了。iterator Begin() { Node* cur _root; while (cur cur-_left) { cur cur-_left; } return iterator(cur); } iterator End() { return iterator(nullptr); }这样Set和Map内部只要把这个Begin和End暴露成begin/end用户就能直接范围for了。打印出来的结果天然就是有序序列这也是验证红黑树是否正常的一个直观手段。4.4 const迭代器和键不可改的问题map里的pairconst K, V本身就保证了键不能通过迭代器修改。set里没有const修饰但标准库的set迭代器实际是const_iterator迭代器指向的数据不允许被修改。自己实现时可以让Set暴露const迭代器或者在Set的迭代器接口上做一层包装避免用户通过迭代器把树里的键改了。提示map和set的键一旦插入绝对不能修改否则整棵树的搜索顺序就乱了find会失灵。底层红黑树不用关心这件事但封装层必须把这个限制暴露出来。5. map的operator[] 是怎么实现的map的[]是STL里最方便的语法糖之一但很多人不知道它其实不是简单查找。它的完整语义是如果键存在返回对应值的引用如果键不存在先插入一个默认值再返回这个默认值的引用。这个行为不是单独实现的而是直接复用了insert的pairiterator, bool返回值。5.1 operator[] 的标准实现V operator[](const K key) { pairiterator, bool ret _t.Insert(make_pair(key, V())); return ret.first-second; }这里的关键在于make_pair(key, V())。如果key已经在树里Insert会找到它并返回falseret.first指向的就是已有的节点。如果key不存在Insert会把这个新pair插入树中ret.first指向新节点。无论哪种情况ret.first-second都是我们想要的V的引用。整个过程只需要一次红黑树查找效率很高。STL源码里的写法是调用了insert(value_type(key, mapped_type()))和这里make_pair的语义一致。V()生成一个默认构造的值如果V是int就是0是string就是空串是一个类就调用默认构造函数。这样“访问不存在元素”这个看似非法操作的场景被[]变成了“创建并初始化”。5.2 [] 的两种语义读取m[key]当key存在时返回value不会插入任何东西。写入m[key] value当key不存在时先插入默认值再赋值当key存在时直接覆盖value。这个双重语义让map的代码非常简洁但也容易产生隐蔽的性能问题。如果你只是想做查找千万不要写成if (m[key])因为key不存在时它会插入一个默认键改变了容器内容。查存在性应该用find或count。5.3 经典场景统计字符出现次数用[]统计一个字符串中每个字符出现的次数是最能展示这个语法糖价值的用法mapchar, int countMap; string str hello world; for (auto ch : str) { countMap[ch]; } for (auto kv : countMap) { cout kv.first : kv.second endl; }第一次遇到某个字符时countMap[ch]会插入一个(char, 0)然后让它变成1。后面再遇到相同字符[]返回已有计数再。整个过程逻辑简单到让人感觉像是map天生就会统计次数一样但底层机制是上面那套insert返回值设计在支撑。5.4 注意set没有[]运算符set的键就是值值就是键不存在“按键取值”这种语义。虽然set也返回pairiterator, bool但它不需要operator[]也没有必要提供。很多刚学的人会下意识给set也加一个[]实际上完全没有意义因为即使实现了也跟find没有本质区别。另外const map也不能调用[]因为[]可能修改树的内容const限定下只能调用find或at。C11新增的at方法是一个只读查找接口如果key不存在会抛out_of_range异常适合那种“只查不改”的场景。6. 常见问题与调试技巧封装过程中的坑比想象中多很多问题不看报错完全摸不着头脑。下面这些是我实际写完并调试通过后总结出来的值得保存。6.1 编译不过模板实例化时找不到first这通常意味着仿函数没写对或者红黑树内部还在用“比较某个具体成员”的旧逻辑。排查顺序确认RBTree的模板参数是K, T, KeyOfT而不是直接把T写成pair。确认所有比较操作都走的是KeyOfT没有残留直接比较data成员的代码。确认MapKeyOfT的operator()参数类型是const pairK, V返回值是const K。确认SetKeyOfT的operator()参数类型是const K返回值是const K。模板代码在“没被实例化”时不报错一旦map或set真正调用Insert所有错误都会一股脑喷出来。建议先从set开始调试因为它比较简单调通后再去看map。6.2 迭代器出现死循环或跳错节点大部分情况都是右子树为空时向上走的条件写错了。正确条件是只要当前节点是父亲的右孩子就继续向上走当当前节点是父亲的左孩子时停下来该父亲就是后继节点。我见过比较常见的错误版本是死循环在 while(parent parent-_right cur) 中。原因往往是向上走时没有正确把cur更新成parent导致parent永远指向同一个节点。调试这个可以通过在纸上画一棵三四个节点的树然后用打印语句跟踪每一步的cur和parent很快就能看出问题。6.3 打印出来不是有序如果范围for打印出来的结果不是从小到大优先怀疑两方面一是红黑树的InOrder顺序不对根和左右子树访问顺序乱了二是插入时的比较条件写反了导致树的结构变成了降序或者乱序。验证方法很简单写一个中序遍历检查打印结果是否严格非降序。如果是非降序说明树结构没问题如果不是回到Insert的查找位置部分检查kot(cur-_data) kot(data)的方向是否正确。6.4 如何验证红黑树确实平衡封装完成后红黑树的自平衡性质需要验证一下。随机插入大量数据后检查从根节点到每个叶子节点的黑色节点数相同且没有连续的红色节点。这个问题一般会在调整逻辑不完善时出现。更简单的快照式检查int Height(Node* root) { if (root nullptr) return 0; return max(Height(root-_left), Height(root-_right)) 1; }插入1万个数后理想高度应该在2 * log2(n1)附近。如果高度明显超出这个范围比如10000个数高度长到几千说明有节点失衡了红黑树的旋转或者变色逻辑有问题。这时候再回过头去检查insert里的调色和旋转分支。6.5 内存管理红黑树使用new动态分配节点析构时必须释放所有节点。树结构不像链表那样可以循环中解引用next递归析构更自然。但红黑树可能很深工程上更稳妥的写法是用后序遍历栈模拟的方式避免递归深度过大。我给自己写的容器界的习惯是提供一个私有Destroy函数在析构函数里调用它统一递归销毁所有节点。测试时跑一下内存泄漏检查工具确保每个new都有对应的delete。6.6 顺手验证一下map和set的行为封装完建议立刻跑这几个基础测试set中插入重复值集合大小不增长。map中插入相同键的pair不会新增节点。map的[]可以读取已有值也可以插入新值。范围for打印map键有序。通过迭代器修改map的value再重新遍历键不变、值变了。尝试通过迭代器修改map的key或set的值编译时会有报错或者被const迭代器挡住。这一套跑完基本可以确定封装版本是能用的。实际用起来至少差不离了。这个系列写到第28篇我从红黑树的结构到map和set的整体封装都手动写过一遍最大的感受是模板复用不是为了炫技而是为了少写重复代码。仿函数抽取出键的比较逻辑、迭代器封装底层指针的移动规则、insert返回值服务于operator[]每一步都体现出容器设计者在“通用性”和“易用性”之间的取舍。如果你也想彻底搞懂STL我强烈建议动手写一遍这个过程。不需要把代码写得像标准库那样极致只要亲手把红黑树改造成半通用结构再把map和set的壳一层层套上去你再看那些“map底层是什么”“[]为什么能自动插入”“迭代器怎么实现”的问题都会有一种豁然开朗的踏实感。踩过的坑会比任何教程都记得更牢。