容器 map 和 set 的底层实现均依赖于红黑树。本文深入探讨如何利用红黑树封装这两种标准容器，剖析其设计精妙之处与底层逻辑。
1. map/set 设计的巧妙之处
map 存储 key/value 对，set 仅存储 key。面对两种不同的参数类型，如何复用同一套红黑树结构？
直观方案是维护两棵独立的红黑树，但这会导致代码复用率极低且维护成本高昂。工程实践中，我们采用**键提取器（仿函数）**来统一处理：通过一个泛型接口提取 key，用同一颗红黑树同时支撑 map 和 set。 C++ 中的仿函数比 C 语言的函数指针更加灵活且类型安全。
接下来，我们基于红黑树进行 map 和 set 的具体封装。
2. map 和 set 的实现
2.1 基本框架与模板通用化
map 是 key-value 结构，set 是 key 结构。为了共用底层红黑树，我们需要将参数通用化：
// 原红黑树可能定义为 K, V
// 现在统一为 T，T 可以是 pair<K,V> 或 K
template <typename T>
class RBTree {
// ...
};
根据数据类型不同，分别编写对应的仿函数来控制底层获取 Key 的行为。
上层调用时传入仿函数对象，下层红黑树需新增一个模板参数接收该仿函数类型。
2.2 Insert 操作
原本的红黑树插入 KV 结构，现在只需传入 data。data 的类型可能是 pair<K,V> 也可能是 Key。创建仿函数对象后，即可提取出用于比较的 Key。
Insert 后续涉及 Key 比较大小，全部交由仿函数处理，形成回调机制。
这样就实现了通用的插入逻辑。
2.3 Find 操作
Find 同样依赖 Key 比较。由于 _data 类型不确定，依然需要仿函数来获取 Key 进行比较。
map 和 set 直接复用红黑树的 Insert 和 Find 方法。
2.4 迭代器 Iterator
map 和 set 的迭代器均由红黑树迭代器封装而成。虽然源码中迭代器实现较为复杂（包含继承关系），但核心思想一致：通过重载运算符使迭代器行为类似指针。
难点在于 ++ 和 -- 的实现。红黑树作为二叉搜索树，中序遍历输出结果有序。因此，红黑树迭代器也是遵循中序遍历（左 -根 -右）的顺序。
- begin: 返回中序遍历第一个结点（最左结点）。
- end: 返回空结点（通常是最右结点的父节点或哨兵）。
迭代器的 ++ 返回中序下一个节点，-- 返回上一个节点。局部解决了这两个操作，全局顺序自然成立。虽然逻辑不复杂，但代码分支较多，属于典型的'代码难点'而非'逻辑难点'。
例如，当走到 10 节点时，说明当前子树的左、根已遍历完，接下来访问右子树。中序访问右子树，必须先访问其最左节点。若 15 没有最左节点（它本身就是右子树的最左节点），则 ++it 结果为 15。
同理，若遍历到 18 节点，++it 即为右子树的最左节点 25。
若右子树为空呢？以 15 为例，其右子树为空且自身已遍历，需向上寻找祖先。15 是 10 的右子树，说明 10 也已遍历完，继续向上找。若找到某个祖先是其左子树，则该祖先即为下一个节点；若一直找不到直到根，则结束。
2.4.1 迭代器实现细节
红黑树内部使用迭代器：
上层（map 和 set）复用红黑树的迭代器。
注意模板未实例化时，取成员类型需加 typename 关键字。
迭代器的 -- 和 ++ 完全对称，区别在于寻找左父亲还是右父亲，end 的前一个节点即为最右结点。
2.5 Key 不能被修改的问题
对于 set，key 是不可变的。如果迭代器允许修改 key，红黑树的平衡性和查找功能将失效。因此必须从源头禁止修改。
最简单的做法是传递 const 引用：
上层传递 const Key 给红黑树，K 被 const 修饰后无法修改。
typedef 声明处也需加上 const，避免模板特化时的语义歧义报错。
对于 map，pair 中的 Key 同样不可变，处理方式一致。
2.6 修改 Find 返回值实现统计次数
将 Find 返回值改为 Iterator，配合其他逻辑可实现统计功能。
2.7 修改 Insert 返回值实现 operator[]
map 和 set 的 operator[] 底层依赖 Insert 的返回值。
newnode 保存新增结点 cur。因为插入过程涉及旋转和变色，向上更新后，最后的 cur 不一定是新增的原始结点。
解决完 Insert，接下来实现 operator[]：
逻辑如下：首先尝试插入 Key。如果插入失败（flag 为 false），说明 Key 已存在，it 指向已存在节点，返回 value；如果插入成功（flag 为 true），说明 Key 不存在，it 指向新增结点，返回 value。
外层对 value 执行 ++ 操作，即可轻松统计出现次数，无需额外复杂逻辑。
2.8 析构函数
map 和 set 的析构函数会调用红黑树的析构，因此无需单独编写。注意析构时应使用后序遍历，确保先销毁子节点再销毁父节点。
