相关文件：

• include/set 头文件按顺序引入了 include/bits/stl_tree.h 和 include/bits/stl_set.h。
• include/bits/stl_set.h 定义了 std::set，依赖了 include/bits/stl_tree.h 却没有明确包含它。
• include/bits/stl_tree.h 定义了诸多类型，如未明确指出则默认下面提到的类型都是来自于这个头文件。
• src/c++98/tree.cc 实现了红黑树用到的非模板算法。这个文件只有 400 多行。

std::set 将实现转发给 _Rb_tree 处理，而它又将实现转发给了 _Rb_tree_impl 处理。

_Rb_tree_impl 继承于：

• _Node_allocator：是一个 typedef，实际类型是一个模板类，模板参数和 _Rb_tree 的参数有关。
• _Rb_tree_key_compare：是一个模板类，模板参数和 _Rb_tree 有关。
• _Rb_tree_header：非模板类。包含了 _Rb_tree_node_base 结构和 _Rb_tree_node_count。前者是表示红黑树结点的聚合类，包含了 parent/left/right/color 四个重要成员；后者是结点计数。初始化时，parent/left/right 都被设置为 header 本身的地址，而 color 被设置为红色，可见这个 header 就是标准库红黑树中的 nil 哨兵。另外，left 和 right 还有最小结点和最大结点的含义。

以插入算法举例，由于比较算子在模板中，所以需要用模板方法找到应该插入的位置，这些都在头文件 include/bits/stl_tree.h 中实现。接着调用插入并平衡的函数，该函数只操作指针，不关心结点中包含的值，所以这个部分可以在源文件 src/c++98/tree.cc 中实现，从而减少了代码膨胀。

按照上面的分析，可以解释以下未定义行为（但是不建议这么写）：

std::set<int> set;
auto it = set.end();
++it; // dead loop

由于 set.end() 返回了哨兵，初始化情况下三个指针都指向自己，所以按照自增算法会一直向右搜索，造成死循环。

std::set<int> set{1};
auto it = set.end();
++it;
assert(it != set.end());
++it;
assert(it == set.end());

由于哨兵的 right 指针指向最大元素，因此自增之后回到了最大元素的位置。再自增一次又回到了哨兵的位置。