封装map和set，红黑树内部的具体实现，单模板参数无法实现的原因，模板泛型思想的应用，迭代器特性

STL 的 _Rb_tree：set 与 map 如何共用一棵红黑树，以及它的迭代器原理（大纲）

摘要

本文从"set 只存 key、map 存 key-value 对，为什么一棵_Rb_tree就能实现两种容器"切入，拆解 SGI STL 的_Rb_tree模板设计：节点里存什么由第二个模板参数Value决定（set 传Key，map 传pair<const Key, T>），KeyOfValue（identity/select1st）负责从节点数据中提取比较用的 key；并回答"源码里的 Value 为什么不是键值对的 value"这个最容易被绕晕的问题。后半篇拆解迭代器实现：大框架沿用 list 迭代器思路（一个类封装节点指针 + 重载运算符，用模板参数Ref统一 iterator / const_iterator），核心难点是把++/--写成"中序后继 / 前驱"——有右子树就取右子树最左节点，没有就沿父链上溯到"父节点的左孩子"为止；哨兵节点header与根互为 parent、left/right 分别封住最小和最大节点，让begin()/end()自然成立。最后给出易混点清单（源码 Value ≠ 键值 value、set 元素不可改、map 的 key 是 const 而 value 可改、解引用 end() 是未定义行为等）。

---

本篇基于手抄笔记（SGI STL 风格：stl_set.h/stl_map.h/stl_tree.h，_Rb_tree/header命名）整理。标注【笔记】的是笔记直接出现的内容，【补充】的是笔记留白、补上才能闭环的部分。

---

一、主题：一棵红黑树，两种容器

• 抛出问题：
  • std::set里每个节点只存一个 key；std::map里每个节点存一对pair<const Key, T>。存储内容不同，为什么不需要写两棵树？
• 一句话答案：_Rb_tree的"节点存什么"不是写死的，而是由模板参数在实例化那一刻决定——set 和 map 只是用不同参数实例化了同一份模板。
• 【补充】背景交代：
  • 这是 SGI STL（C++ 标准库的原型实现）的写法，文件对应stl_set.h/stl_map.h/stl_tree.h。
  • 后来 libstdc++（GCC）把同一套思想改名为__tree/__rb_tree_node/__node，结构一致，只是命名风格不同（见"延伸阅读"）。

---

二、_Rb_tree 的模板设计：一份代码通吃 set 和 map【笔记】

2.1 set 与 map 的简化定义【笔记】

// stl_set.htemplate<classKey,classCompare=less<Key>,classAlloc=alloc>classset{public:typedefKey key_type;typedefKey value_type;// 注意：set 的 value_type 就是 Key 本身private:typedef_Rb_tree<key_type,value_type,identity<key_type>,key_compare,Alloc>rep_type;rep_type t;// 表示该 set 的红黑树};

// stl_map.htemplate<classKey,classT,classCompare=less<Key>,classAlloc=alloc>classmap{public:typedefKey key_type;typedefT mapped_type;typedefpair<constKey,T>value_type;// map 的 value_type 是"键值对"private:typedef_Rb_tree<key_type,value_type,select1st<value_type>,key_compare,Alloc>rep_type;rep_type t;// 表示该 map 的红黑树};

• 对照看两个定义，就看出"一份模板"的用法：
  • set：第二个参数传key_type→ 节点里存 key。
  • map：第二个参数传pair<const Key, T>→ 节点里存键值对。
  • “一份模板，实例化出不同的 rb tree：一个存 Key，一个存 pair<K, V>”【笔记】。
• 【补充】第三、四个模板参数的差异（笔记原图两处都疑似写identity，map 实际应为select1st，待核对）：
  • identity<key_type>：存储即 key，原样取出（set 用）。
  • select1st<value_type>：存储是 pair，取第一个元素（const Key）作为比较用的 key（map 用）。

2.2 节点结构：Value 控制节点里存什么【笔记】

template<classValue>struct_Rb_tree_node:public_Rb_tree_node_base{Value _M_data;// 节点实际存储的数据};

• 【补充】_Rb_tree_node_base是骨架：_M_left/_M_right/_M_parent三个指针 + 颜色标记（红黑树维护用）；_Rb_tree_node在骨架上追加一个_M_data装业务数据。
• 骨架与数据分离的意义：
  • 旋转、重新着色这些"结构操作"只碰骨架，写一次就够；
  • "数据是什么"完全由实例化时的Value决定，set / map 各取所需。

2.3 围绕模板参数的三个疑问【笔记】

• 疑问 1：为什么"是 key 搜索场景还是 key/value 搜索场景"不直接写死？
  • 场景不是写死的，由第二个模板参数Value决定节点里存的数据类型，一棵树结构同时服务两种场景。
• 疑问 2：源码里的 “Value” 和日常 key/value 的 “value” 是一回事吗？
  • 不是。源码中Value=节点中真实存储的数据类型：对 set 而言它其实就是Key，跟"键值对的 v"毫无关系。这是读 STL 源码最容易绕晕的点。
• 疑问 3：set 里 Key 和 Value 明明一样，为什么第一个模板参数 Key 还要单独传？

  • 第一个模板参数是find/erase等接口的形参类型：

    boolinsert(constValue&v);iteratorfind(constKey&key);

  • set 的 insert 和 find 恰好同型；map 的 insert 传 pair，find / erase 传 Key，两个参数各司其职。

• 【补充】KeyOfValue的角色：把"从节点数据里取出 key"统一成一步，使_Rb_tree内部查找 / 比较代码对 set、map 无差别。
• 命名吐槽【笔记】：set 用Key命名、map 用Key+T命名、_Rb_tree又用Key+Value命名，风格不统一（“大佬写代码有时也不规范”）。读源码时看类型别看名字，别被命名带偏。

---

三、迭代器的设计大框架：从 list_iterator 借来【笔记】

3.1 用一个类统一 iterator 和 const_iterator【笔记】

• 大框架与 list 的迭代器思路一致：用一个类型封装节点指针，重载运算符，让对象有指针的行为。

  template<classT,classRef>classlist_iterator{Refoperator*();// Ref = T& → list_iterator// Ref = const T& → list_const_iterator};

  • 两种迭代器（可改 / 不可改）不是写两个类，而是同一个类用Ref参数实例化两次。

• 【补充】_Rb_tree的迭代器同理：_Rb_tree_iterator与_Rb_tree_const_iterator共享实现，区别只在解引用给出去的是Value&还是const Value&。

• 红黑树迭代器真正的难点【笔记】：树节点在内存里不连续，++/--不能像数组、list（配合哨兵）那样简单取"下一个地址"，必须按中序遍历的结构关系跳转。这是本篇的主体（第四、五、六节）。

3.2 迭代器的"可修改性"是怎么设计的【笔记】

• set 的迭代器不支持修改元素：把树的第二个模板参数改成const K即可：

  RBTree<K,constK,SetKeyOfT>_t;

• map 的迭代器不支持修改 key，但支持修改 value：把pair的第一个参数改成const K即可：

  RBTree<K,pair<constK,V>,MapKeyOfT>_t;

• 【补充】原理：key 决定树中节点的相对位置，一旦可改，BST 不变式随时可能被破坏，所以用const 在编译期封死；value 不参与排序，原地修改无副作用。这也解释了"it->first = x编译不过、it->second = x合法"。

• 笔记末句留白【笔记】：要支持完整迭代器（比较运算符、operator==/!=、后置++等）还有不少细节要改，参考配套代码。

---

四、中序遍历语义：begin() 与 end() 的由来【笔记】

4.1 为什么 begin() 是最左节点

• BST 的中序遍历顺序 = 排序顺序：左子树 → 根节点 → 右子树。

• 所以"中序第一个"就是全树最左节点：begin()返回最左节点所在结点的迭代器。

• 笔记示例树（后文反复使用）：

  18 / \ 10 30 \ / \ 15 25 40 / \ 35 50

  • 中序结果：10, 15, 18, 25, 30, 35, 40, 50 →begin()指向 10。
  • （待核对原图：15 为 10 的右孩子、25 为 30 的左孩子，以上按笔记文字描述"15 是 10 的右、25 是 30 的左"整理。）

4.2 end() 的两种表示：nullptr vs 哨兵 header【笔记】

• 以 50（最右节点）为例走一遍"往上找"：
  • ++it时：50 是 40 的右 → 40 是 30 的右 → 30 是 18 的右 → 18 到根没有父亲；
  • 始终找不到"孩子是父亲左"的那个祖先，父亲为空 → 把迭代器里的节点指针置为nullptr，用nullptr充当end()。
• STL 源码的做法：增设一个哨兵位头结点header作为end()：
  • header与根互为父亲（root->_M_parent == header，header->_M_parent == root）；
  • header->_M_left指向最左节点（最小值），header->_M_right指向最右节点（最大值）。
• 两种方案对比【笔记】：
  • 相比nullptr方案差别不大——“它所能实现的，我们也能实现；只是end()判断到结点为空时特殊处理一下，让迭代器节点指向最右结点”。
  • 哨兵的好处：begin()/end()形态统一，while (it != end())惯用法自然成立，不必处处判空。

---

五、operator++ 详解：中序后继【笔记】

5.1 核心思路

• 原话【笔记】：“迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下一个结点。”

• 分两种情况：

  情况 1：当前结点的右子树不为空

  • 当前结点已访问完，下一个是右子树的中序第一个；
  • 任何一棵子树的中序第一个 =最左节点→ 直接"先向右一步，再一直向左到底"。

  情况 2：当前结点的右子树为空

  • 当前结点已访问完，且当前结点所在的子树也访问完了，下一个结点必然在祖先里 → 沿"当前结点到根"的路径向上找：
    • 当前结点是父亲的左孩子：按中序"左子树 → 根 → 右子树"，左子树（含当前结点）刚访问完，下一个就是父亲。
      • 笔记例子：it 指向 25，25 右为空，25 是 30 的左 → 下一个访问的结点是 30。
    • 当前结点是父亲的右孩子：当前结点所在子树访问完、其父亲的子树也访问完，继续往上找，直到找到"孩子是父亲左"的那个祖先，它就是要访问的下一个结点。
      • 笔记例子：15 右为空，15 是 10 的右，15 所在子树、10 所在子树都访问完了；继续往上，10 是 18 的左 → 下一个是 18。
    • 一路到根仍没找到（当前是最后一个节点）：→end()。
  • 笔记图中标注：“孩子是父亲左的那个祖先”。

5.2 三个例子在示例树上的走位【笔记 + 补充】

++(15): 15 右为空 → 15 是 10 的右，上溯；10 是 18 的左 → 停。后继 = 18 ++(25): 25 右为空 → 25 是 30 的左 → 停。后继 = 30 ++(30): 30 右子树非空(40) → 进右子树再一路向左：40 → 35。后继 = 35 ++(50): 50 右为空 → 50 是 40 的右；40 是 30 的右；30 是 18 的右； 18 是 header 的左 → 停。后继 = header，即 end()

5.3 代码实现（SGI 风格，注释版）【笔记 + 补充】

// increment()：让 _M_node 指向中序后继voidincrement(){if(_M_node->_M_right){// 情况 1：有右子树_M_node=_M_node->_M_right;// 先向右一步while(_M_node->_M_left)// 再一直向左，到最左为止_M_node=_M_node->_M_left;}else{// 情况 2：无右子树while(_M_node==_M_node->_M_parent->_M_right)_M_node=_M_node->_M_parent;// 只要是父亲的右孩子就继续上溯_M_node=_M_node->_M_parent;// 成为"父亲的左孩子"时，父亲即后继}}

• 对照 5.1 的两种情况逐行理解：
  • while条件_M_node == _M_node->_M_parent->_M_right循环的语义：“当前结点是父亲的右孩子就继续上溯”；
  • 循环退出时当前结点是父亲的左孩子（或已到头），此时的父亲就是中序后继；
  • 最右节点一路追到header（18 是 header 的左孩子 → 退出循环后_M_node = header），正好落到end()。
• 【补充】复杂度：单次++最多沿父链上溯若干步，但整趟遍历 n 个元素总步数 O(n)，均摊 O(1)。

---

六、operator-- 详解：中序前驱【笔记】

6.1 核心思路

• 原话【笔记】：“迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为它的访问顺序是右子树 → 根节点 → 左子树。”

• 分三种情况（与++对称）：

  情况 1：当前结点的左子树不为空

  • 前一个结点是左子树的中序最后一个 =左子树最右节点→ 先向左一步，再一直向右到底。

  情况 2：当前结点是哨兵 header（即从 end() 后退一步）

  • header本身不存数据，--到header时应落到最右节点（全树最大值）：_M_node = _M_node->_M_right。

  • 源码写法【笔记】：

    operator--(){if(_M_node==header)_M_node=header->_M_right;// end() 后退一步 → 最右节点...}

  情况 3：无左子树，且不是 header

  • 沿父链上溯：当前结点是父亲的左孩子就继续上溯；一旦当前结点是父亲的右孩子，那个父亲就是前驱。

6.2 例子在示例树上的走位【笔记 + 补充】

--(18): 18 左子树非空(10) → 进左子树再一路向右：10 → 15。前驱 = 15 --(30): 30 左子树非空(25) → 25 无右子。前驱 = 25 --(25): 25 左为空，25 是 30 的左 → 上溯；30 是 18 的右 → 停。前驱 = 18 --(end/header): header 无数据 → _M_node = header->_M_right = 最右节点 50

6.3 代码实现（SGI 风格，注释版）【笔记 + 补充】

// decrement()：让 _M_node 指向中序前驱voiddecrement(){if(_M_node->_M_color==_S_red){// 当前是 header（哨兵，红色）_M_node=_M_node->_M_right;// 情况 2：落到最右节点while(_M_node->_M_left)// 再一路向左到底_M_node=_M_node->_M_left;}elseif(_M_node->_M_left!=0){// 情况 1：有左子树_M_node=_M_node->_M_left;// 先向左一步while(_M_node->_M_right)// 再一直向右，到最右为止_M_node=_M_node->_M_right;}else{// 情况 3：无左子树base_ptr y=_M_node->_M_parent;while(_M_node==y->_M_left){// 只要是父亲的左孩子就继续上溯_M_node=y;y=y->_M_parent;}_M_node=y;// 成为"父亲的右孩子"时，父亲即前驱}}

• 对照 6.1 三种情况逐行理解：
  • 第一个分支判断的是颜色：真实数据节点之外，只有header哨兵是红色（SGI 的约定），所以"是不是 header"直接看颜色——这就是笔记里把"颜色"和header关系标红圈的原因；
  • 第三分支while (_M_node == y->_M_left)的语义与increment完全镜像。
• 【笔记】末尾的-- end()注记：--作用于end()时合法，得到指向最右元素的迭代器；++作用于begin()同理。不要对end()做++，也不要对begin()做--（都是未定义行为）。

---

七、header 哨兵与源码细节：begin / end / leftmost / root【笔记】

7.1 一棵带哨兵的树（对照图）

header(哨兵, 红) / \ (header 与根互为 parent) _M_left _M_right | | v v 18 ======== 50 ← 18 是最左节点(begin)，50 是最右节点 / \ 10 30 ...

• header是虚拟节点，不存业务数据，只负责封住首尾；
• header->_M_left= 最左节点 =begin()的位置；
• header->_M_right= 最右节点；
• 根节点通过header->_M_parent取得。

7.2 关键成员与函数【笔记】

protected:size_type node_count;// 记录树中节点总数（size() 由此而来）link_type header;// 哨兵节点指针Compare key_compare;// 比较器（默认 std::less<Key>）iteratorbegin(){returnleftmost();}const_iteratorbegin()const{returnleftmost();}iteratorend(){returnheader;}// end() 就是 header 本身const_iteratorend()const{returnheader;}link_type&leftmost()const{return(link_type&)_M_header->_M_left;// 强转掉 const，直接暴露可写引用}link_type&root()const{return(link_type&)_M_header->_M_parent;// 根 = header 的 parent}

• 【补充】两个值得留意的"小动作"：
  • leftmost()/root()在const函数里做了const_cast式强转：header 的 left/right/parent 只是"指针"，允许 const 容器也返回可引用的链接位，是 SGI 的惯用技巧；
  • begin()不是从根一路向左找，而是直接读header->_M_left（最左节点始终被 header 挂着），O(1)。

7.3 迭代器解引用【笔记】

_V&operator*()const{returnthis->_M_node->_M_data();}// 非 const 迭代器const_V&operator*()const{returnthis->_M_node->_M_data();}// const 迭代器

• 【补充】_M_data()取出节点里的业务数据（map 就是那个pair<const K, V>）；迭代器的"可改/不可改"最终全部落在这一行的返回类型上（呼应 3.2 节的const K/pair<const K, V>设计）。

---

八、易混点与高频面试题

#	易混点	正确结论
1	源码里的 “Value” 是键值对的 value 吗？	不是。Value= 节点实际存储的数据类型；set 里它反而就是Key
2	set 和 map 是不是两套不同的树？	不是，同一份_Rb_tree模板，参数不同实例化出不同容器
3	为什么 set 要传 Key 和 Value 两个一模一样的参数？	第一个参数是find/erase的形参类型；set 恰好同型，map 的 insert(find pair) 与 find(erase Key) 才不同
4	set 的元素能改吗？map 的 key 能改吗？	set 元素不可改（节点存的就是 key）；map 的 key 因pair<const K, V>不可改，value 可改
5	*end()合法吗？	未定义行为；end()指向哨兵，不可解引用
6	++到底怎么走？	有右子 → 右子树最左；无右子 → 上溯到"父亲的左孩子"，其父为后继
7	--到底怎么走？	有左子 → 左子树最右；无左子 → 上溯到"父亲的右孩子"，其父为前驱；--end()→ 最右节点
8	为什么树里要加哨兵 header？	统一 begin/end 形态，免判空；header与根互为 parent，left/right 封住最小/最大
9	++/--复杂度是多少？	均摊 O(1)（遍历 n 个节点总上溯步数 O(n)）
10	SGI 的_Rb_tree和 GCC 的__tree是什么关系？	同一套思想：libstdc++ 重命名 + 微调（__rb_tree_node_base、__node分层相同），读法通用

快答

• 面试问"map 迭代器的operator++怎么实现？" → 中序后继：有右子取右子最左，无右子沿父链上溯到父节点的左孩子；配合哨兵 header 让 end() 自然成立，均摊 O(1)。
• 面试问"为什么 set 元素不可修改？" → 节点存储类型在实例化时定为const Key（set 直接存 Key），且 key 决定节点位置，可改则破坏 BST 不变式。

---

九、知识链串联（Feynman 视角）

• 前置：
  • BST 中序遍历 = 排序序（本文第四节的地基）；
  • 红黑树五条性质与插入/删除修复（见《红黑树》篇，本文只引用"树是平衡的"这一事实）；
  • 迭代器五类成员（*、++、--、==、迭代器类别）——本文实现其中结构相关的几个。
• 平行对照：
  • list迭代器：节点在物理上也是散的，但 list 有"双向链表 + 哨兵头"，++/--直接走 next/prev；
  • 本文的_Rb_tree迭代器：节点靠 left/right/parent 三指针组织，++/--走的是中序遍历的拓扑关系——同样是"封装指针 + 重载运算符"，难点全在跳转算法。
• 后续可展开：
  • 手写一套RBTree<K, V, KeyOf>+ 迭代器（笔记里"支持完整的迭代器还有很多细节"即指这部分）；
  • 在RBTree上包set/map接口（insert/find/begin/end），完整复刻本文 §二 的模板设计。

---

十、复习挑战清单（主动回忆）

• 不看笔记默写：set / map 实例化_Rb_tree时各传了什么模板参数？
• 说清：源码里的Value、日常的 key/value 里的 value、mapped_type三者分别指什么？
• 画出示例树（18/10/30/15/25/40/35/50），并手动走一遍++(15)、++(30)、--(25)的完整路径。
• 写出increment()的两种情况，并解释while (_M_node == _M_node->_M_parent->_M_right)这一行在干嘛。
• 写出decrement()三种情况，并说明"第一个分支为什么看颜色就能判断出 header"。
• 说明header与根"互为 parent"、left/right 封住最左最右的布局，以及begin()为何是 O(1)。
• 解释"set 元素不可改、map 的 key 不可改而 value 可改"在类型层面是怎么实现的。
• 一句话回答：为什么迭代器++是均摊 O(1) 而不是每次 O(log n)？

---

十一、记忆锚点

• “一份模板，两个实例”：set 节点存 Key，map 节点存 pair<K,V>，树只有一份代码。
• “第一参数管接口（find/erase 形参），第二参数管存储（节点里装什么），KeyOfValue管提取（从存储里掏出 key 来比较）。”
• “++口诀：右子不为空，进右向左冲；右子若为空，上溯找左翁（父亲的左孩子，父即后继）。”
• “--口诀：左子不为空，进左向右冲；左子若为空，上溯找右翁；站在 header（红哨兵）上，先右再左到最大。”
• “哨兵 header：跟根互为爹，左手最小右手最大，end() 就是它本人。”

---

十二、延伸阅读

• 配套代码：笔记所指的"具体参考下面题的代码"（RBTree + 完整迭代器实现）。
• libstdc++bits/stl_tree.h：同一套思想，命名换成__tree/__rb_tree_node_base/__node，_M_impl._M_header即本文 header。
• LLVM/Clanginclude/llvm/ADT与 libc++__tree：哨兵布局略有差异，读法一致。
• 《STL 源码剖析》红黑树与 map/set 章节：本文 §二 的"set 用 identity / map 用 select1st"即出自该书。
• CP-Algorithms / Visualize 类红黑树可视化：中序后继路径动画，对照第五节三个例子。

任何的批评和建议欢迎指出，我们共同进步！