基于红黑树封装 C++ map/set：源码级实现与核心逻辑解析

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 的析构函数会调用红黑树的析构，因此无需单独编写。注意析构时应使用后序遍历，确保先销毁子节点再销毁父节点。