很多人学 STL 的时候基本停留在“会用”层面std::set能去重、能排序插入查找都是O(log n)。但一旦追问“它内部到底怎么实现的”“为什么迭代器 之后就能按顺序走”“为什么insert返回的是一个 pair”大多数人答不上来。我也经历过这个阶段。后来花了大把时间泡源码把set从头到尾过了一遍才算是真正理解了这个容器的底气在哪里。这篇博文是“STL 源码阅读”系列的一篇专门讲set。我不会把源码逐行贴出来讲解那没意思也没法读。我尽量按我自己的阅读路径走先搞清楚set的壳是什么、底下的肉是什么再去抠红黑树这个核心最后聊聊迭代器、插入删除、以及那些只有看了源码才懂的坑。内容会比较长但你真读进去收获也是持续的。1. 阅读前的准备set 的壳与里子1.1 先搞清楚 set 到底是什么std::set在标准里的定义很简单一个关联式容器存放唯一的、有序的元素。它对元素的要求是“可比较”默认用std::less做排序准则。从使用者的角度看set就是一个“自动排序 自动去重”的集合。但读源码时会发现set本身根本没有自己的数据存储逻辑。它所有的底层功能几乎全部转发给一个叫_Rb_tree的类模板。set只是给_Rb_tree套了一层壳把对外接口裁剪成适合“集合”语义的样子。所以读set的源码本质上读的是两件事set这个类模板怎么封装_Rb_tree_Rb_tree这个红黑树容器怎么实现插入、删除、查找、迭代这两层都看完才算真正读懂了set。1.2 选哪份源码来读目前主流的 STL 实现有好几份GCC 自带的 libstdc、LLVM 的 libc、MSVC 的 STL。我推荐从 GCC 的 libstdc 开始读。原因很直接它的_Rb_tree实现相对经典结构清晰且 STL 源码剖析那本书主要参考的就是 SGI STL和 libstdc 一脉相承网上讨论资源多遇到不明白的地方容易找到资料。libc 的实现也不错但它的代码风格更“现代化”用了不少宏和模板技巧新手读起来门槛偏高。MSVC 的实现细节和 GCC 有不少差异如果不是在 Windows 下开发优先级放后面。# GCC 环境下可以快速找到头文件位置以 Ubuntu 为例 g -print-file-nameinclude # 通常在 /usr/include/c/xx 下面 # set 的头文件是 bits/stl_set.h # _Rb_tree 的头文件是 bits/stl_tree.h我个人建议打开源码时同时开两个文件stl_set.h和stl_tree.h。前者是壳后者是核心。读的时候从stl_set.h入手看到它调用了_Rb_tree的哪个方法就跳过去看那个方法的实现。提示不要试图从头到尾一行行读那样会很快失去耐心。先画出“set 的公开接口 - 对应 _Rb_tree 的底层操作”这个映射表再逐个击破。1.3 set 的接口到底转发给了谁打开stl_set.h一眼扫过去能看到set类内部有一个类型别名typedef _Rb_treekey_type, value_type, _Identityvalue_type, key_compare, _Alloc _Rep_type; _Rep_type _M_t;set的所有公开操作基本上都是直接调_M_t的对应方法。比如begin()-_M_t.begin()insert(x)-_M_t._M_insert_unique(x)erase(pos)-_M_t.erase(pos)find(x)-_M_t.find(x)注意_M_insert_unique这个名字它表示“唯一插入”也就是如果元素已经存在就不插入。这正好对应set的去重语义。如果哪天你去看multiset会发现它的底层调用变成了_M_insert_equal——允许重复插入。这个设计其实就是经典的设计模式Bridge桥接模式。set是抽象接口_Rb_tree是实现体。两者可以各自独立演化。2. 红黑树结构set 的灵魂所在2.1 为什么 set 选择了红黑树而不是别的结构这是读源码之前必须想明白的问题。set需要支持有序遍历、快速查找、插入删除同时不能太消耗内存。候选方案有哈希表、AVL 树、跳表、B 树。哈希表查找 O(1)但无序做不到“按顺序遍历”。C11 里因此才有了unordered_set它和set是两套东西。AVL 树平衡性比红黑树更严格查找略快但插入删除时旋转频繁代价高。跳表实现简单但内存开销大缓存友好性差。B 树适合磁盘型数据库内存容器里玩不转。红黑树是个折中它不追求“完全平衡”而是保证“最长路径不超过最短路径的两倍”。所以它的树高控制在2log(n)级别插入删除时的重平衡代价也远低于 AVL。对set这种读写混合、还要求有序遍历的场景红黑树是面试官最爱问、也是工程上最稳的选择。2.2 从源码看红黑树的节点设计_Rb_tree的节点类型长这样简化版struct _Rb_tree_node_base { _Rb_tree_color _M_color; // 节点颜色红或黑 _Rb_tree_node_base* _M_parent; // 父节点 _Rb_tree_node_base* _M_left; // 左孩子 _Rb_tree_node_base* _M_right; // 右孩子 }; templatetypename _Val struct _Rb_tree_node : public _Rb_tree_node_base { _Val _M_value_field; // 实际存储的元素 };这里有个非常关键的设计_Rb_tree_node_base不存值只存树结构信息。所有红黑树相关的旋转、变色操作全部基于_Rb_tree_node_base完成完全不关心节点里存的是什么类型。只有到真正需要读写_Val时才通过继承下来的_Rb_tree_node访问_M_value_field。这种做法叫“模板分离”。它带来的好处非常明显树结构操作的代码只编译一次不管你setint还是setstring旋转逻辑的代码是同一份大大降低了二进制体积。2.3 关键点header 哨兵节点_Rb_tree里有一颗永远存在的空节点叫header。它不存储实际数据但它的_M_left永远指向树的最左节点_M_right永远指向树的最右节点_M_parent指向根节点。这个设计是 STL 容器迭代器合法性的基石。为什么要这样begin()要返回“最小元素”的迭代器。如果直接找根节点一路向左那每次都要走while (x-_M_left) x x-_M_left;。有了 header直接返回header-_M_left的迭代器就行O(1)。rbegin()同理返回header-_M_right。当树为空时header的_M_left和_M_right都指向 header 自己。这样迭代器永远有“哨兵”可指不会出现空指针。代码里对应的是templatetypename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc typename _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::iterator _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::begin() { return iterator(_M_begin()); // _M_begin() 内部返回 header-_M_left }2.4 红黑树的平衡规则回顾读旋转代码之前需要把红黑树的五条规则刻在脑子里每个节点非红即黑。根节点是黑色。每个叶子节点NIL是黑色。如果一个节点是红色则它的两个子节点必须是黑色不能有连续的红色节点。从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这五条规则保证了路径上黑色节点的数量一致从而限制了树的高度。后面的_Rb_tree_insert_and_rebalance和_Rb_tree_erase_and_rebalance两个函数本质就是“插入/删除后通过变色和旋转让树重新满足这五条规则”。3. 核心操作源码走读插入、删除、查找3.1 插入_M_insert_unique 是怎么工作的set的insert通过_M_insert_unique实现。当我们调用s.insert(5)时内部到底走了几步第一步从根节点开始按比较器查找插入位置同时记录路径上遇到的最后一个节点。这部分实现核心可以用伪代码表示templatetypename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc pairtypename _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::iterator, bool _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc:: _M_insert_unique(const _Val __v) { // 从 header 开始_M_begin() 返回根节点 _Link_type __x _M_begin(); _Link_type __y _M_end(); // header bool __comp true; while (__x ! 0) { __y __x; __comp _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); __x __comp ? _S_left(__x) : _S_right(__x); } // 找到插入点后再走一遍查找确认是否已经存在相同 key iterator __j iterator(__y); if (__comp) { if (__j begin()) return _M_insert_(__x, __y, __v); else --__j; } if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) return _M_insert_(__x, __y, __v); // 已经存在返回已有元素的迭代器和 false return pairiterator, bool(__j, false); }这里有两个值得注意的点第一次循环只是定位到了插入位置但还不能确定这个 key 是不是已经存在。所以紧接着用--__j往前回退一个节点再用比较器验证“前一个元素是否小于待插入元素”。如果前一个元素不小于说明树里已经有相同的 key直接返回false。最终真正插入数据的是_M_insert_它负责分配节点、设置父子关系然后调用_Rb_tree_insert_and_rebalance做红黑树平衡修复。3.2 再看一眼M_insert和原地构造_M_insert_做的事情如下申请一块_Rb_tree_node内存通过分配器_M_get_node在节点内存上构造元素construct把节点挂到树中合适的位置调用_Rb_tree_insert_and_rebalance调整颜色和旋转更新 header 指针如果插入的是最小或最大节点header的_M_left或_M_right也要跟着变实现里有个细节是在 C11 之后insert有两个版本一个接收 const 左值引用一个接收右值引用。后者在节点构造时会调用std::move避免了不必要的拷贝。如果你往setstring里插一个临时字符串用s.emplace(hello)或者s.insert(std::move(str))能省掉一次字符串拷贝。这个优化在源码级是看得到的用法上也有感知。3.3 删除erase 的三种形态set::erase有三个重载erase(iterator pos)删除指定位置的元素erase(const key_type x)删除指定 key 的元素返回删除个数set 里要么 0 要么 1erase(iterator first, iterator last)删除一个区间底层调用_Rb_tree::erase之后真正干活的是_Rb_tree_erase_and_rebalance。这个函数是红黑树实现里最难啃的一块比插入要复杂。原因是删除一个黑色节点会破坏规则五黑色高度一致而删除红色节点则不用修复。所以删除后的修复逻辑要处理各种兄弟节点颜色、侄子节点颜色的组合情况。源码里面对应的是经典的“删除修复四情况”兄弟节点是红色先做一次旋转把红色兄弟转上去变成黑色兄弟的情况兄弟节点是黑色且兄弟的两个孩子都是黑色把兄弟变红问题向上传递兄弟节点是黑色左孩子是红色、右孩子是黑色或反过来先做局部旋转变成下面的情况兄弟节点是黑色且同侧孩子是红色做一次旋转把兄弟转上去变色结束修复这四类情况我在读源码的时候就对着 CLRS 的算法导论那章来读两边对照很快就能看通。单纯看代码很容易晕因为各种_M_parent、_M_left的指针换来换去没有一个指导框架在脑子里会越看越乱。3.4 查找find 为什么不走 key 的 operatorset的查找走的是比较器_Compare默认是std::less。find的逻辑就是从根节点开始按comp(key, node_key)的结果向左或向右走直到找到相等的元素或走到空节点。这里有个特别容易被误解的点set判断“相等”的标准不是而是“互不小于”。也就是说如果comp(a, b)和comp(b, a)都为假set就认为 a 和 b 等价。对于std::less这等价于a b和b a都为假也就是a b对于标准类型而言。但如果你传入一个自定义比较器比如按照abs(x)排序那么set会认为绝对值相同的数“相等”即使x本身不同。这是源码里一个非常实用的知识点后面讲坑的时候还会回到这。查找的复杂度是O(log n)这一点从源码结构上看得清清楚楚因为树高受红黑树约束每次比较都会排除掉一半的子树不可能有线性扫描。4. 迭代器与 const 正确性4.1 set 的迭代器为什么是 const_iterator在stl_set.h里能看到这样的定义typedef typename _Rep_type::const_iterator iterator; typedef typename _Rep_type::const_iterator const_iterator;注意set的iterator直接就是_Rb_tree的const_iterator。也就是说即使你拿到一个非 const 的setint的iterator你也只能读取元素不能修改。这是刻意为之。因为set的排序依据是元素的 key。如果你能通过迭代器直接修改元素那等于可以把树里某个节点的值改掉从而破坏红黑树的有序性。后续的查找和遍历都会出问题。代价就是你不能通过迭代器对set的元素做原地赋值。如果想修改只能 erase 掉再 insert 新的。这个设计冲突在源码层面体现得非常直接_Rb_tree本身有iterator和const_iterator但set对外只暴露const_iterator。你可以在_Rb_tree层面自由读写但set把这扇门焊死了。4.2 迭代器 是怎么找到下一个节点的这是红黑树迭代器实现里最精彩的地方。_Rb_tree_iterator::operator的逻辑是_Self operator() { _Rb_tree_node_base* __y _M_node; if (__y-_M_right ! 0) { // 如果右子树非空下一个节点就是右子树的最左节点 __y __y-_M_right; while (__y-_M_left ! 0) __y __y-_M_left; } else { // 如果右子树为空往上找第一个“我是它左孩子”的祖先 __y __y-_M_parent; while (__y-_M_parent __y-_M_parent-_M_right __y) { __y __y-_M_parent; } __y __y-_M_parent; } _M_node __y; return *this; }一句话总结右孩子存在就去右子树的最左右孩子不存在就一路向上直到某个节点是其父节点的左孩子那么父节点就是下一个。思考题为什么要借助“右子树非空”而不是“当前节点有右孩子”因为红黑树里节点可能只有左孩子也可能只有右孩子还可能没有孩子。这个逻辑实际上是中序遍历的迭代版——树结构中序遍历的结果就是有序序列。begin()从最左节点出发一路走到最右节点end()就是 header。把中序遍历和红黑树结合起来理解迭代器设计就完全通了。类似的operator--是对称的逻辑左子树最右、或者向上找“我是它右孩子”的祖先。4.3 为什么 end() 不是空指针很多其他容器实现里end()可以理解成“最后一个元素的后一个位置”往往用空指针表示。红黑树特殊在它是双向迭代器需要支持--end()得到最后一个元素这个操作不能对空指针做。所以 header 哨兵节点在这个地方再次发挥作用。end()返回的迭代器指向 header而不是nullptr。--end()时进入operator--由于 header 的_M_right指向最右节点自然就能得到最大元素。哨兵节点的存在让红黑树迭代器始终有一个“非空但无意义”的节点可依赖这让边界情况的代码简单了很多。这也是 STL 源码设计里我认为最妙的地方之一。5. 源码阅读后记我知道的避坑指南与实用心得5.1 迭代器失效规则set 比 vector 友好得多关于set很多资料会提“插入和删除其他元素时迭代器不会失效”。源码读完这句话就好理解了插入新节点时树结构会旋转、变色但节点的内存地址不会搬移。已经存在的迭代器指向的还是同一个_Rb_tree_node数据没动过所以迭代器依然有效。删除某个节点时只有指向被删节点的迭代器失效。其他迭代器指向的节点内存还在指针关系虽然可能因旋转改变了但迭代器本身存的是节点指针不受影响。这和vector完全不同。vector插入导致扩容所有迭代器直接失效删除元素导致元素搬移后面的迭代器全部失效。set的节点是独立的堆内存搬移不存在的所以迭代器自然稳定。但注意一件事虽然迭代器不失效set的erase(key)返回值在 C11 之前是size_tC11 之后变成了返回size_type删除个数。而erase(pos)返回的是下一个迭代器。这两个别搞混。5.2 自定义比较器最容易踩的坑实战里我见过不少人给set传了个自定义比较器结果插入时行为诡异。最常见的问题有三个。第一个比较器不满足“严格弱序”strict weak ordering。比如比较器里用了那a b和b a可能同时成立导致set认为两个不相同的元素等价误吞数据。源码里_M_key_compare是直接用的它不会去校验你的比较器是否合法出了问题全是静默的。第二个比较器只比较部分字段。比如一个结构体有 id 和 name 两个字段比较器只比较 id那存进去之后即使 name 不同set也认为它们“相等”。find的时候只用 id 找name 跟没存一样。第三个比较器的结果依赖外部可变状态。这相当于让树的排序规则随时变化红黑树直接崩给你看。重要Comparator 必须满足严格弱序——comp(a, a)必须为 false且对于任意三个元素传递性必须成立。这是所有基于比较的 STL 容器set、map、priority_queue、sort的隐含契约。5.3 性能问题set 真的比 unordered_set 慢吗这个纠结了很多人的问题源码也能给出答案。set的查找是O(log n)unordered_set是平均O(1)。数据量很大时unordered_set确实通常更快。但真实工程里要考虑缓存、哈希冲突、内存碎片。set的节点分散在堆上遍历时缓存不友好unordered_set的 bucket 数组是连续的节点通常也集中分配遍历时缓存命中率更高。但反过来unordered_set的哈希函数如果设计得差冲突多到退化成链表性能会比set更糟糕。此外set能提供有序遍历这是unordered_set做不到的。如果你需要“按顺序输出”千万别拿unordered_set排序然后输出直接用set遍历更快。实测经验元素量小于几百个时set和unordered_set差距感知不到元素量几万到几十万时unordered_set可能快 2-3 倍但如果你频繁插入删除unordered_set的 rehash 开销反而可能让它慢下来。5.4 内存开销set 到底有多“重”每个set节点除了存元素本身还要存三个指针parent、left、right和一个颜色标记。在 64 位系统上这三个指针就是 24 字节颜色枚举至少 1 字节但会对齐到 4 字节。也就是说每存一个int4 字节树的元信息就要 28 字节左右。如果你有十万个int存到set里光树结构的开销就是 2.8MB 往上而原始数据本身才 0.4MB。这在嵌入式或内存敏感场景是不能忽视的。所以数据规模大且不需要有序性时优先考虑std::vector sort unique或std::unordered_set。set的正确使用场景是需要动态插入删除、同时要求有序遍历、且数据量可控。5.5 面试题视角set 源码常被问到的几个点读源码本身也是为面试做准备。我看过不少候选人聊到set就说“底层是红黑树”但深问一层就卡住。这里总结几个常见追问点set的插入返回类型是什么答pairiterator, boolbool 表示是否插入成功。set迭代器为什么不能修改元素答会破坏有序性所以实现上把迭代器直接定为 const_iterator。set和map的底层区别是什么答map的_Rb_tree存的是pairconst Key, T_KeyOfValue提取 pair 的 firstset存的是 Key 本身。lower_bound和upper_bound在set里怎么找的答基于红黑树的二分查找找到第一个不小于或大于key 的节点。红黑树插入后最多几次旋转答插入修复最多两次旋转删除修复最多三次旋转。这个结论源码里有体现。6. 实操试验从源码出发验证红黑树行为6.1 用调试器跟踪一次插入过程源码读再多不如动手跑一遍。我用一个简单的例子做过验证#include set #include iostream int main() { std::setint s; for (int x : {10, 5, 15, 3, 7, 12, 18}) { s.insert(x); } for (auto it s.begin(); it ! s.end(); it) { std::cout *it ; } std::cout \n; }用 gdb 打断点断在_Rb_tree_insert_and_rebalance每插入一个数看根节点颜色、左右孩子。你会亲眼看到“10 是黑根5 和 15 是红孩子插入 3 时触发左左旋转”这些教科书上的过程真实发生。我强烈建议自己也做一次这个实验。理由很简单红黑树的旋转和变色操作光看源码容易“看了就忘”但在调试器里一步步跟过之后就会发现它其实就是二叉搜索树的插入加上“修正颜色和结构”的后处理。6.2 验证 set 的严格弱序语义换个角度用自定义类型来验证前面说的比较器陷阱struct AbsCompare { bool operator()(int a, int b) const { return std::abs(a) std::abs(b); } }; int main() { std::setint, AbsCompare s; s.insert(3); s.insert(-3); // 第二次插入abs(-3) abs(3)set 认为已存在 std::cout s.size() \n; // 输出 1 }这个例子很好地演示了“等价”不等于“相等”的语义。3和-3在operator下不等但AbsCompare认为它们等价所以第二个插入被拒绝。实际开发中如果你依赖set::find的“精确匹配”语义这种自定义比较器就会带来隐蔽 bug。6.3 验证 erase 过程中的迭代器稳定性再做一个简单试验来判断“erase 一个节点其他迭代器是否有效”std::setint s {1, 2, 3, 4, 5}; auto it2 s.find(2); auto it4 s.find(4); s.erase(3); std::cout *it2 *it4 \n; // 正常输出 2 4我实测过很多次结果都是正常的。原因是erase(3)虽然触发了删除后的平衡修复但节点 2 和节点 4 的内存地址没有变化迭代器里保存的指针仍然有效。这个特性在多线程环境下做“无锁读 加锁写”时很有用但必须注意整体同步策略不能因为set迭代器稳定就掉以轻心。6.4 批量插入用 insert 的迭代器版本源码里还有一个容易被忽略的接口insert(InputIterator first, InputIterator last)。它内部会循环调_M_insert_unique。如果你手头有一个已经排好序的 vector 要转成 set可以传vector.begin()和vector.end()。这里有个细微差别_M_insert_unique在插入时如果待插入的值已经存在会直接跳过不会更新已有节点。所以批量插入时如果输入有重复重复项会被静默忽略这符合set语义。另一个小技巧是std::set::mergeC17 引入可以把另一个 set 的节点直接“嫁接”过来避免重新分配节点内存。如果你要把一个set合并到另一个优先考虑merge而不是循环 insert因为merge利用底层红黑树结构复杂度更有优势。6.5 性能测试set vs vectorsortunique我统计过一个简单实验随机生成 100 万个整数分别用set和vector sort unique做去重再测量耗时和峰值内存。结果符合源码层面的推断set单元素插入每个节点独立分配内存随机访问模式导致缓存命中差总体耗时偏高。vector是连续内存sort是原地排序去重后直接uniqueerase整体比set快不少内存也更紧凑。但反过来如果你需要“边插入边查询”“随时删除”vector的优势就没了。这个实验想说明的是源码结构决定了容器性能特征读源码的意义就是让你在看到接口的第一眼就对它的性能画像有直观判断而不是跑一堆 benchmark 才恍然大悟。7. 最后分享一点读完源码后的体会整套set源码读下来我最强烈的感受是STL 的代码不是写给编译器看的是写给读懂它的人看的。_Rb_tree把树的通用操作抽象到基类set把接口收窄到集合语义迭代器用哨兵节点免去边界判断每个设计都有它的历史背景和权衡逻辑。读之前我以为set的源码就是一棵“加了颜色的二叉搜索树”读完之后才发现真正复杂的是各种边界条件和语义约定等价和相等不是一回事、end()不是空指针、插入返回值为什么是 pair、为什么迭代器不能修改元素。这些东西不读源码光靠经验是永远踩不全的。如果这篇能给你一点启发建议自己打开stl_tree.h跟着走一遍。从_M_insert_unique进从_Rb_tree_erase_and_rebalance出中间卡住了就回去翻算法导论的红黑树章节。那本书的图配上 GCC 的源码是我见过最有效的组合。等你读通了再去看map、multiset、multimap基本就是换个壳的事。 
长河君 · 2026/10/14 20:05:22 · 阅读 1.2k STL源码阅读：set底层红黑树实现与迭代器机制
很多人学 STL 的时候基本停留在“会用”层面std::set能去重、能排序插入查找都是O(log n)。但一旦追问“它内部到底怎么实现的”“为什么迭代器 之后就能按顺序走”“为什么insert返回的是一个 pair”大多数人答不上来。我也经历过这个阶段。后来花了大把时间泡源码把set从头到尾过了一遍才算是真正理解了这个容器的底气在哪里。这篇博文是“STL 源码阅读”系列的一篇专门讲set。我不会把源码逐行贴出来讲解那没意思也没法读。我尽量按我自己的阅读路径走先搞清楚set的壳是什么、底下的肉是什么再去抠红黑树这个核心最后聊聊迭代器、插入删除、以及那些只有看了源码才懂的坑。内容会比较长但你真读进去收获也是持续的。1. 阅读前的准备set 的壳与里子1.1 先搞清楚 set 到底是什么std::set在标准里的定义很简单一个关联式容器存放唯一的、有序的元素。它对元素的要求是“可比较”默认用std::less做排序准则。从使用者的角度看set就是一个“自动排序 自动去重”的集合。但读源码时会发现set本身根本没有自己的数据存储逻辑。它所有的底层功能几乎全部转发给一个叫_Rb_tree的类模板。set只是给_Rb_tree套了一层壳把对外接口裁剪成适合“集合”语义的样子。所以读set的源码本质上读的是两件事set这个类模板怎么封装_Rb_tree_Rb_tree这个红黑树容器怎么实现插入、删除、查找、迭代这两层都看完才算真正读懂了set。1.2 选哪份源码来读目前主流的 STL 实现有好几份GCC 自带的 libstdc、LLVM 的 libc、MSVC 的 STL。我推荐从 GCC 的 libstdc 开始读。原因很直接它的_Rb_tree实现相对经典结构清晰且 STL 源码剖析那本书主要参考的就是 SGI STL和 libstdc 一脉相承网上讨论资源多遇到不明白的地方容易找到资料。libc 的实现也不错但它的代码风格更“现代化”用了不少宏和模板技巧新手读起来门槛偏高。MSVC 的实现细节和 GCC 有不少差异如果不是在 Windows 下开发优先级放后面。# GCC 环境下可以快速找到头文件位置以 Ubuntu 为例 g -print-file-nameinclude # 通常在 /usr/include/c/xx 下面 # set 的头文件是 bits/stl_set.h # _Rb_tree 的头文件是 bits/stl_tree.h我个人建议打开源码时同时开两个文件stl_set.h和stl_tree.h。前者是壳后者是核心。读的时候从stl_set.h入手看到它调用了_Rb_tree的哪个方法就跳过去看那个方法的实现。提示不要试图从头到尾一行行读那样会很快失去耐心。先画出“set 的公开接口 - 对应 _Rb_tree 的底层操作”这个映射表再逐个击破。1.3 set 的接口到底转发给了谁打开stl_set.h一眼扫过去能看到set类内部有一个类型别名typedef _Rb_treekey_type, value_type, _Identityvalue_type, key_compare, _Alloc _Rep_type; _Rep_type _M_t;set的所有公开操作基本上都是直接调_M_t的对应方法。比如begin()-_M_t.begin()insert(x)-_M_t._M_insert_unique(x)erase(pos)-_M_t.erase(pos)find(x)-_M_t.find(x)注意_M_insert_unique这个名字它表示“唯一插入”也就是如果元素已经存在就不插入。这正好对应set的去重语义。如果哪天你去看multiset会发现它的底层调用变成了_M_insert_equal——允许重复插入。这个设计其实就是经典的设计模式Bridge桥接模式。set是抽象接口_Rb_tree是实现体。两者可以各自独立演化。2. 红黑树结构set 的灵魂所在2.1 为什么 set 选择了红黑树而不是别的结构这是读源码之前必须想明白的问题。set需要支持有序遍历、快速查找、插入删除同时不能太消耗内存。候选方案有哈希表、AVL 树、跳表、B 树。哈希表查找 O(1)但无序做不到“按顺序遍历”。C11 里因此才有了unordered_set它和set是两套东西。AVL 树平衡性比红黑树更严格查找略快但插入删除时旋转频繁代价高。跳表实现简单但内存开销大缓存友好性差。B 树适合磁盘型数据库内存容器里玩不转。红黑树是个折中它不追求“完全平衡”而是保证“最长路径不超过最短路径的两倍”。所以它的树高控制在2log(n)级别插入删除时的重平衡代价也远低于 AVL。对set这种读写混合、还要求有序遍历的场景红黑树是面试官最爱问、也是工程上最稳的选择。2.2 从源码看红黑树的节点设计_Rb_tree的节点类型长这样简化版struct _Rb_tree_node_base { _Rb_tree_color _M_color; // 节点颜色红或黑 _Rb_tree_node_base* _M_parent; // 父节点 _Rb_tree_node_base* _M_left; // 左孩子 _Rb_tree_node_base* _M_right; // 右孩子 }; templatetypename _Val struct _Rb_tree_node : public _Rb_tree_node_base { _Val _M_value_field; // 实际存储的元素 };这里有个非常关键的设计_Rb_tree_node_base不存值只存树结构信息。所有红黑树相关的旋转、变色操作全部基于_Rb_tree_node_base完成完全不关心节点里存的是什么类型。只有到真正需要读写_Val时才通过继承下来的_Rb_tree_node访问_M_value_field。这种做法叫“模板分离”。它带来的好处非常明显树结构操作的代码只编译一次不管你setint还是setstring旋转逻辑的代码是同一份大大降低了二进制体积。2.3 关键点header 哨兵节点_Rb_tree里有一颗永远存在的空节点叫header。它不存储实际数据但它的_M_left永远指向树的最左节点_M_right永远指向树的最右节点_M_parent指向根节点。这个设计是 STL 容器迭代器合法性的基石。为什么要这样begin()要返回“最小元素”的迭代器。如果直接找根节点一路向左那每次都要走while (x-_M_left) x x-_M_left;。有了 header直接返回header-_M_left的迭代器就行O(1)。rbegin()同理返回header-_M_right。当树为空时header的_M_left和_M_right都指向 header 自己。这样迭代器永远有“哨兵”可指不会出现空指针。代码里对应的是templatetypename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc typename _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::iterator _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::begin() { return iterator(_M_begin()); // _M_begin() 内部返回 header-_M_left }2.4 红黑树的平衡规则回顾读旋转代码之前需要把红黑树的五条规则刻在脑子里每个节点非红即黑。根节点是黑色。每个叶子节点NIL是黑色。如果一个节点是红色则它的两个子节点必须是黑色不能有连续的红色节点。从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这五条规则保证了路径上黑色节点的数量一致从而限制了树的高度。后面的_Rb_tree_insert_and_rebalance和_Rb_tree_erase_and_rebalance两个函数本质就是“插入/删除后通过变色和旋转让树重新满足这五条规则”。3. 核心操作源码走读插入、删除、查找3.1 插入_M_insert_unique 是怎么工作的set的insert通过_M_insert_unique实现。当我们调用s.insert(5)时内部到底走了几步第一步从根节点开始按比较器查找插入位置同时记录路径上遇到的最后一个节点。这部分实现核心可以用伪代码表示templatetypename _Key, typename _Val, typename _KeyOfValue, typename _Compare, typename _Alloc pairtypename _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc::iterator, bool _Rb_tree_Key, _Val, _KeyOfValue, _Compare, _Alloc:: _M_insert_unique(const _Val __v) { // 从 header 开始_M_begin() 返回根节点 _Link_type __x _M_begin(); _Link_type __y _M_end(); // header bool __comp true; while (__x ! 0) { __y __x; __comp _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); __x __comp ? _S_left(__x) : _S_right(__x); } // 找到插入点后再走一遍查找确认是否已经存在相同 key iterator __j iterator(__y); if (__comp) { if (__j begin()) return _M_insert_(__x, __y, __v); else --__j; } if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) return _M_insert_(__x, __y, __v); // 已经存在返回已有元素的迭代器和 false return pairiterator, bool(__j, false); }这里有两个值得注意的点第一次循环只是定位到了插入位置但还不能确定这个 key 是不是已经存在。所以紧接着用--__j往前回退一个节点再用比较器验证“前一个元素是否小于待插入元素”。如果前一个元素不小于说明树里已经有相同的 key直接返回false。最终真正插入数据的是_M_insert_它负责分配节点、设置父子关系然后调用_Rb_tree_insert_and_rebalance做红黑树平衡修复。3.2 再看一眼M_insert和原地构造_M_insert_做的事情如下申请一块_Rb_tree_node内存通过分配器_M_get_node在节点内存上构造元素construct把节点挂到树中合适的位置调用_Rb_tree_insert_and_rebalance调整颜色和旋转更新 header 指针如果插入的是最小或最大节点header的_M_left或_M_right也要跟着变实现里有个细节是在 C11 之后insert有两个版本一个接收 const 左值引用一个接收右值引用。后者在节点构造时会调用std::move避免了不必要的拷贝。如果你往setstring里插一个临时字符串用s.emplace(hello)或者s.insert(std::move(str))能省掉一次字符串拷贝。这个优化在源码级是看得到的用法上也有感知。3.3 删除erase 的三种形态set::erase有三个重载erase(iterator pos)删除指定位置的元素erase(const key_type x)删除指定 key 的元素返回删除个数set 里要么 0 要么 1erase(iterator first, iterator last)删除一个区间底层调用_Rb_tree::erase之后真正干活的是_Rb_tree_erase_and_rebalance。这个函数是红黑树实现里最难啃的一块比插入要复杂。原因是删除一个黑色节点会破坏规则五黑色高度一致而删除红色节点则不用修复。所以删除后的修复逻辑要处理各种兄弟节点颜色、侄子节点颜色的组合情况。源码里面对应的是经典的“删除修复四情况”兄弟节点是红色先做一次旋转把红色兄弟转上去变成黑色兄弟的情况兄弟节点是黑色且兄弟的两个孩子都是黑色把兄弟变红问题向上传递兄弟节点是黑色左孩子是红色、右孩子是黑色或反过来先做局部旋转变成下面的情况兄弟节点是黑色且同侧孩子是红色做一次旋转把兄弟转上去变色结束修复这四类情况我在读源码的时候就对着 CLRS 的算法导论那章来读两边对照很快就能看通。单纯看代码很容易晕因为各种_M_parent、_M_left的指针换来换去没有一个指导框架在脑子里会越看越乱。3.4 查找find 为什么不走 key 的 operatorset的查找走的是比较器_Compare默认是std::less。find的逻辑就是从根节点开始按comp(key, node_key)的结果向左或向右走直到找到相等的元素或走到空节点。这里有个特别容易被误解的点set判断“相等”的标准不是而是“互不小于”。也就是说如果comp(a, b)和comp(b, a)都为假set就认为 a 和 b 等价。对于std::less这等价于a b和b a都为假也就是a b对于标准类型而言。但如果你传入一个自定义比较器比如按照abs(x)排序那么set会认为绝对值相同的数“相等”即使x本身不同。这是源码里一个非常实用的知识点后面讲坑的时候还会回到这。查找的复杂度是O(log n)这一点从源码结构上看得清清楚楚因为树高受红黑树约束每次比较都会排除掉一半的子树不可能有线性扫描。4. 迭代器与 const 正确性4.1 set 的迭代器为什么是 const_iterator在stl_set.h里能看到这样的定义typedef typename _Rep_type::const_iterator iterator; typedef typename _Rep_type::const_iterator const_iterator;注意set的iterator直接就是_Rb_tree的const_iterator。也就是说即使你拿到一个非 const 的setint的iterator你也只能读取元素不能修改。这是刻意为之。因为set的排序依据是元素的 key。如果你能通过迭代器直接修改元素那等于可以把树里某个节点的值改掉从而破坏红黑树的有序性。后续的查找和遍历都会出问题。代价就是你不能通过迭代器对set的元素做原地赋值。如果想修改只能 erase 掉再 insert 新的。这个设计冲突在源码层面体现得非常直接_Rb_tree本身有iterator和const_iterator但set对外只暴露const_iterator。你可以在_Rb_tree层面自由读写但set把这扇门焊死了。4.2 迭代器 是怎么找到下一个节点的这是红黑树迭代器实现里最精彩的地方。_Rb_tree_iterator::operator的逻辑是_Self operator() { _Rb_tree_node_base* __y _M_node; if (__y-_M_right ! 0) { // 如果右子树非空下一个节点就是右子树的最左节点 __y __y-_M_right; while (__y-_M_left ! 0) __y __y-_M_left; } else { // 如果右子树为空往上找第一个“我是它左孩子”的祖先 __y __y-_M_parent; while (__y-_M_parent __y-_M_parent-_M_right __y) { __y __y-_M_parent; } __y __y-_M_parent; } _M_node __y; return *this; }一句话总结右孩子存在就去右子树的最左右孩子不存在就一路向上直到某个节点是其父节点的左孩子那么父节点就是下一个。思考题为什么要借助“右子树非空”而不是“当前节点有右孩子”因为红黑树里节点可能只有左孩子也可能只有右孩子还可能没有孩子。这个逻辑实际上是中序遍历的迭代版——树结构中序遍历的结果就是有序序列。begin()从最左节点出发一路走到最右节点end()就是 header。把中序遍历和红黑树结合起来理解迭代器设计就完全通了。类似的operator--是对称的逻辑左子树最右、或者向上找“我是它右孩子”的祖先。4.3 为什么 end() 不是空指针很多其他容器实现里end()可以理解成“最后一个元素的后一个位置”往往用空指针表示。红黑树特殊在它是双向迭代器需要支持--end()得到最后一个元素这个操作不能对空指针做。所以 header 哨兵节点在这个地方再次发挥作用。end()返回的迭代器指向 header而不是nullptr。--end()时进入operator--由于 header 的_M_right指向最右节点自然就能得到最大元素。哨兵节点的存在让红黑树迭代器始终有一个“非空但无意义”的节点可依赖这让边界情况的代码简单了很多。这也是 STL 源码设计里我认为最妙的地方之一。5. 源码阅读后记我知道的避坑指南与实用心得5.1 迭代器失效规则set 比 vector 友好得多关于set很多资料会提“插入和删除其他元素时迭代器不会失效”。源码读完这句话就好理解了插入新节点时树结构会旋转、变色但节点的内存地址不会搬移。已经存在的迭代器指向的还是同一个_Rb_tree_node数据没动过所以迭代器依然有效。删除某个节点时只有指向被删节点的迭代器失效。其他迭代器指向的节点内存还在指针关系虽然可能因旋转改变了但迭代器本身存的是节点指针不受影响。这和vector完全不同。vector插入导致扩容所有迭代器直接失效删除元素导致元素搬移后面的迭代器全部失效。set的节点是独立的堆内存搬移不存在的所以迭代器自然稳定。但注意一件事虽然迭代器不失效set的erase(key)返回值在 C11 之前是size_tC11 之后变成了返回size_type删除个数。而erase(pos)返回的是下一个迭代器。这两个别搞混。5.2 自定义比较器最容易踩的坑实战里我见过不少人给set传了个自定义比较器结果插入时行为诡异。最常见的问题有三个。第一个比较器不满足“严格弱序”strict weak ordering。比如比较器里用了那a b和b a可能同时成立导致set认为两个不相同的元素等价误吞数据。源码里_M_key_compare是直接用的它不会去校验你的比较器是否合法出了问题全是静默的。第二个比较器只比较部分字段。比如一个结构体有 id 和 name 两个字段比较器只比较 id那存进去之后即使 name 不同set也认为它们“相等”。find的时候只用 id 找name 跟没存一样。第三个比较器的结果依赖外部可变状态。这相当于让树的排序规则随时变化红黑树直接崩给你看。重要Comparator 必须满足严格弱序——comp(a, a)必须为 false且对于任意三个元素传递性必须成立。这是所有基于比较的 STL 容器set、map、priority_queue、sort的隐含契约。5.3 性能问题set 真的比 unordered_set 慢吗这个纠结了很多人的问题源码也能给出答案。set的查找是O(log n)unordered_set是平均O(1)。数据量很大时unordered_set确实通常更快。但真实工程里要考虑缓存、哈希冲突、内存碎片。set的节点分散在堆上遍历时缓存不友好unordered_set的 bucket 数组是连续的节点通常也集中分配遍历时缓存命中率更高。但反过来unordered_set的哈希函数如果设计得差冲突多到退化成链表性能会比set更糟糕。此外set能提供有序遍历这是unordered_set做不到的。如果你需要“按顺序输出”千万别拿unordered_set排序然后输出直接用set遍历更快。实测经验元素量小于几百个时set和unordered_set差距感知不到元素量几万到几十万时unordered_set可能快 2-3 倍但如果你频繁插入删除unordered_set的 rehash 开销反而可能让它慢下来。5.4 内存开销set 到底有多“重”每个set节点除了存元素本身还要存三个指针parent、left、right和一个颜色标记。在 64 位系统上这三个指针就是 24 字节颜色枚举至少 1 字节但会对齐到 4 字节。也就是说每存一个int4 字节树的元信息就要 28 字节左右。如果你有十万个int存到set里光树结构的开销就是 2.8MB 往上而原始数据本身才 0.4MB。这在嵌入式或内存敏感场景是不能忽视的。所以数据规模大且不需要有序性时优先考虑std::vector sort unique或std::unordered_set。set的正确使用场景是需要动态插入删除、同时要求有序遍历、且数据量可控。5.5 面试题视角set 源码常被问到的几个点读源码本身也是为面试做准备。我看过不少候选人聊到set就说“底层是红黑树”但深问一层就卡住。这里总结几个常见追问点set的插入返回类型是什么答pairiterator, boolbool 表示是否插入成功。set迭代器为什么不能修改元素答会破坏有序性所以实现上把迭代器直接定为 const_iterator。set和map的底层区别是什么答map的_Rb_tree存的是pairconst Key, T_KeyOfValue提取 pair 的 firstset存的是 Key 本身。lower_bound和upper_bound在set里怎么找的答基于红黑树的二分查找找到第一个不小于或大于key 的节点。红黑树插入后最多几次旋转答插入修复最多两次旋转删除修复最多三次旋转。这个结论源码里有体现。6. 实操试验从源码出发验证红黑树行为6.1 用调试器跟踪一次插入过程源码读再多不如动手跑一遍。我用一个简单的例子做过验证#include set #include iostream int main() { std::setint s; for (int x : {10, 5, 15, 3, 7, 12, 18}) { s.insert(x); } for (auto it s.begin(); it ! s.end(); it) { std::cout *it ; } std::cout \n; }用 gdb 打断点断在_Rb_tree_insert_and_rebalance每插入一个数看根节点颜色、左右孩子。你会亲眼看到“10 是黑根5 和 15 是红孩子插入 3 时触发左左旋转”这些教科书上的过程真实发生。我强烈建议自己也做一次这个实验。理由很简单红黑树的旋转和变色操作光看源码容易“看了就忘”但在调试器里一步步跟过之后就会发现它其实就是二叉搜索树的插入加上“修正颜色和结构”的后处理。6.2 验证 set 的严格弱序语义换个角度用自定义类型来验证前面说的比较器陷阱struct AbsCompare { bool operator()(int a, int b) const { return std::abs(a) std::abs(b); } }; int main() { std::setint, AbsCompare s; s.insert(3); s.insert(-3); // 第二次插入abs(-3) abs(3)set 认为已存在 std::cout s.size() \n; // 输出 1 }这个例子很好地演示了“等价”不等于“相等”的语义。3和-3在operator下不等但AbsCompare认为它们等价所以第二个插入被拒绝。实际开发中如果你依赖set::find的“精确匹配”语义这种自定义比较器就会带来隐蔽 bug。6.3 验证 erase 过程中的迭代器稳定性再做一个简单试验来判断“erase 一个节点其他迭代器是否有效”std::setint s {1, 2, 3, 4, 5}; auto it2 s.find(2); auto it4 s.find(4); s.erase(3); std::cout *it2 *it4 \n; // 正常输出 2 4我实测过很多次结果都是正常的。原因是erase(3)虽然触发了删除后的平衡修复但节点 2 和节点 4 的内存地址没有变化迭代器里保存的指针仍然有效。这个特性在多线程环境下做“无锁读 加锁写”时很有用但必须注意整体同步策略不能因为set迭代器稳定就掉以轻心。6.4 批量插入用 insert 的迭代器版本源码里还有一个容易被忽略的接口insert(InputIterator first, InputIterator last)。它内部会循环调_M_insert_unique。如果你手头有一个已经排好序的 vector 要转成 set可以传vector.begin()和vector.end()。这里有个细微差别_M_insert_unique在插入时如果待插入的值已经存在会直接跳过不会更新已有节点。所以批量插入时如果输入有重复重复项会被静默忽略这符合set语义。另一个小技巧是std::set::mergeC17 引入可以把另一个 set 的节点直接“嫁接”过来避免重新分配节点内存。如果你要把一个set合并到另一个优先考虑merge而不是循环 insert因为merge利用底层红黑树结构复杂度更有优势。6.5 性能测试set vs vectorsortunique我统计过一个简单实验随机生成 100 万个整数分别用set和vector sort unique做去重再测量耗时和峰值内存。结果符合源码层面的推断set单元素插入每个节点独立分配内存随机访问模式导致缓存命中差总体耗时偏高。vector是连续内存sort是原地排序去重后直接uniqueerase整体比set快不少内存也更紧凑。但反过来如果你需要“边插入边查询”“随时删除”vector的优势就没了。这个实验想说明的是源码结构决定了容器性能特征读源码的意义就是让你在看到接口的第一眼就对它的性能画像有直观判断而不是跑一堆 benchmark 才恍然大悟。7. 最后分享一点读完源码后的体会整套set源码读下来我最强烈的感受是STL 的代码不是写给编译器看的是写给读懂它的人看的。_Rb_tree把树的通用操作抽象到基类set把接口收窄到集合语义迭代器用哨兵节点免去边界判断每个设计都有它的历史背景和权衡逻辑。读之前我以为set的源码就是一棵“加了颜色的二叉搜索树”读完之后才发现真正复杂的是各种边界条件和语义约定等价和相等不是一回事、end()不是空指针、插入返回值为什么是 pair、为什么迭代器不能修改元素。这些东西不读源码光靠经验是永远踩不全的。如果这篇能给你一点启发建议自己打开stl_tree.h跟着走一遍。从_M_insert_unique进从_Rb_tree_erase_and_rebalance出中间卡住了就回去翻算法导论的红黑树章节。那本书的图配上 GCC 的源码是我见过最有效的组合。等你读通了再去看map、multiset、multimap基本就是换个壳的事。