对于C++：基于红黑树模拟实现C++set和map类的详细解析

开篇介绍：

hello 大家，那么在上篇博客中，我们完成了红黑树的实现，那么我们知道，在C++的STL库中，我们之前使用的set和map的底层就是红黑树，那么，我们怎么能不用我们自己实现的红黑树去模拟实现一下set和map呢？？？哈哈哈，接下来，就让我们开始！！！

在C++ STL标准库中，set和map是两大核心有序容器，它们的出现极大地简化了“有序存储”和“快速查找”场景的开发。很多初学者在使用这两个容器时，只关注其接口用法，却忽略了其底层的设计精髓——红黑树复用。

一、基础铺垫：搞懂3个核心问题，奠定实现基础

在动手实现set和map之前，我们必须先明确3个核心问题：为什么选择红黑树作为底层？set和map的核心差异是什么？如何通过技术手段实现红黑树的复用？这3个问题是后续实现的基石，理解透彻才能真正掌握底层逻辑。

1.1 为什么set和map要复用红黑树？

set和map的核心共性需求是有序性和key唯一性（multiset/multimap除外），而红黑树恰好完美匹配这两个需求，同时兼顾高效性和复用性，这也是STL选择红黑树作为其底层实现的核心原因。具体分析如下：

首先是有序性：红黑树是一种自平衡二叉搜索树，其核心特性是“中序遍历结果严格递增”。这个特性直接对应set的“有序key集合”和map的“有序key-value集合”——我们不需要额外做排序操作，只需通过中序遍历就能获得有序的数据序列，这正是set和map的核心诉求。

其次是高效性：普通二叉搜索树在最坏情况下会退化为链表，此时插入、删除、查找的时间复杂度会降到O(N)，无法满足容器的性能要求。而红黑树通过一套“变色+旋转”的自平衡机制，确保树的高度始终维持在O(logN)级别，因此这三个操作的时间复杂度都能稳定在O(logN)，既能满足日常开发的性能需求，又比AVL树的平衡调整成本更低（AVL树要求左右子树高度差不超过1，调整更频繁）。

最后是复用性：set存储“单一key”（如int、string），map存储“key-value对”（如pair<const K, V>），但两者的底层核心逻辑（搜索、插入、删除）完全一致，仅存在“数据存储类型”和“key比较方式”两个差异点。通过泛型编程和仿函数，我们可以让同一棵红黑树适配这两种场景，避免编写两套重复的红黑树代码，极大地提升代码复用率——这也是本文实现的核心思路。

1.2 set与map的核心差异：明确封装边界

虽然set和map复用红黑树，但两者的对外接口和功能定位存在明显差异，这些差异决定了我们在封装时的不同处理方式。我们通过“功能维度”对比，清晰梳理两者的核心区别：

1. 存储类型不同：set存储的是“单一key”，比如我们存储一组整数{1,3,5}，每个节点只需要保存一个int类型的值；而map存储的是“key-value键值对”，比如存储“姓名-年龄”映射，每个节点需要保存pair<string, int>类型的数据，其中first是key（姓名），second是value（年龄）。

2. 核心作用不同：set的核心作用是“去重+有序存储”，比如对一组重复数据去重后按升序排列；map的核心作用是“按key有序存储键值对，并支持通过key快速查找value”，比如根据姓名快速查询对应的年龄。

3. key可修改性不同：两者的key都不允许修改——因为红黑树的有序性依赖key的大小关系，修改key会直接破坏树的有序结构。具体来说，set的key本身就是存储的数据，因此直接限制为const类型；map的key是pair的first成员，因此将其定义为const K，确保无法修改，但value（pair的second成员）可以修改。

4. 独有操作不同：set的接口相对简单，只有基础的增删查改操作；而map最核心的独有操作是支持[]运算符，通过key可以快速插入键值对或访问value，比如map["张三"] = 20，这个操作的底层依赖红黑树的insert函数实现。

明确这些差异后，我们就知道：后续的红黑树改造需要解决“适配不同存储类型”和“统一key比较方式”两个问题，而set和map的封装则需要根据自身特性，通过不同的“仿函数”和“模板参数”适配改造后的红黑树。

1.3 红黑树复用的核心技术：泛型+仿函数

要让红黑树同时支持set和map，必须解决两个核心问题：一是“存储类型不确定”，二是“key比较方式不确定”。而泛型编程和仿函数正是解决这两个问题的关键技术，我们逐一拆解：

第一个问题：存储类型不确定。红黑树既可能存储set的“单一key”（如int），也可能存储map的“key-value对”（如pair<const K, V>）。如果我们为每种存储类型都写一套红黑树代码，会导致严重的代码冗余。此时泛型编程就能发挥作用——我们用模板参数T表示红黑树的存储类型，红黑树的所有操作都基于T进行，不关心T具体是什么类型。这样一来，一套红黑树代码就能适配任意存储类型，实现“类型无关”的复用。

第二个问题：key比较方式不确定。红黑树的核心操作（插入、查找）都需要通过key的大小关系判断方向（往左走还是往右走），但不同存储类型的key提取方式不同：set的存储类型T就是key，直接比较T即可；map的存储类型T是pair，需要提取pair的first成员（key）进行比较。如果在红黑树内部写死比较逻辑，就无法适配两种场景。

此时“仿函数”就能解决这个问题。仿函数本质是一个重载了()运算符的类，我们可以在红黑树中引入一个模板参数KeyOfT（表示“从T中提取key的方法”），红黑树通过调用KeyOfT的()运算符获取key，而具体的提取逻辑由上层的set或map实现。比如：set实现一个“直接返回T本身”的仿函数，map实现一个“返回T.first”的仿函数，红黑树只需调用KeyOfT()(data)就能统一获取key，实现“比较逻辑与存储类型解耦”。

这就是泛型+仿函数的魅力：红黑树只负责“按key有序存储数据”的核心逻辑，不关心T的具体类型，也不关心如何从T中提取key——这些细节都由上层的set和map通过模板参数传递进来，从而实现一套红黑树适配两种容器的复用目标。

二、核心实现：可复用红黑树的改造

普通红黑树只能存储固定类型（如int），无法直接复用。我们需要对其进行“模板化改造”，使其支持泛型参数T（存储类型）和KeyOfT（key提取仿函数），同时实现适配set和map的迭代器、插入等核心接口。这部分是整个实现的核心，我们分“节点改造”“迭代器实现”“核心操作改造”三个小节逐步拆解。

2.1 红黑树节点的改造：适配泛型与迭代器回溯

红黑树的节点是数据存储的基本单元，普通红黑树节点的存储类型是固定的，我们需要将其改造为模板类，同时为了支持迭代器的++/–操作，还需要增加“父节点指针”。我们先看改造后的节点结构逻辑（对应你提供的RBTreeNode结构体）：

改造后的节点类是模板类template <typename T> struct RBTreeNode，核心成员包括：

1. 存储数据：T _kv; 这里的T就是泛型参数，表示节点存储的数据类型（set的K或map的pair<const K, V>），用_kv命名是为了统一表示“key相关数据”（key或key-value对）。

2. 颜色标记：COLOR _color = RED; 红黑树节点的颜色，默认初始化为红色。这里要重点说明：为什么新节点默认是红色？因为红黑树有一条规则：“每个红色节点的两个子节点都是黑色”（规则4）。如果新节点是黑色，会直接破坏另一条规则：“从任一节点到其所有后代叶节点的简单路径上，黑色节点数相同”（规则5），修复这条规则的成本很高；而新节点是红色，只会在“父节点也是红色”时破坏规则4，修复成本更低——这是红黑树插入的核心优化点。

3. 指针成员：包括左孩子指针_left、右孩子指针_right，以及新增的父节点指针_parent。为什么需要_parent？因为迭代器的++/–操作需要“回溯祖先节点”（比如当前节点没有右子树时，需要沿着父节点找到第一个“当前节点是其左孩子”的祖先），没有父节点指针就无法实现这个回溯逻辑——这是迭代器实现的关键。

4. 构造函数：RBTreeNode(const T& kv)，通过传入的kv初始化_kv，同时将_left、_right、_parent置为nullptr，_color置为红色。这里的构造函数很简单，核心是适配T类型的通用性，无论T是int还是pair，都能通过拷贝构造初始化。

节点改造的核心目标：一是通过模板参数T适配不同存储类型，二是通过_parent指针支持迭代器回溯，这两个改造是后续复用的基础。

示例代码：

//红黑树的节点的颜色
enum COLOR
{
RED,
BLACK
};

//红黑树的节点类
//那么对于红黑树的节点，其实和AVL树的节点差不多，只不过多了个红黑树的节点的颜色
//那么其实想一想，set就是存储一种类型的数据，而map虽然是存储两种类型，但是本质上也是pair的类型
//所以，聪明的你其实很容易就能想到，红黑树可以就存储一种类型，我们假设是T
template <typename T>
struct RBTreeNode//因为全公开，所以直接使用struct类
{
T _kv=T();//大保底,红黑树节点所存储的数据就是这个了
int _color=RED;//红黑树的节点的颜色，默认新插入的节点就是红色的哦，至于原因在红黑树的插入函数那里再解释
RBTreeNode<T>* _right=nullptr;//节点的右孩子
RBTreeNode<T>* _left=nullptr;//节点的左孩子

// 这里更新控制平衡也要加入parent指针
RBTreeNode<T>* _parent=nullptr;//节点的父亲

//节点类的构造函数
RBTreeNode(const T& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_color(RED)
{}
};

2.2 红黑树迭代器的实现：核心难点突破

set和map的迭代器是“双向迭代器”，支持++、–、*、->等操作，且迭代顺序为中序遍历（保证有序性）。迭代器的本质是“封装节点指针”，通过重载运算符模拟指针的行为。这部分是整个实现的难点，尤其是++和–的逻辑，我们分“迭代器模板设计”“核心运算符重载”“++/–逻辑拆解”三个部分详细说明。

2.2.1 迭代器模板设计：复用普通与const迭代器

set和map都需要支持普通迭代器和const迭代器：普通迭代器可以修改value（map）或无法修改（set），const迭代器则完全无法修改。如果我们为两种迭代器写两套代码，会导致冗余——这和红黑树复用的思路相悖。因此，我们采用“模板参数复用”的设计，用三个模板参数实现一套代码适配两种迭代器（对应你提供的RBTreeIterator模板类）：

模板参数定义：template <typename T, typename REF, typename PTR> struct RBTreeIterator

三个参数的含义：

1. T：节点存储的数据类型（与红黑树的T一致）；

2. REF：引用类型，普通迭代器为T&，const迭代器为const T&——通过REF控制*运算符返回的引用是否可修改；

3. PTR：指针类型，普通迭代器为T*，const迭代器为const T*——通过PTR控制->运算符返回的指针是否可修改。

同时，我们在迭代器内部定义两个别名：using node = RBTreeNode<T>（简化节点类型名），using self = RBTreeIterator<T, REF, PTR>（简化迭代器自身类型名），让代码更简洁。

迭代器的核心成员变量：

1. node* _node：指向当前迭代器对应的红黑树节点——这是迭代器的核心，所有操作都围绕这个指针展开；

2. node* _root：指向红黑树的根节点——专门用于处理“–end()”的特殊情况（end()是nullptr，–end()需要找到整棵树的最右节点，这就需要从根节点开始遍历）。

迭代器的构造函数：RBTreeIterator(node* __node, node* root)，通过传入当前节点和根节点初始化成员变量，这个构造函数由红黑树的begin()和end()函数调用，用户无需直接使用。

2.2.2 核心运算符重载：模拟指针行为

迭代器需要重载*、->、==、!=四个基础运算符，模拟指针的访问和比较行为，这些运算符的逻辑相对简单，我们逐一拆解：

1. 重载*运算符：REF operator*() { return _node->_kv; }。作用是返回当前节点存储的数据的引用——对于普通迭代器，REF是T&，可以通过*it修改数据（set的T是const K，因此无法修改；map的T是pair<const K, V>，可以修改second）；对于const迭代器，REF是const T&，无法修改任何数据。

2. 重载->运算符：PTR operator->() { return &_node->_kv; }。作用是返回当前节点存储的数据的指针——主要用于map的迭代器访问pair的成员，比如it->first访问key，it->second访问value。这里有一个小细节：编译器会自动优化“->”的调用，比如it->first等价于(*it).first，我们只需返回数据的指针即可。

3. 重载==和!=运算符：bool operator==(const self& i) { return _node == i._node; }，bool operator!=(const self& i) { return _node != i._node; }。作用是比较两个迭代器是否指向同一个节点——因为迭代器的本质是封装节点指针，所以直接比较_node即可。

2.2.3 迭代器++实现：中序后继节点的查找

迭代器++的核心需求是“找到当前节点的中序后继节点”（中序遍历的下一个节点），因为中序遍历是严格递增的，这样才能保证迭代器的有序访问。中序遍历的顺序是“左子树→根节点→右子树”，因此后继节点的查找分两种情况，我们结合逻辑和例子详细说明：

情况1：当前节点有右子树。根据中序遍历规则，根节点的下一个节点是“右子树的中序第一个节点”，而右子树的中序第一个节点就是右子树的最左节点（因为左子树先于根节点访问）。比如：当前节点是10，右子树是{15,20}，右子树的最左节点是15，因此++it后指向15。

对应的逻辑：如果_node->_right不为空，先将_node指向右子树，然后循环向左遍历，直到找到最左节点（_node->_left为空）。

情况2：当前节点没有右子树。这说明当前节点所在的子树已经遍历完毕，需要沿着父节点回溯，寻找“第一个以当前节点为左孩子的祖先节点”——这个祖先节点就是后继节点。为什么？因为中序遍历是“左→根→右”，如果当前节点是父节点的左孩子，说明父节点的左子树已经遍历完毕，下一个就是父节点；如果当前节点是父节点的右孩子，说明父节点的右子树已经遍历完毕，需要继续向上回溯。

举个例子：当前节点是15，父节点是10，15是10的右孩子——说明10的右子树已经遍历完毕，继续回溯到10的父节点20；10是20的左孩子——说明20的左子树已经遍历完毕，下一个节点就是20，因此++it后指向20。

对应的逻辑：

1. 用cur保存当前节点，将_node指向父节点；

2. 循环判断：如果_node不为空，且cur是_node的右孩子，就继续回溯（cur更新为_node，_node更新为父节点）；

3. 循环结束后，_node就是后继节点（如果_node为空，说明已经遍历到树的末尾，即end()）。

总结++的核心逻辑：有右子树找右子树的最左节点，无右子树回溯找“左孩子祖先”。

2.2.4 迭代器–实现：中序前驱节点的查找

迭代器–的逻辑与++对称，核心需求是“找到当前节点的中序前驱节点”（中序遍历的前一个节点），中序前驱的查找分三种情况（包含–end()的特殊处理）：

特殊情况：当前节点是nullptr（即end()）。end()是迭代器的末尾标记，指向“最后一个有效节点的下一个位置”，因此–end()需要找到整棵树的最右节点（中序遍历的最后一个节点）。比如：整棵树是{10,15,20}，最右节点是20，因此–end()后指向20。对应的逻辑：从根节点开始，循环向右遍历，直到找到最右节点（_node->_right为空）。

情况1：当前节点有左子树。根据中序遍历规则，根节点的前一个节点是“左子树的中序最后一个节点”，而左子树的中序最后一个节点就是左子树的最右节点（因为右子树后于根节点访问）。比如：当前节点是15，左子树是{10,12}，左子树的最右节点是12，因此–it后指向12。对应的逻辑：如果_node->_left不为空，先将_node指向左子树，然后循环向右遍历，直到找到最右节点。

情况2：当前节点没有左子树。这说明当前节点所在的子树已经反向遍历完毕，需要沿着父节点回溯，寻找“第一个以当前节点为右孩子的祖先节点”——这个祖先节点就是前驱节点。逻辑与++的情况2对称：用cur保存当前节点，将_node指向父节点，循环判断如果_node不为空且cur是_node的左孩子，就继续回溯，直到找到目标祖先节点。

迭代器–的核心逻辑：是nullptr就找最右节点，有左子树找左子树的最右节点，无左子树回溯找“右孩子祖先”。

示例代码：

//实现一下迭代器类，那么之所以要用类模版，就是因为可以直接让编译器帮我们实现两套迭代器
//我们只需要传入不同的变量，就能让编译器帮我们实现普通迭代器和const迭代器
//这个在之前实现我们自己的list中也有提到过
template <typename T,typename REF,typename PTR>//REF是引用，PTR是指针
struct RBTreeIterator
{
using node=RBTreeNode<T>;
using self=RBTreeIterator<T,REF,PTR>;
//对节点类和迭代器类自己进行重命名，避免写一大堆不优雅

private:

node* _node;//传入迭代器所在的当前红黑树节点，迭代器类的核心，本质上获取迭代器就是为了获取该节点！！！
node* _root;//需要外界传入红黑树的根节点，是为了迭代器–而准备的

public:
//构造函数，在红黑树中传入迭代器所需的成员变量，用户是看不到的
RBTreeIterator(node* __node,node* root)
:_node(__node)
,_root(root)
{}

//重载迭代器的*运算符
//我们知道，我们平时对迭代器*一下就能获取到数据结构中所存储的数据
//所以在这里本质上当用户*一下，我们就得返回节点类中的数据

//其实是返回T&，但是上面说了为了让编译器帮我们生成两套迭代器，所以我们是用类模版，所以用REF替代T&
//那么外界传入T&时，就代表是普通迭代器，外界可以通过*修改节点中的数据
//而要是传入const T&的话，就代表是const迭代器，外界不可以通过*修改节点中的数据
//不用担心用户会修改掉key值，我们在map和set中传入的时候，就是传入const K哦，所以不必担心
REF operator*()
{
return _node->_kv;
}

//其实是返回T*，但是呢，和上面说的T&原因一样，所以这里不再赘述！！！
PTR operator->()
{
return &_node->_kv;
}

//重载一下==和!=运算符，用于比较两个迭代器是否是指向同一个节点
bool operator==(const RBTreeIterator<T,REF,PTR>& i)
{
return _node==i._node;
}

bool operator!=(const RBTreeIterator<T,REF,PTR>& i)
{
return _node!=i._node;
}

//实现迭代器的++，那么其实就是按照中序遍历去将节点走到中序遍历的下一个节点
//比较复杂，但是也还行，画图嗷嗷理解就完事了
//本质上就是中序遍历：左子树，根节点，右子树
//因为中序遍历的要求是左子树，根节点，右子树
//所以当迭代器对应某一个节点时，那么这个节点的左孩子是一定被遍历完了，不然是走不到这根节点（父节点）上的
//那么再想想，左子树下一个顺序应该是根（父）节点了，而此时它就是到了这个根（父）节点
//所以当前根节点的左子树和根节点都遍历完了，那么此时就是要情况讨论
//要是当当前的迭代器对应的节点有右孩子的话，那是不是就得进入当前根节点的右子树进行遍历了？？？
//那么就得先进入当前根节点的右孩子，然后可不是就这么停止了
//你得看这个当前根节点的右孩子是不是还有它的左子树，有的话，你还得先走到当前根节点的右孩子的左子树的最左的孩子
//因为你要满足左根右，而你当前根节点的右孩子也是相当于一个根节点，那么你得在走完你的左子树后才能去访问你
//所以就得先去在当前根节点的右孩子有左孩子的话嗷嗷去当前根节点的右孩子的左子树的最左的孩子
//而要是当前根节点的右孩子没有左子树，也就是它的左孩子为空的话
//那么就只能返回你了，也就是当前根节点的右孩子，因为要满足左根右，而你没有左孩子，所以就得走根，
//那么也就是你自己了，可不能走到你的右孩子去了，因为你都还没访问呢！！！
//上面的是第一种情况

//下面的是第二种情况：当前根节点没有右孩子，那么这代表什么？？？
//这就代表说对于你这个当前根节点而言，你这棵子树的中序遍历已经走完了，因为没有右，那么中序遍历终点就是根了
//但是你这个子树完了，不代表整颗树走完了，有可能你这个根节点只是你父节点的左孩子或者右孩子罢了，还得继续往上走
//那么要怎么走呢???那么如果当前根节点是它父节点的右孩子的话，那么你得继续往上更新，找新的祖先
//因为是右孩子的话，不是也代表说，你的父节点的这棵子树，中序遍历也走完了吗，左根右，仔细想想就知道了
//而要是左孩子的话，就代表说你的父节点的这棵子树，你只走完了左边子树，但是根（你的父节点）以及右边子树还没走
//那么按照中序遍历左根右的顺序，下一个要访问的就是根了，也就是你的父节点
//所以我们就能总结出来：
//如果当前根节点没有右孩子，那就一直往上找祖先，直到新的祖先是它（新的祖先）的父节点的左孩子为止
//返回（新的祖先）的父节点！！！
//所以这也是利用到我们节点类中设计的_parent！！！
//不用担心跑到最上面的根节点去怎么办，因为最上面的根节点的父节点就是nullptr

//还有就是要注意是返回迭代器自己哦，本质上只是对迭代器的_node进行更新！！！
self& operator++()
{
//就按照上面说的来
if(_node->_right)//当前根节点有右孩子
{
_node=_node->_right;
while(_node->_left)//存在左孩子的话，就一直去找左孩子
{
_node=_node->_left;
}
}
else//当前根节点没有右孩子
{
node* cur=_node;//设置节点标记孩子
_node=_node->_parent;
while(_node&&cur==_node->_right)//只要节点还是其父节点的右孩子，就一直更新，同时注意会对_node进行访问，所以要保证其不为空
{
//不断向上进行更新
cur=_node;
_node=_node->_parent;
}
}
return *this;//最后的结果就是迭代器中的_node已经更新完毕，所以我们返回迭代器本身！！！
}

//然后就是迭代器的–操作，其实也是很简单，如果能知道上面的++的思路的话
//那么理解–也就非常轻松，也就是和++的顺序反过来而已，把++中的左变成右，右变成左就行了
//大家自行理解，那么在这里主要是说明一下要是迭代器是map或者set的end()呢
//那么此时–一个怎么办，我们知道，迭代器中的end()其实就是指向最后一个有效数据的后面
//那么在红黑树这中节点类中，其实就是nullptr，这一点希望大家注意
//怎么说呢，因为它本质上就是对整棵树进行中序遍历结束后的下一个节点
//所以end()就是相当于树的最右的节点的右孩子，而这个孩子很明显是为空的
//那么我们对end()–之后，迭代器应该去哪里？？？
//很明显，就是去树的最右的节点！！！很简单的，大家自己模拟一下就知道了
//毕竟–就是相当于进行右根左的遍历
self& operator–()
{
if (_node == nullptr) // –end()
{
// –end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
//那么我们怎么去找到整颗树的最右节点呢？？？很明显，就是从根节点不断的往下走
//所以这也是为什么我们要给迭代器类传入_root的原因
node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left)
{
// 左子树不为空，中序左子树最后一个
node* rightMost = _node->_left;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else
{
// 孩子是父亲右的那个祖先
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}

return *this;
}

};

2.3 红黑树核心操作的改造：插入与平衡调整

红黑树的核心操作是插入，因为插入可能破坏红黑树的规则，需要进行平衡调整。改造后的插入函数需要支持泛型参数T和KeyOfT，同时返回pair<Iterator, bool>——这个返回值是map实现[]运算符的关键：bool表示插入成功（key不存在）或失败（key已存在），Iterator指向新插入的节点或已存在的节点。我们分“插入流程”“平衡调整”“仿函数的应用”三个部分拆解。

2.3.1 插入函数的模板设计与返回值

改造后的红黑树类是模板类：template <typename T, typename KeyofT> class RBTree。其中T是存储类型，KeyofT是提取key的仿函数。插入函数的声明为：std::pair<Iterator, bool> Insert(const T& data)。

为什么返回pair<Iterator, bool>？因为set和map都要求“key唯一”，插入时需要告知用户是否插入成功：如果key已存在，插入失败，返回已存在节点的迭代器和false；如果key不存在，插入成功，返回新节点的迭代器和true。对于map的[]运算符，我们需要利用这个返回值——无论插入成功与否，都能通过迭代器访问到对应的value。

2.3.2 插入流程：从查找位置到节点插入

插入流程与普通红黑树类似，核心差异是通过仿函数提取key进行比较，我们分步骤拆解：

步骤1：空树处理。如果红黑树为空（_root == nullptr），直接创建新节点作为根节点，将根节点的颜色置为黑色（红黑树规则1：根节点是黑色），然后返回pair<Iterator(_root, _root), true>。

步骤2：查找插入位置。用cur指针从根节点开始遍历，parent指针记录cur的父节点。遍历过程中，通过仿函数KeyofT koft;提取当前节点和插入数据的key（koft(cur->_kv)和koft(data)），比较key的大小：

– 如果当前节点的key < 插入数据的key：cur向右子树移动；

– 如果当前节点的key > 插入数据的key：cur向左子树移动；

– 如果key相等：插入失败，返回pair<Iterator(cur, _root), false>。

步骤3：插入新节点。当cur遍历到nullptr时，parent就是新节点的父节点。创建新节点（默认红色），根据key的大小关系将新节点插入到parent的左孩子或右孩子位置，同时设置新节点的_parent为parent。

步骤4：保存新节点。因为后续的平衡调整可能会修改cur指针（比如旋转后cur的位置变化），所以我们用newnode变量保存新插入的节点，方便后续返回迭代器。

2.3.3 平衡调整：变色+旋转的核心逻辑

插入新节点后，可能会破坏红黑树的规则4（红色节点的子节点是黑色）——只有当父节点是红色时才需要调整（父节点是黑色则不会破坏规则）。平衡调整的核心思路是“通过变色或旋转恢复红黑树规则”，具体分两种大情况（父节点是祖父节点的左孩子或右孩子），每种情况又分两个子情况（叔叔节点是红色/黑色），我们以“父节点是祖父左孩子”为例详细说明：

首先明确几个关键节点：parent（父节点，红色）、grandfather（祖父节点，黑色，因为父节点是红色，祖父节点不可能是红色，否则插入前就违反规则）、uncle（叔叔节点，祖父节点的右孩子）。

子情况1：叔叔节点存在且为红色。此时只需通过“变色”就能恢复规则：将parent和uncle置为黑色，grandfather置为红色。为什么？因为祖父节点原本是黑色，parent和uncle是红色，变色后，祖父节点所在路径的黑色节点数不变（祖父节点从黑变红，parent/uncle从红变黑，总黑色节点数不变），同时解决了“父节点红色”的问题。之后需要将cur更新为grandfather，parent更新为cur的父节点，继续向上调整（因为grandfather变红后，可能与它的父节点形成红色父子对）。

子情况2：叔叔节点不存在或为黑色。此时需要通过“旋转+变色”恢复规则，具体又分两种子情况：

1. 新节点是parent的左孩子（LL型）：对祖父节点进行右旋转，然后将parent置为黑色，grandfather置为红色。右旋转的作用是“降低树的高度，调整节点位置”，变色则是为了恢复规则4——旋转后parent成为祖父节点的父节点，parent置为黑色，grandfather置为红色，确保红色节点的子节点是黑色。

2. 新节点是parent的右孩子（LR型）：先对parent进行左旋转，将LR型转化为LL型，然后对祖父节点进行右旋转，最后将新节点置为黑色，grandfather置为红色。为什么要先旋转parent？因为LR型是“父节点左孩子的右孩子”，直接旋转祖父节点无法解决问题，需要先将其转化为LL型（左孩子的左孩子），再用LL型的调整方法处理。

当“父节点是祖父节点的右孩子”时，逻辑与上述对称：叔叔节点是祖父的左孩子，子情况1同样是变色，子情况2分RR型（新节点是parent的右孩子，左旋转祖父）和RL型（先右旋转parent，再左旋转祖父），变色逻辑也对称。

最后一个关键步骤：无论调整过程如何，都要将根节点强制置为黑色。因为调整过程中可能会将根节点置为红色（比如子情况1中grandfather是根节点，变色后变红），违反规则1，所以最后强制将_root->_color = BLACK。

2.3.4 仿函数的核心作用：解耦key提取逻辑

在整个红黑树的插入和查找过程中，仿函数KeyofT扮演了“桥梁”的角色，实现了“红黑树与存储类型的解耦”。我们通过两个例子说明仿函数的具体作用：

例子1：set的仿函数。set的存储类型T是K（如int），仿函数的逻辑是“直接返回T本身”，比如：

//实现set的仿函数，能获取到传入的参数的key值，然后再去进行比较
//因为红黑树就存储一种类型，具体可以看红黑树头文件中所解析的
struct keyofkey
{
//那么是需要外界传入K类型的数据的，这样子我们函数内部才能去获取到传入的参数的key值，
const K& operator()(const K& k) const
{
return k;
}
};

当红黑树处理set的插入时，koft(cur->_kv)就是cur->_kv（int类型），直接比较两个int即可。

例子2：map的仿函数。map的存储类型T是pair<const K, V>，仿函数的逻辑是“返回pair的first成员（key）”，比如：

//实现map的仿函数，能获取到传入的参数的key值——T.first，然后再去进行比较
//因为红黑树就存储一种类型，具体可以看红黑树头文件中所解析的
struct keyofpair
{
//那么是需要外界传入pair结构体的，这样子我们函数内部才能去获取到传入的参数的key值，
//也就是pair.first
const V& operator()(std::pair<const K,V>& kv) const
{
return kv.first;
}
};

当红黑树处理map的插入时，koft(cur->_kv)就是cur->_kv.first（K类型），通过key比较方向，完全不关心value是什么。

正是因为仿函数的存在，红黑树不需要知道T的具体类型，只需调用koft()就能获取key，从而实现一套代码适配set和map的复用目标。

2.4 红黑树的其他核心操作：拷贝构造、析构与查找

为了让红黑树更完整，我们还需要实现拷贝构造、析构函数、查找等操作，这些操作是容器的基础要求，我们简要说明核心逻辑：

1. 拷贝构造函数：RBTree(const RBTree<T, KeyofT>& a)。核心逻辑是“前序遍历拷贝节点”：从根节点开始，递归拷贝每个节点的_kv、_color，同时设置父节点指针（确保拷贝后的树结构正确）。用copy函数实现递归拷贝，copy函数接收当前节点和父节点，返回拷贝后的新节点。

2. 析构函数：~RBTree()。核心逻辑是“后序遍历释放节点”：先递归释放左子树，再递归释放右子树，最后释放当前节点，避免内存泄漏。用destroy函数实现递归释放，destroy函数接收节点的引用，释放后将节点置为nullptr（避免野指针）。

3. 查找函数：bool Find(const T& t) 和 const node* Find_Node(const T& t)。核心逻辑与插入的“查找位置”步骤一致：通过仿函数提取key，遍历树查找匹配的key，找到返回true或节点指针，找不到返回false或nullptr。Find函数用于判断key是否存在，Find_Node函数用于返回节点指针（方便上层容器访问value）。

底层示例代码：

#include <iostream>
#include <cassert>
#include <algorithm>
#include <utility>

//那么在本文件中，我们就修改一下我们的红黑树的实现
//使其能够用于set和map的实现
//先复习一下，set就是存储key的红黑树
//map就是存储key和value，也就是pair<key,value>
//那么由于两个数据结构存储的数据不同，那难道说要我们去用两份红黑树代码吗？？
//这很明显很浪费，那么想想看我们之前学过自己实现list中迭代器的利用模版巧妙的让编译器帮我们生成两份迭代器类
//不错，在我们自己实现map和set的过程中，我们也可以使用这个方法！！！
//那么其实想一想，set就是存储一种类型的数据，而map虽然是存储两种类型，但是本质上也是pair的类型
//所以，聪明的你其实很容易就能想到，红黑树可以就存储一种类型，我们假设是T
//只不过set存储的是int等等，而map存储的是pair！！！
//但是这么一来，还有一个问题，那就是红黑树的插入，得比较key值啊！！！
//那么你set很简单，存储的类型就是key，可以直接进行比较，cur->data<等等形参->data
//而你map是pair类型啊，就不能直接进行比较：cur->data<等等形参->data
//得是cur->data.first 等等 形参->data.first
//那么这个要怎么办呢？？？其实还是很好想到的，就是借用仿函数
//在set中，我们传入的就是获取到T本身的值，然后去进行比较
//而在map中，我们就要实现仿函数能获取到T.second，然后再去进行比较
//两个不同的容器，就传入不同的仿函数，对应不同的获取数据进行比较

//红黑树的节点的颜色
enum COLOR
{
RED,
BLACK
};

//红黑树的节点类
//那么对于红黑树的节点，其实和AVL树的节点差不多，只不过多了个红黑树的节点的颜色
//那么其实想一想，set就是存储一种类型的数据，而map虽然是存储两种类型，但是本质上也是pair的类型
//所以，聪明的你其实很容易就能想到，红黑树可以就存储一种类型，我们假设是T
template <typename T>
struct RBTreeNode//因为全公开，所以直接使用struct类
{
T _kv=T();//大保底,红黑树节点所存储的数据就是这个了
int _color=RED;//红黑树的节点的颜色，默认新插入的节点就是红色的哦，至于原因在红黑树的插入函数那里再解释
RBTreeNode<T>* _right=nullptr;//节点的右孩子
RBTreeNode<T>* _left=nullptr;//节点的左孩子

// 这里更新控制平衡也要加入parent指针
RBTreeNode<T>* _parent=nullptr;//节点的父亲

//节点类的构造函数
RBTreeNode(const T& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_color(RED)
{}
};

//实现一下迭代器类，那么之所以要用类模版，就是因为可以直接让编译器帮我们实现两套迭代器
//我们只需要传入不同的变量，就能让编译器帮我们实现普通迭代器和const迭代器
//这个在之前实现我们自己的list中也有提到过
template <typename T,typename REF,typename PTR>//REF是引用，PTR是指针
struct RBTreeIterator
{
using node=RBTreeNode<T>;
using self=RBTreeIterator<T,REF,PTR>;
//对节点类和迭代器类自己进行重命名，避免写一大堆不优雅

private:

node* _node;//传入迭代器所在的当前红黑树节点，迭代器类的核心，本质上获取迭代器就是为了获取该节点！！！
node* _root;//需要外界传入红黑树的根节点，是为了迭代器–而准备的

public:
//构造函数，在红黑树中传入迭代器所需的成员变量，用户是看不到的
RBTreeIterator(node* __node,node* root)
:_node(__node)
,_root(root)
{}

//重载迭代器的*运算符
//我们知道，我们平时对迭代器*一下就能获取到数据结构中所存储的数据
//所以在这里本质上当用户*一下，我们就得返回节点类中的数据

//其实是返回T&，但是上面说了为了让编译器帮我们生成两套迭代器，所以我们是用类模版，所以用REF替代T&
//那么外界传入T&时，就代表是普通迭代器，外界可以通过*修改节点中的数据
//而要是传入const T&的话，就代表是const迭代器，外界不可以通过*修改节点中的数据
//不用担心用户会修改掉key值，我们在map和set中传入的时候，就是传入const K哦，所以不必担心
REF operator*()
{
return _node->_kv;
}

//其实是返回T*，但是呢，和上面说的T&原因一样，所以这里不再赘述！！！
PTR operator->()
{
return &_node->_kv;
}

//重载一下==和!=运算符，用于比较两个迭代器是否是指向同一个节点
bool operator==(const RBTreeIterator<T,REF,PTR>& i)
{
return _node==i._node;
}

bool operator!=(const RBTreeIterator<T,REF,PTR>& i)
{
return _node!=i._node;
}

//实现迭代器的++，那么其实就是按照中序遍历去将节点走到中序遍历的下一个节点
//比较复杂，但是也还行，画图嗷嗷理解就完事了
//本质上就是中序遍历：左子树，根节点，右子树
//因为中序遍历的要求是左子树，根节点，右子树
//所以当迭代器对应某一个节点时，那么这个节点的左孩子是一定被遍历完了，不然是走不到这根节点（父节点）上的
//那么再想想，左子树下一个顺序应该是根（父）节点了，而此时它就是到了这个根（父）节点
//所以当前根节点的左子树和根节点都遍历完了，那么此时就是要情况讨论
//要是当当前的迭代器对应的节点有右孩子的话，那是不是就得进入当前根节点的右子树进行遍历了？？？
//那么就得先进入当前根节点的右孩子，然后可不是就这么停止了
//你得看这个当前根节点的右孩子是不是还有它的左子树，有的话，你还得先走到当前根节点的右孩子的左子树的最左的孩子
//因为你要满足左根右，而你当前根节点的右孩子也是相当于一个根节点，那么你得在走完你的左子树后才能去访问你
//所以就得先去在当前根节点的右孩子有左孩子的话嗷嗷去当前根节点的右孩子的左子树的最左的孩子
//而要是当前根节点的右孩子没有左子树，也就是它的左孩子为空的话
//那么就只能返回你了，也就是当前根节点的右孩子，因为要满足左根右，而你没有左孩子，所以就得走根，
//那么也就是你自己了，可不能走到你的右孩子去了，因为你都还没访问呢！！！
//上面的是第一种情况

//下面的是第二种情况：当前根节点没有右孩子，那么这代表什么？？？
//这就代表说对于你这个当前根节点而言，你这棵子树的中序遍历已经走完了，因为没有右，那么中序遍历终点就是根了
//但是你这个子树完了，不代表整颗树走完了，有可能你这个根节点只是你父节点的左孩子或者右孩子罢了，还得继续往上走
//那么要怎么走呢???那么如果当前根节点是它父节点的右孩子的话，那么你得继续往上更新，找新的祖先
//因为是右孩子的话，不是也代表说，你的父节点的这棵子树，中序遍历也走完了吗，左根右，仔细想想就知道了
//而要是左孩子的话，就代表说你的父节点的这棵子树，你只走完了左边子树，但是根（你的父节点）以及右边子树还没走
//那么按照中序遍历左根右的顺序，下一个要访问的就是根了，也就是你的父节点
//所以我们就能总结出来：
//如果当前根节点没有右孩子，那就一直往上找祖先，直到新的祖先是它（新的祖先）的父节点的左孩子为止
//返回（新的祖先）的父节点！！！
//所以这也是利用到我们节点类中设计的_parent！！！
//不用担心跑到最上面的根节点去怎么办，因为最上面的根节点的父节点就是nullptr

//还有就是要注意是返回迭代器自己哦，本质上只是对迭代器的_node进行更新！！！
self& operator++()
{
//就按照上面说的来
if(_node->_right)//当前根节点有右孩子
{
_node=_node->_right;
while(_node->_left)//存在左孩子的话，就一直去找左孩子
{
_node=_node->_left;
}
}
else//当前根节点没有右孩子
{
node* cur=_node;//设置节点标记孩子
_node=_node->_parent;
while(_node&&cur==_node->_right)//只要节点还是其父节点的右孩子，就一直更新，同时注意会对_node进行访问，所以要保证其不为空
{
//不断向上进行更新
cur=_node;
_node=_node->_parent;
}
}
return *this;//最后的结果就是迭代器中的_node已经更新完毕，所以我们返回迭代器本身！！！
}

//然后就是迭代器的–操作，其实也是很简单，如果能知道上面的++的思路的话
//那么理解–也就非常轻松，也就是和++的顺序反过来而已，把++中的左变成右，右变成左就行了
//大家自行理解，那么在这里主要是说明一下要是迭代器是map或者set的end()呢
//那么此时–一个怎么办，我们知道，迭代器中的end()其实就是指向最后一个有效数据的后面
//那么在红黑树这中节点类中，其实就是nullptr，这一点希望大家注意
//怎么说呢，因为它本质上就是对整棵树进行中序遍历结束后的下一个节点
//所以end()就是相当于树的最右的节点的右孩子，而这个孩子很明显是为空的
//那么我们对end()–之后，迭代器应该去哪里？？？
//很明显，就是去树的最右的节点！！！很简单的，大家自己模拟一下就知道了
//毕竟–就是相当于进行右根左的遍历
self& operator–()
{
if (_node == nullptr) // –end()
{
// –end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
//那么我们怎么去找到整颗树的最右节点呢？？？很明显，就是从根节点不断的往下走
//所以这也是为什么我们要给迭代器类传入_root的原因
node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left)
{
// 左子树不为空，中序左子树最后一个
node* rightMost = _node->_left;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else
{
// 孩子是父亲右的那个祖先
node* cur = _node;
node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}

return *this;
}

};

//红黑树类
//那么只需要要传入一个T类型的数据就行，同时还要传入仿函数对应不同（map和set）的获取数据进行比较
template <typename T,typename KeyofT>//后面一个便是仿函数
class RBTree
{
public:
using node=RBTreeNode<T>;

//在红黑树类里面封装迭代器函数
//遍历与在map和set里面可以忽略底层直接调用获得迭代器

//普通迭代器，传入T，T&，T*
using Iterator=RBTreeIterator<T,T&,T*>;

//const迭代器，传入T,const T&,const T*
using ConstIterator=RBTreeIterator<T,const T&,const T*>;

//普通迭代器的begin()函数，那么就是整棵树的最左节点了
//依旧是从根节点出发一路找就完事了，返回的是也是迭代器类变量
Iterator begin()
{
node* leftmost=_root;
while(leftmost&&leftmost->_left)//注意不能走到空
{
leftmost=leftmost->_left;//一路往左走
}

// return Iterator ret(leftmost,_root);

//返回迭代器变量，我们可以直接隐式转换
return {leftmost,_root};

}

//普通迭代器的end()函数，那么其实就是nullptr
//我们知道，迭代器中的end()其实就是指向最后一个有效数据的后面
//那么在红黑树这中节点类中，其实就是nullptr，这一点希望大家注意
//怎么说呢，因为它本质上就是对整棵树进行中序遍历结束后的下一个节点
//所以end()就是相当于树的最右的节点的右孩子，而这个孩子很明显是为空的
Iterator end()
{
//我们直接返回为nullptr的迭代器类就行了
return {nullptr,_root};
}

//const迭代器的cbegin()函数，那么就是整棵树的最左节点了
//依旧是从根节点出发一路找就完事了，返回的是也是迭代器类变量
ConstIterator cbegin()
{
node* leftmost=_root;
while(leftmost&&leftmost->_left)//注意不能走到空
{
leftmost=leftmost->_left;//一路往左走
}

// return Iterator ret(leftmost,_root);

//返回迭代器变量，我们可以直接隐式转换
return {leftmost,_root};
}

//const迭代器的cend()函数
ConstIterator cend()
{
//我们直接返回为nullptr的迭代器类就行了
return {nullptr,_root};
}

//编译器自动生成的二叉搜索树类的无参构造函数就够用了
//但是由于我们下面写了拷贝构造函数，所以编译器就不帮我们生成构造函数了
//所以我们可以用default强制执行
RBTree() = default;

//实现二叉搜索树类的拷贝构造函数
RBTree(const RBTree<T,KeyofT>& a)
{
//得去将传过来的二叉搜索树的节点一个一个插入this
//用到前序遍历去进行插入
//那么这个就在下面的copy函数实现好了
this->_root = copy(a._root);
}

//实现二叉搜索树类的=运算符重载函数
RBTree<T,KeyofT>& operator=(const RBTree<T,KeyofT>& b)
{
//现代写法直接秒
RBTree<T,KeyofT> temp(b);

std::swap(this->_root, temp._root);

return *this;//连续赋值
}

//实现二叉搜索树类的析构函数
~RBTree()
{
//使用后序遍历进行释放节点
destroy(_root);//直接利用我们下面写的destory函数进行释放节点
_root = nullptr;
}

//红黑树的重点：插入节点
//那么在该函数中，我们不仅要有节点的颜色的修改
//更要有按照相对应的情况进行左旋（RR型），右旋（LL型），左右双旋（LR型），右左双旋（RL型）+颜色修改
//当然最重要的就是红黑树默认新插入的节点的颜色就是红色的
//因为这样子的话就一定不会违反红黑树的第四条规则
//至于第二、三条规则的违反是没事的，比较好修回去
//第四条规则的违反就不会修改了
//所以要牢记，红黑树默认新插入的节点的颜色就是红色的！！！

//修改红黑树的insert函数的返回值，符合stl风格，且为[]运算符重载作铺垫
//成功了就返回新插入节点的迭代器和true，失败了就返回已经存在的节点的迭代器和false
std::pair<Iterator,bool> Insert(const T& data)
{
//红黑树的前面的插入工作是和二叉搜索树的插入工作一样的

node* cur = _root;//定义cur指针，最终指向要插入到的节点为止
node* parent = nullptr;//定义parent指针，代表cur的父节点

//创建仿函数变量
//用于获取到set和map对应的key值
//依旧是具体解析看上面
KeyofT koft;

if (_root == nullptr)//如果是一棵空树，那么直接把新节点设置为整棵树的根节点即可
{
//在确定了要插入之后，再去new
node* newnode = new node(data);//新节点，直接构造就完事了

//最上面一层根节点的颜色要为黑色的哦、
newnode->_color=BLACK;

//把新节点赋值给最上面一层根节点
_root = newnode;

//return std::make_pair(Iterator{_root, _root}, true);

return {{_root,_root},true};//依旧是使用隐式转换，就这个爽
}
else//不是空树
{
while (cur != nullptr)
{
if (koft(cur->_kv) < koft(data))//使用仿函数,比较key值
{
//那就让cur指针往它的右子树去
parent = cur;
cur = cur->_right;
}
else if (koft(data) < koft(cur->_kv))//使用仿函数,比较key值
{
//那就让cur指针往它的左子树去
parent = cur;
cur = cur->_left;
}
else if (koft(cur->_kv) == koft(data))//使用仿函数,比较key值
{
return {{cur,_root},false};//依旧是使用隐式转换，就这个爽
}
}
//出了循环之后，cur指向nullptr，也是它要在的位置，
//而parent指向新插入节点最终在红黑树树中的位置的父节点
//比较parent节点和要插入数据key值
//然后根据比较结果进行插入
if (koft(parent->_kv) > koft(data))//使用仿函数,比较key值
{
cur = new node(data);//新节点，直接构造就完事了，把它给cur指针
cur->_color=RED;//红黑树默认新插入的节点的颜色就是红色的
parent->_left = cur;//放入parent的左孩子
}
else if (koft(data) > koft(parent->_kv))//使用仿函数,比较key值
{
cur = new node(data);//新节点，直接构造就完事了，把它给cur指针
cur->_color=RED;//红黑树默认新插入的节点的颜色就是红色的
parent->_right = cur;//放入parent的右孩子
}
else
{
assert(false);//其实压根不会出现这个情况，但是为了彰显我们的专业性，所以随便加上
}
}

cur->_parent = parent;//把新节点里的父节点指针更新为parent

//最后在恢复平衡后，我们也要返回新插入节点的迭代器，
//但是问题是在我们恢复的过程中，会改变cur值，所以我们得在上面先保存一下cur的值，即保存新插入的节点
node* newnode=cur;

//接下来我们就进行插入代码的书写
while(parent&&parent->_color==RED)//因为条件判断就会访问parent节点，所以我们前面得加上保证节点不为空
{
//获取祖父节点
node* grandfather=parent->_parent;

//父节点是祖父节点的左孩子，LR或者LL型
if(parent==grandfather->_left)
{
//获取uncle节点
//uncle为祖父的右孩子
node* uncle=grandfather->_right;
//uncle存在且为红色
if(uncle&&uncle->_color==RED)
{
//只需要变色就完事了
//uncle变为黑，parent变为黑，grandparent变为红
uncle->_color=BLACK;
parent->_color=BLACK;
grandfather->_color=RED;

//向上更新cur和parent节点，因为可能上面会出现红红
//记得是把cur更新到祖父节点那里去，可不是父节点
//我们已经把祖父节点下的子树处理好了
cur=grandfather;
parent=cur->_parent;
}
//uncle不存在或者颜色为黑色
else if(!uncle||uncle->_color==BLACK)
{
//新插入节点是在父节点的左孩子，单旋+变色
if(cur==parent->_left)
{
//对祖父节点进行右单旋+变色
RotateR(grandfather);

//叔叔节点不用管，因为它甚至都可以不存在，所以不用对它变色
//父节点变为黑色,因为进入到这里它一定是红色的,
//祖父节点颜色变为红色，因为一开始它是黑色的，后面它变为父节点的孩子
//且父节点为黑了，那么为了规则4，它就得由原本的黑变为红
//孩子节点颜色不用变
parent->_color=BLACK;
grandfather->_color=RED;

break;//停止循环，因为已经符合四条规则了，原因在上面
}
//新插入节点是在父节点的右孩子（LR），双旋+变色
else if(cur==parent->_right)
{
//先对父节点进行左单旋
RotateL(parent);
//再对祖父节点进行右单旋
RotateR(grandfather);

//然后变色
//那么就是新插入的节点变为新的祖父节点了
//而原本的祖父节点是黑色的，所以新插入的节点修改颜色为黑色
//而原本的祖父节点变为原本的新插入的节点的孩子
//所以要把它修改为红色，它原本是为黑色的
grandfather->_color=RED;
cur->_color=BLACK;

break;//停止循环，因为已经符合四条规则了，原因在上面
}
}
}
//父节点是祖父节点的右孩子，RL或者RR型
else if(parent==grandfather->_right)
{
//uncle为祖父的左孩子
node* uncle=grandfather->_left;
//那么其实剩下的步骤和上面的差不多
// 情况1：uncle存在且为红色 → 仅变色
if(uncle && uncle->_color == RED)
{
// 变色逻辑：uncle黑、parent黑、grandfather红
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;

// 向上更新节点（和左分支逻辑一致）
cur = grandfather;
parent = cur->_parent;
}
// 情况2：uncle不存在或颜色为黑色 → 旋转变色
else if(!uncle || uncle->_color == BLACK)
{
// 子情况1：cur是parent的右孩子（RR型）→ 单旋+变色
if(cur == parent->_right)
{
// 对祖父节点进行左单旋（与右旋对称）
RotateL(grandfather);

// 变色逻辑：parent黑、grandfather红（和LL型对称）
parent->_color = BLACK;
grandfather->_color = RED;

break; // 修复完成，终止循环
}
// 子情况2：cur是parent的左孩子（RL型）→ 双旋+变色
else if(cur == parent->_left)
{
// 先对父节点进行右单旋（与左旋对称）
RotateR(parent);
// 再对祖父节点进行左单旋
RotateL(grandfather);

// 变色逻辑：cur黑、grandfather红（和LR型对称）
grandfather->_color = RED;
cur->_color = BLACK;

break; // 修复完成，终止循环
}
}
}
}

_root->_color=BLACK;//最后直接再暴力让树的最上面的根节点颜色为黑！！！

//最后在恢复平衡后，我们也要返回新插入节点的迭代器，
//但是问题是在我们恢复的过程中，会改变cur值，所以我们得在上面先保存一下cur的值，即保存新插入的节点
return {{newnode,_root},true};
}

//提供一下树的常规操作
//直接从AVL树那里cv一下

//实现红黑树的查找功能，其实和二叉搜索树的查找功能实现方法一样
//这个其实就是真的很简单了
//就是看要查找的值有没有在二叉搜索树里面，
//那么先设置一个指针cur，然后按照二叉搜索树的性质去进行cur的移动
//如果要查找的值大于cur的话
//cur就进入它的右子树，要是要查找的值小于cur的话，cur就进入它的左子树
//重复上面操作不断比较，直到cur移动到值与要查找的值相同的节点，代表找到
//或者cur运动到nullptr，此时就代表cur无路可去，即没找到

//那么find函数的本质也是比较key值，所以我们也得利用仿函数

bool Find(const T& t)//设置返回值为bool，判断是否找到
{
//创建仿函数类变量
KeyofT koft;
node* cur = _root;//从整棵树的最上面的根节点开始寻找
while (cur != nullptr)
{
if (koft(t) < koft(cur->_kv))//使用仿函数
{
cur = cur->_left;
}
else if (koft(t) > koft(cur->_kv))//使用仿函数
{
cur = cur->_right;
}
else//即相等了，代表找到
{
return true;
}
}
return false;//出了循环就代表没找到
}

//也可以重载返回找到节点的find函数，可通过节点访问对应的value
const node* Find_Node(const T& t) const
{
//创建仿函数类变量
KeyofT koft;
node* cur = _root;//从整棵树的最上面的根节点开始寻找
while (cur != nullptr)
{
if (koft(t) < koft(cur->_kv))//使用仿函数
{
cur = cur->_left;
}
else if (koft(t) > koft(cur->_kv))//使用仿函数
{
cur = cur->_right;
}
else//即相等了，代表找到
{
return cur;
}
}
return nullptr;//出了循环就代表没找到
}

//中序遍历，证明二叉搜索树的有序性
void InOrder() const
{
//直接调用我们已经封装好的中序遍历就行，传入根节点指针
_inorder(_root);
}

int Height()
{
return _RBTreeHeight(_root);
}

private:
//先来个中序遍历，证明二叉搜索树的有序性
//同样记得是封装一个不用传入根节点的中序遍历函数出来
void _inorder(const node* root) const
{
if (root == nullptr)
{
return;
}
//中序遍历：左子树，根节点，右子树
_inorder(root->_left);
//std::cout << "key值：" << root->_kv.first << "value值：" << root->_kv.second << std::endl;
KeyofT koft;
std::cout << "key值：" << koft(root->_kv) << std::endl;//使用仿函数获取key值
_inorder(root->_right);
}

//获取到树的高度的函数，其实很简单，之前就已经实现过了
//本质是使用后序遍历，找根节点中左子树和右子树中较大的那一个+1
//补充：空树高度为0，叶子节点高度为1（符合AVL树节点高度定义）
int _RBTreeHeight(node* root)
{
if (root == nullptr)
{
return 0;
}

int leftheight = _RBTreeHeight(root->_left);
int rightheight = _RBTreeHeight(root->_right);

//return (leftheight > rightheight ? leftheight + 1 : rightheight + 1);
return std::max(leftheight, rightheight) + 1;
}

void destroy(node*& root)
{
if (root == nullptr)
{
return;
}

//使用后序遍历
destroy(root->_left);
destroy(root->_right);
delete root;
//最后要将root置为空指针，避免成为野指针
//那么这也就要求我们要把形参设置为引用
root = nullptr;
}

node* copy(const node* root, node* parent = nullptr)// 新增 parent 参数，传递父节点
{
if (root == nullptr)
{
return nullptr;
}

// 1. 复制原节点的_kv
node* newroot = new node(root->_kv);
newroot->_color = root->_color; //复制节点颜色
newroot->_parent = parent; // 设置父节点指针

// 2. 递归复制左/右子树，传递当前 newroot 作为子节点的父节点
newroot->_left = copy(root->_left, newroot);
newroot->_right = copy(root->_right, newroot);

return newroot;
}

//因为红黑树也是要用到旋转的，但是它的旋转和AVL树的旋转又是一样的
//都是左啊右啊什么什么的
//所以呢
//我们直接copy就完事了
//毕竟旋转其实也挺好写的

//第一种情况：LL型，即新插入节点在失衡节点的左孩子的左子树中
//进行右单旋
void RotateR(node* parent)
{
assert(parent);//检验是否传入空指针
assert(parent->_left && "LL型失衡节点无左孩子！");

//失衡节点是该函数的参数，由外界传入
node* subl = parent->_left;
node* sublr = parent->_left->_right;
//无论失衡节点的左孩子的右孩子为不为空
//（即无论该节点为不为nullptr）
//都得把该孩子纳为失衡节点的左孩子（最终的平衡的树）
//而要是该孩子不为nullptr的话，那么得把该孩子的parent进行更新，换为失衡节点
parent->_left = sublr;
if (sublr != nullptr)
{
//同时把失衡节点的左孩子的右孩子的_parent指针进行更新
sublr->_parent = parent;
}
//然后将失衡节点的左孩子的右孩子修改为失衡节点
subl->_right = parent;
//那么在最后失衡节点的左孩子会变为原本的失衡节点的整颗子树的新的根节点
//所以要判断原本的失衡节点是不是整棵树的根节点
//是的话,那么就把整棵树的root赋值为失衡节点的左孩子
//不是的话，那么就看原本的失衡节点是它的父节点的左孩子还是右孩子，所以得记录一下失衡节点的父节点
//对应哪一个孩子，就把失衡节点的父节点对应的孩子赋值为失衡节点的左孩子
//记录失衡节点的原本的父节点
node* parentparent = parent->_parent;
if (parent == _root)
{
_root = subl;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subl;
}
else if (parent == parentparent->_right)
{
parentparent->_right = subl;
}
}

//然后把失衡节点的左孩子的_parent指针修改为失衡节点的原本的父节点
//即parent->_parent;
//无论失衡节点是不是最上面的根节点（是的话，不就是它的父节点为nullptr吗）
//都可以进行这个操作
subl->_parent = parentparent;
//最后把失衡节点的_parent指针修改为失衡节点的左孩子
parent->_parent = subl;
}

//第二种情况：RR型，即新插入节点在失衡节点的右孩子的右子树中
//进行左单旋
void RotateL(node* parent)
{
assert(parent);//检验是否传入空指针
assert(parent->_right); // 补充：RR型左单旋必须保证失衡节点有右孩子

//失衡节点是该函数的参数，由外界传入
node* subr = parent->_right;
node* subrl = parent->_right->_left;
//无论失衡节点的右孩子的左孩子为不为空
//（即无论该节点为不为nullptr）
//都得把该孩子纳为失衡节点的右孩子（最终的平衡的树）
//而要是该孩子不为nullptr的话，那么得把该孩子的parent进行更新，换为失衡节点
parent->_right = subrl;
if (subrl != nullptr)
{
//同时把失衡节点的右孩子的左孩子的_parent指针进行更新
subrl->_parent = parent;
}
//然后将失衡节点的右孩子的左孩子修改为失衡节点
subr->_left = parent;
//那么在最后失衡节点的右孩子会变为原本的失衡节点的整颗子树的新的根节点
//所以要判断原本的失衡节点是不是整棵树的根节点
//是的话,那么就把整棵树的root赋值为失衡节点的右孩子
//不是的话，那么就看原本的失衡节点是它的父节点的左孩子还是右孩子，所以得记录一下失衡节点的父节点
//对应哪一个孩子，就把失衡节点的父节点对应的孩子赋值为失衡节点的右孩子
//记录失衡节点的原本的父节点
node* parentparent = parent->_parent;
if (parent == _root)
{
_root = subr;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subr;
}
else if (parent == parentparent->_right)
{
parentparent->_right = subr;
}
}

//然后把失衡节点的右孩子的_parent指针修改为失衡节点的原本的父节点
//即parent->_parent;
//无论失衡节点是不是最上面的根节点（是的话，不就是它的父节点为nullptr吗）
//都可以进行这个操作
subr->_parent = parentparent;
//最后把失衡节点的_parent指针修改为失衡节点的右孩子
parent->_parent = subr;
}

private:
node* _root=nullptr;//整棵红黑树的最上面一层的根节点！！！记得是黑色的哦
};

三、封装实现set类：适配红黑树的单一key存储

set的核心需求是“有序+去重的单一key存储”，其封装逻辑相对简单：通过定义专属仿函数，将红黑树的存储类型指定为const K（确保key不可修改），然后复用红黑树的接口实现自己的对外接口。我们分“仿函数设计”“迭代器封装”“核心接口实现”三个部分拆解。

3.1 set的仿函数设计：直接提取key

set的存储类型是K（如int、string），key就是存储的数据本身，因此仿函数的逻辑是“直接返回传入的K类型数据”。我们在set类内部定义仿函数KeyOfKey（对应你提供的keyofkey）：

struct KeyOfKey { const K& operator()(const K& k) const { return k; } };

这个仿函数的作用是将set的存储类型K传递给红黑树，让红黑树能够直接提取key进行比较。需要注意的是，仿函数的返回值是const K&——这是为了避免拷贝，同时确保key不会被修改。

3.2 set的迭代器封装：复用红黑树的迭代器

set的迭代器本质是红黑树的迭代器，因为set的有序访问依赖红黑树的中序遍历。我们只需将红黑树的迭代器重命名为set的迭代器，即可实现迭代器的复用。具体来说：

set的红黑树成员是RBTree<const K, KeyOfKey> _tree;——这里将存储类型指定为const K，是为了确保key不可修改（修改key会破坏红黑树的有序性）。因此，set的迭代器定义为：

using iterator = typename RBTree<const K, KeyOfKey>::Iterator;

using const_iterator = typename RBTree<const K, KeyOfKey>::ConstIterator;

这里的typename是必须的，因为RBTree<const K, KeyOfKey>::Iterator是“依赖于模板参数的类型”，编译器无法确定其是类型还是成员变量，需要用typename显式说明。

set的begin()和end()函数直接复用红黑树的对应接口：

iterator begin() { return _tree.begin(); }

iterator end() { return _tree.end(); }

const_iterator cbegin() const { return _tree.cbegin(); }

const_iterator cend() const { return _tree.cend(); }

这样，set的迭代器就具备了双向迭代和有序访问的功能，完全满足STL的迭代器要求。

3.3 set的核心接口实现：复用红黑树的插入与查找

set的核心接口是insert（插入key）、find（查找key）、erase（删除key），这些接口都可以直接复用红黑树的对应接口，只需做简单的封装：

1. insert函数：std::pair<iterator, bool> insert(const K& kv)。直接调用红黑树的Insert函数，返回红黑树的返回值即可——红黑树的Insert函数已经实现了“去重”逻辑（key存在则返回false），正好满足set的去重需求。

2. find函数：iterator find(const K& key)。调用红黑树的Find_Node函数，找到返回对应的迭代器，找不到返回end()。需要注意的是，find函数的参数是key（K类型），而红黑树的Find_Node函数参数是T（const K类型），因此直接传递key即可。

3. erase函数：size_t erase(const K& key)。调用红黑树的erase函数（需要额外实现），删除对应的节点，返回删除的节点个数（0或1，因为set的key唯一）。红黑树的erase函数需要通过key找到节点，然后删除并进行平衡调整，逻辑与插入类似，但更复杂（需要处理多种节点删除情况）。

set的其他接口（如clear、size等）也都可以通过红黑树的成员函数实现，核心思路都是“封装红黑树的接口，对外提供简洁的访问方式”。

示例代码：

#include <iostream>
#include <algorithm>
#include <utility>
#include "RedBlackTree.hpp"

namespace win
{
template <typename K>
class set
{
public:
//实现set的仿函数，能获取到传入的参数的key值，然后再去进行比较
//因为红黑树就存储一种类型，具体可以看红黑树头文件中所解析的
struct keyofkey
{
//那么是需要外界传入K类型的数据的，这样子我们函数内部才能去获取到传入的参数的key值，
const K& operator()(const K& k) const
{
return k;
}
};

//获取迭代器的函数
using iterator=RBTree<const K,keyofkey>::Iterator;
using const_iterator=RBTree<const K,keyofkey>::ConstIterator;
//再次进行重命名，符合stl风格

iterator begin()
{
return _tree.begin();//直接调用红黑树类里面我们封装好的函数即可
}

iterator end()
{
return _tree.end();//直接调用红黑树类里面我们封装好的函数即可
}

const_iterator cbegin() const
{
return _tree.cbegin();//直接调用红黑树类里面我们封装好的函数即可
}

const_iterator cend() const
{
return _tree.cend();//直接调用红黑树类里面我们封装好的函数即可
}

//实现set的insert函数
std::pair<iterator,bool> insert(const T& kv)
{
return _tree.Insert(kv);
}
private:
RBTree<const K,keyofkey> _tree;//在set中，红黑树的节点存储的数据就是K类型，所以我们要传入K
//key值不能改，所以我们传入到红黑树里的key得加个const

};
}

四、封装实现map类：适配红黑树的key-value存储

map的核心需求是“有序的key-value存储”，并支持通过key快速访问value，其封装逻辑与set类似，但需要处理“key-value对”的存储和[]运算符的实现。我们分“仿函数设计”“迭代器封装”“核心接口实现”“[]运算符实现”四个部分拆解。

4.1 map的仿函数设计：提取pair的key

map的存储类型是pair<const K, V>，其中first是key（不可修改），second是value（可修改）。因此，仿函数的逻辑是“从pair中提取first成员作为key”。我们在map类内部定义仿函数KeyOfPair（对应你提供的keyofpair）：

struct KeyOfPair { const K& operator()(const pair<const K, V>& kv) const { return kv.first; } };

这个仿函数的作用是将map的pair类型数据传递给红黑树，让红黑树能够通过pair的first成员进行比较。需要注意的是，pair的first成员被定义为const K——这是为了确保key不可修改，避免破坏红黑树的有序性。

4.2 map的迭代器封装：复用红黑树的迭代器

map的迭代器同样复用红黑树的迭代器，其存储类型是pair<const K, V>，因此迭代器的定义为：

using iterator = typename RBTree<pair<const K, V>, KeyOfPair>::Iterator;

using const_iterator = typename RBTree<pair<const K, V>, KeyOfPair>::ConstIterator;

与set不同的是，map的普通迭代器可以修改value（pair的second成员），但无法修改key（pair的first成员是const）——这正是我们想要的效果：key不可修改，value可修改。

map的begin()、end()、cbegin()、cend()函数与set完全一致，直接复用红黑树的对应接口：

iterator begin() { return _tree.begin(); }

iterator end() { return _tree.end(); }

const_iterator cbegin() const { return _tree.cbegin(); }

const_iterator cend() const { return _tree.cend(); }

4.3 map的核心接口实现：复用红黑树的插入与查找

map的核心接口是insert（插入key-value对）、find（查找key）、erase（删除key），这些接口同样复用红黑树的对应接口，封装逻辑与set类似：

1. insert函数：std::pair<iterator, bool> insert(const pair<const K, V>& kv)。调用红黑树的Insert函数，插入pair类型数据，返回红黑树的返回值——红黑树通过仿函数提取kv.first进行比较，实现key的唯一性。

2. find函数：iterator find(const K& key)。调用红黑树的Find_Node函数，参数是pair<const K, V>(key, V())（通过key构造一个临时pair），红黑树通过仿函数提取key进行查找，找到返回对应的迭代器，找不到返回end()。

3. erase函数：size_t erase(const K& key)。与set的erase函数类似，调用红黑树的erase函数，通过key找到节点并删除，返回删除的节点个数。

4.4 map的核心特性：[]运算符的实现

[]运算符是map最具特色的接口，其功能是“通过key快速插入键值对或访问value”，比如map["张三"] = 20; 如果"张三"不存在，会自动插入键值对("张三", 20)；如果"张三"已存在，会直接修改value为20。这个功能的底层完全依赖红黑树的insert函数，我们详细拆解其实现逻辑：

首先，[]运算符的函数声明：V& operator[](const K& key)。返回值是V&，这样才能支持修改value（比如赋值操作）。

其次，核心逻辑分两步：

步骤1：调用红黑树的Insert函数插入键值对。插入的数据是pair<const K, V>(key, V())——这里的V()是V类型的默认构造函数（比如V是int，就是0；V是string，就是空字符串）。红黑树的Insert函数会返回pair<iterator, bool>：如果key不存在，插入成功，iterator指向新插入的节点，bool为true；如果key已存在，插入失败，iterator指向已存在的节点，bool为false。

步骤2：返回迭代器指向节点的value引用。无论插入成功与否，迭代器都指向“key对应的节点”，我们通过it->second获取value的引用并返回——这样，用户就可以直接对value进行赋值或访问。

用代码表示就是：

V& operator[](const K& key) {

std::pair<iterator, bool> ret = _tree.Insert({key, V()}); // 隐式构造pair

return ret.first->second;

}

这个实现非常巧妙：它将“插入”和“访问”两个操作合并为一个接口，既简化了用户的使用，又复用了红黑树的insert逻辑，避免了重复代码。需要注意的是，如果V没有默认构造函数，这个实现会编译失败——这也是STL map的限制，用户需要确保V具备默认构造能力。

示例代码：

#include <iostream>
#include <algorithm>
#include <utility>
#include "RedBlackTree.hpp"

namespace win
{
template <typename K,typename V>
class map
{
public:
//实现map的仿函数，能获取到传入的参数的key值——T.first，然后再去进行比较
//因为红黑树就存储一种类型，具体可以看红黑树头文件中所解析的
struct keyofpair
{
//那么是需要外界传入pair结构体的，这样子我们函数内部才能去获取到传入的参数的key值，
//也就是pair.first
const V& operator()(std::pair<const K,V>& kv) const
{
return kv.first;
}
};

//获取迭代器的函数
using iterator=RBTree<const K,keyofkey>::Iterator;
using const_iterator=RBTree<const K,keyofkey>::ConstIterator;
//再次进行重命名，符合stl风格

iterator begin()
{
return _tree.begin();//直接调用红黑树类里面我们封装好的函数即可
}

iterator end()
{
return _tree.end();//直接调用红黑树类里面我们封装好的函数即可
}

const_iterator cbegin() const
{
return _tree.cbegin();//直接调用红黑树类里面我们封装好的函数即可
}

const_iterator cend() const
{
return _tree.cend();//直接调用红黑树类里面我们封装好的函数即可
}

//实现map的insert函数
std::pair<iterator,bool> insert(const T& kv)
{
return _tree.Insert(kv);
}

//那么我们知道，在map里面，stl还对[]进行运算符重载
//当用户调用它时，[]里面放入的数据就得被插入红黑树中，然后返回数据的second，也就是value值，支持修改
//那么它的实现其实就是依靠insert函数，stl中insert函数的返回值是pair<iterator,bool>类型的
//成功了就返回新插入节点的迭代器和true，失败了就返回已经存在的节点的迭代器和false
//所以本质上是需要在insert函数进行开刀的
V& operator[](const K& key)
{
std::pair<iterator,bool> ret=_tree.Insert({key,V()});//使用隐式转换，传入key值和V类型的默认构造函数
//返回节点的value值，即pair的second
//即新插入节点的->second，因为我们有对->进行重载，所以->可以直接访问到节点中的数据的second
return ret.first->second;
}
private:
RBTree<std::pair<const K,V>,keyofpair> _tree;//在map中，红黑树的节点存储的数据是pair类型，所以我们要传入pair
//key值不能改，所以我们传入到红黑树里的key得加个const
};
}

五、与SGI-STL源码对比：理解工业级实现的细节

我们的模拟实现参考了SGI-STL的设计思路，但工业级实现会更严谨、更高效。通过对比我们的实现和SGI-STL源码，我们可以理解一些细节设计的原因，提升对STL容器的认知。我们主要对比“红黑树的模板参数”“迭代器的实现”“set和map的封装”三个核心部分：

5.1 红黑树的模板参数：SGI-STL的设计

我们的红黑树模板参数是template <typename T, typename KeyofT>，而SGI-STL的红黑树模板参数是template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>。两者的核心差异在于：SGI-STL额外增加了Key（key类型）和Compare（比较仿函数）两个模板参数，以及Alloc（内存分配器）。

为什么增加Key参数？因为set和map的find、erase函数的参数是Key类型（比如map的find参数是K，而不是pair），而我们的实现中，find函数的参数是T类型（set是K，map是pair），需要用户构造临时的T对象——SGI-STL通过Key参数直接指定find、erase的参数类型，更高效、更灵活。

为什么增加Compare参数？我们的实现中，key的比较是默认的“小于”（<），而SGI-STL通过Compare参数支持自定义比较规则（比如大于、自定义对象的比较），比如set<int, greater<int>>可以实现降序存储——这是工业级实现的灵活性要求。

为什么增加Alloc参数？内存分配器是STL的核心组件之一，用于统一管理内存分配和释放。我们的实现中直接

使用new/delete进行内存分配，而SGI-STL通过Alloc参数将内存分配逻辑解耦，允许用户自定义内存分配策略（比如内存池分配、共享内存分配等）。这一设计的核心目的是提升内存管理的灵活性和效率——在高频次、小批量的节点分配场景中，默认的new/delete会因频繁调用系统内存管理接口产生大量内存碎片，且分配效率较低；而SGI-STL的默认内存分配器（alloc）采用了内存池技术，预先从系统申请一块连续的内存空间，再根据节点大小按需切割分配，不仅大幅减少了内存碎片，还通过内存块的复用提升了分配和释放的效率。此外，Alloc参数的抽象设计也让STL具备了跨环境适配能力，比如在嵌入式系统等内存资源紧张的场景中，用户可自定义精简版内存分配器，进一步优化内存占用。相比之下，我们的模拟实现为了简化逻辑，直接使用new/delete，虽然易于理解，但在性能和灵活性上无法满足工业级场景的需求，这也体现了模拟实现与工业级实现的核心差异之一。

5.2 迭代器的实现：SGI-STL的优化

迭代器是容器与算法之间的“桥梁”，其设计的优劣直接影响容器的使用体验和性能。我们的模拟实现仅满足了迭代器的基础功能（双向遍历、数据访问），而SGI-STL的迭代器实现围绕“高效性、简洁性、兼容性”三大目标做了多重优化。下面从“边界处理优化”“类型安全强化”“冗余逻辑精简”三个核心维度，结合源码设计思路展开对比分析。

5.2.1 哨兵节点（nil节点）：彻底简化end()与边界判断

我们的模拟实现中，迭代器的end()被设计为nullptr，代表“最后一个有效节点的下一个位置”。这种设计存在两个明显局限：一是处理–end()时，必须依赖红黑树的_root指针遍历找到最右节点，增加了逻辑复杂度；二是迭代器的++/–操作中，需要频繁判断节点是否为nullptr，边界处理逻辑繁琐。

SGI-STL通过引入“哨兵节点（nil节点）”彻底解决了这一问题。nil节点是一个全局共享的空节点，具备红黑树节点的所有成员（颜色、左右孩子、父节点），且颜色固定为黑色。其核心作用是“统一所有空指针的指向”和“作为end()的具体载体”，具体优化逻辑如下：

1. 统一空指针指向：红黑树中所有原本为nullptr的左孩子、右孩子、父节点（如根节点的父节点、叶子节点的左右孩子），全部指向nil节点。这使得迭代器的++/–操作中，无需再判断“节点是否为nullptr”，只需直接访问nil节点的相关成员即可，大幅简化了边界判断逻辑。

2. end()的实现优化：SGI-STL中，红黑树的end()迭代器直接指向nil节点，而非nullptr。此时–end()的逻辑变得异常简洁：由于nil节点的父节点正是红黑树的最右节点（插入和删除操作中会维护这一关系），因此只需将迭代器的节点指针从nil指向其parent即可，无需再从根节点遍历查找。这种设计将–end()的时间复杂度从O(logN)降至O(1)，极大提升了效率。

对比来看，我们的模拟实现为了简化理解，牺牲了边界处理的效率和简洁性；而SGI-STL的nil节点设计，通过“空间换时间”的思路，将复杂的边界逻辑统一化，是工业级实现中“兼顾效率与可维护性”的典型优化。

5.2.2 迭代器的类型封装：强化类型安全与接口标准化

我们的模拟实现通过“模板参数REF和PTR”实现了普通迭代器与const迭代器的复用，但在类型安全和接口标准化上存在明显不足：一是迭代器的类型信息未完全封装，可能出现普通迭代器与const迭代器的非法赋值（如将普通迭代器赋值给const迭代器是允许的，但反之不允许，我们的实现未严格限制）；二是未严格遵循STL迭代器的接口规范（如未定义iterator_category、value_type等关联类型），无法与STL算法无缝适配。

SGI-STL的迭代器实现严格遵循C++标准的迭代器规范，通过“类型封装”和“关联类型定义”解决了上述问题：

1. 严格的类型区分与限制：SGI-STL将普通迭代器和const迭代器设计为两个不同的类（而非仅通过模板参数区分），并通过“隐式转换”控制赋值权限——允许const迭代器接收普通迭代器的赋值（因为const迭代器的访问权限更严格），但禁止普通迭代器接收const迭代器的赋值，从语法层面强化了类型安全，避免了非法数据修改。

2. 完善的关联类型定义：SGI-STL的迭代器内部通过typedef定义了5个核心关联类型（iterator_category、value_type、difference_type、pointer、reference），这些类型是迭代器与STL算法协同工作的基础。例如，算法通过iterator_category判断迭代器的类型（双向迭代器、随机访问迭代器等），从而选择最优的遍历策略；通过value_type确定算法处理的数据类型。我们的模拟实现未定义这些关联类型，因此无法直接适配STL标准算法，而SGI-STL的标准化设计，确保了容器与算法的无缝衔接，这是工业级实现“兼容性”的核心要求。

5.2.3 冗余成员的精简：移除_root指针的依赖

我们的模拟实现中，迭代器内部存储了_root指针，用于处理–end()的特殊情况。但_root指针的存在带来了两个问题：一是增加了迭代器的内存占用（每个迭代器多存储一个指针）；二是迭代器与红黑树强耦合，当红黑树的根节点发生变化（如插入删除导致根节点旋转）时，需要同步更新所有迭代器的_root指针，增加了维护成本。

SGI-STL借助nil节点的设计，彻底移除了迭代器对_root指针的依赖：如前文所述，end()迭代器指向nil节点，–end()直接通过nil的parent找到最右节点，无需_root指针；而其他迭代器的++/–操作，通过节点的parent、left、right指针即可完成（所有空指针都指向nil，无需判断根节点）。这种设计使迭代器的内存占用减少了1/3（仅存储一个节点指针），同时降低了迭代器与红黑树的耦合度，提升了代码的可维护性。

5.2.4 优化总结：工业级迭代器的核心设计思路

对比我们的模拟实现与SGI-STL的迭代器设计，可以总结出工业级迭代器的核心优化思路：一是通过“统一化设计”（如nil节点）简化复杂边界逻辑，提升效率；二是通过“严格的类型封装”强化类型安全，遵循标准规范；三是通过“冗余逻辑精简”降低耦合度，提升可维护性。这些优化并非孤立存在，而是相互协同——nil节点的设计不仅优化了边界处理，还为移除_root指针提供了可能；严格的类型封装则确保了容器与算法的兼容性，这正是SGI-STL迭代器实现“高效、安全、通用”的核心原因。

5.3 set 和 map 的封装：SGI-STL 的细节优化

我们的模拟实现仅完成了set和map“基本功能的封装”，核心目标是清晰呈现“红黑树复用”的核心逻辑；而SGI-STL的set和map封装，在复用红黑树的基础上，围绕“灵活性、兼容性、安全性、高效性”四大目标做了大量细节打磨。本节从“模板参数拓展”“接口标准化适配”“红黑树复用深度优化”“类型安全与边缘情况处理”四个维度，结合源码设计思路展开对比分析。

5.3.1 模板参数拓展：兼容自定义比较与内存分配

我们的模拟实现中，set和map的模板参数设计较为简单：set仅接收“key类型K”，map仅接收“key类型K”和“value类型V”，比较逻辑固定为“小于（<）”，内存分配固定为new/delete。这种设计虽然简洁，但无法满足工业级开发的多样化需求——比如需要降序存储、自定义对象比较，或在内存紧张场景下使用自定义内存池等。

SGI-STL通过拓展模板参数，彻底解决了这一局限。其set和map的模板参数定义如下：

// set的模板参数：Key（key类型）、Compare（比较仿函数）、Alloc（内存分配器）

template <class Key, class Compare = less<Key>, class Alloc = alloc> class set;

// map的模板参数：Key（key类型）、T（value类型）、Compare（比较仿函数）、Alloc（内存分配器）

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map;

两个核心拓展参数的优化价值的具体体现如下：

1. Compare参数：支持自定义比较规则。SGI-STL默认使用less<Key>仿函数（即“小于比较”），实现升序存储；若需降序，可传入greater<Key>仿函数（如set<int, greater<int>> desc_set）；对于自定义对象（如Person类，需按年龄比较），用户可自定义仿函数（如struct ComparePerson { bool operator()(const Person& p1, const Person& p2) { return p1.age < p2.age; } }），直接传递给set/map即可。这种设计让set/map的排序逻辑完全“解耦”于容器本身，适配多样化排序需求。

2. Alloc参数：支持自定义内存分配器。与红黑树的Alloc参数一致，set和map的Alloc参数可接收自定义内存分配器——比如在嵌入式系统中，用户可实现一个基于静态内存的分配器，传递给set/map，避免动态内存分配的碎片问题；在高频次节点插入/删除场景中，可使用内存池分配器提升效率。SGI-STL默认使用alloc内存分配器（基于内存池），兼顾效率与通用性。

对比来看，我们的模拟实现通过“硬编码”固定了比较逻辑和内存分配，牺牲了灵活性；而SGI-STL的模板参数拓展，通过“仿函数+内存分配器抽象”，让set/map具备了跨场景适配能力，这是工业级容器“通用性”的核心保障。

5.3.2 接口标准化：适配STL算法与多场景使用

我们的模拟实现仅实现了set和map的核心接口（insert、find、erase、begin、end等），接口形式较为单一；而SGI-STL的set和map严格遵循STL容器的接口规范，实现了完整的“容器必要接口”和“可选拓展接口”，确保与STL算法无缝适配，同时支持多场景使用。

核心标准化接口的优化的具体体现如下：

1. 多形态插入接口：除了“插入单个元素”（insert(const value_type& x)），SGI-STL还实现了“插入迭代器范围”（insert(iterator first, iterator last)）和“插入初始化列表”（C++11后支持，insert(initializer_list<value_type> il)）。其中，“迭代器范围插入”是工业级开发的高频需求——比如将一个vector中的元素批量插入set去重，使用insert(v.begin(), v.end())可避免循环调用单元素插入，大幅提升效率（批量插入可减少红黑树的平衡调整次数）。

2. 多形态erase接口：除了“按key删除”（size_t erase(const Key& x)），SGI-STL还实现了“按迭代器删除”（void erase(iterator pos)）和“按迭代器范围删除”（void erase(iterator first, iterator last)）。“按迭代器删除”可直接定位到节点，避免重新查找key，提升效率；“范围删除”则支持批量删除连续元素，适配算法中的批量处理场景。

3. 算法适配接口：SGI-STL的set和map实现了size()、empty()、swap()、clear()等标准接口，结合迭代器的关联类型（iterator_category、value_type等），可直接与STL算法协同工作。比如使用std::find算法查找set中的元素（std::find(set.begin(), set.end(), 10)）、使用std::for_each遍历map等——而我们的模拟实现因缺少标准化接口和迭代器关联类型，无法直接适配这些算法。

5.3.3 红黑树复用深度优化：减少冗余与解耦

我们的模拟实现中，set和map通过“内部定义仿函数+包含红黑树成员变量”实现复用，逻辑清晰但存在轻微冗余——比如set和map都需要单独定义仿函数（KeyOfKey、KeyOfPair），且红黑树的模板参数传递逻辑重复。

SGI-STL通过“红黑树基类抽象”和“模板参数复用”，进一步提升了红黑树的复用深度，减少了代码冗余。其核心设计思路是“set和map的底层红黑树是同一个模板类的实例化，仅通过模板参数差异区分存储类型和比较逻辑”，具体优化细节如下：

1. 红黑树的value_type适配：SGI-STL的红黑树模板参数接收“Value类型”（即节点存储类型），set的value_type就是Key（且为const，确保key不可修改），map的value_type是pair<const Key, T>（确保key不可修改，value可修改）。set和map通过传递不同的Value类型，直接复用同一套红黑树代码，无需单独适配。

2. 仿函数的统一传递：set和map将自身的Compare参数，直接传递给红黑树的Compare参数，红黑树的所有比较操作（插入、查找）均依赖该仿函数——这让set和map的比较逻辑与红黑树完全解耦，红黑树无需关心比较规则，只需调用Compare仿函数即可，进一步提升了复用性。

3. 共用基类封装公共逻辑：SGI-STL为set和map设计了共用的基类（如_Rb_tree<Key, Value, KeyOfValue, Compare, Alloc>），将红黑树的操作（insert、erase、find等）封装在基类中，set和map仅需继承基类，再根据自身特性封装对外接口即可——比如map的[]运算符是独有接口，在map类中单独实现；set的value_type是const Key，在set类中通过typedef显式定义，避免冗余代码。

5.3.4 类型安全与边缘情况处理：工业级可靠性保障

我们的模拟实现为了简化逻辑，忽略了很多边缘情况处理和类型安全限制——比如set的迭代器允许通过*it修改key（若模拟实现中set的存储类型未严格定义为const K）、map的insert函数未处理“value_type为pair<const K, V>”的const限制、erase迭代器后未考虑迭代器失效问题等。这些问题在模拟场景下影响不大，但在工业级开发中可能导致程序崩溃或逻辑错误。

SGI-STL通过严格的类型定义和边缘情况处理，确保了容器的可靠性，核心优化点如下：

1. 严格限制key的可修改性：set的value_type被显式定义为const Key，因此其迭代器是“只读迭代器”——即使是普通迭代器，*it返回的也是const Key&，无法修改key；map的value_type是pair<const K, V>，通过const K确保key不可修改，同时允许修改V（it->second）。这种类型定义从语法层面杜绝了“修改key破坏红黑树有序性”的风险。

2. 处理迭代器失效问题：红黑树的插入/删除操作可能导致节点旋转或移动，进而导致迭代器失效（比如删除节点后，指向该节点的迭代器变为野指针）。SGI-STL在erase接口中做了特殊处理：对于“按迭代器删除”，返回“删除节点的下一个节点的迭代器”（如iterator erase(iterator pos) { return _tree.erase(pos); }），用户可通过该返回值更新迭代器，避免失效（如for (auto it = map.begin(); it != map.end(); ) { if (it->first == 10) it = map.erase(it); else ++it; }）。而我们的模拟实现未处理这一问题，删除迭代器后继续使用会导致未定义行为。

3. 边缘情况的兼容处理：SGI-STL还兼容了多种边缘场景，比如插入空值（若Key支持）、删除不存在的key（返回0，无错误）、对空容器调用begin()/end()（返回指向nil节点的迭代器，避免空指针访问）等。这些细节处理确保了容器在各种极端场景下的稳定性，是工业级实现“可靠性”的核心要求。

5.3.5 优化总结：工业级封装的核心设计思路

对比我们的模拟实现与SGI-STL的set/map封装设计，可以总结出工业级容器封装的核心优化思路：一是通过“模板参数拓展”提升灵活性，适配自定义比较、内存分配等多样化需求；二是通过“接口标准化”确保与STL生态（算法、迭代器）的无缝衔接；三是通过“基类抽象与参数复用”深化红黑树复用，减少代码冗余；四是通过“严格类型定义与边缘情况处理”保障容器的安全性和可靠性。

这些优化的本质是“在复用核心逻辑的基础上，通过抽象和解耦，提升容器的通用性、兼容性和稳定性”——这也是STL容器能够成为C++工业级开发核心工具的关键原因。

六、总结：

从“理解逻辑”到“掌握思想”的进阶路径

set与map的底层实现涉及二叉树、泛型、仿函数、迭代器等多个知识点，初学者容易陷入“代码看不懂、实现不会写”的困境。结合本文内容，给出3条针对性学习建议，帮助大家高效进阶：

最后需要强调：学习set与map的底层实现，核心不是“复刻STL源码”，而是掌握“复用思想”“抽象解耦”“平衡效率与可用性”的设计思路。这些思路不仅适用于容器实现，更适用于日常开发中的代码设计，这才是这部分知识的核心价值。

结语：以底层为基，向进阶而行

当我们终于走完set与map底层实现的探索之旅，从红黑树的泛型改造、迭代器的双向逻辑，到set的单一key去重、map的key-value适配，再到与SGI-STL工业级实现的深度对比，相信每一位学习者心中都多了一份对“底层逻辑”的敬畏，也多了一份对“代码设计”的通透。这段旅程或许充满挑战——红黑树旋转的四种场景曾让我们反复画图推演，迭代器++/–的边界处理曾让我们纠结于nullptr与哨兵节点的差异，map[]运算符的底层复用逻辑曾让我们恍然大悟。但正是这些“纠结”与“顿悟”，构成了我们从“会用容器”到“懂容器”的进阶阶梯。

回望整个学习过程，我们最核心的收获，从来不是复刻了一套set与map的模拟实现代码，而是掌握了贯穿始终的“复用思想”与“抽象解耦”的设计哲学。红黑树作为底层核心，通过模板参数与仿函数的抽象，完美适配了set与map两种不同的业务需求——set的单一key存储只需简单提取key，map的key-value存储则通过pair封装与key提取仿函数实现适配，这种“一份核心代码，多场景复用”的思路，正是工业级开发中提升效率、降低维护成本的关键。而迭代器的设计，则通过“封装节点指针+重载运算符”的方式，构建了容器与算法之间的桥梁，让我们明白“接口标准化”对于生态协同的重要性——这也是STL能够成为C++工业级开发基石的核心原因。

在与SGI-STL源码的对比中，我们更深刻地体会到“工业级实现”与“模拟实现”的差距所在。从哨兵节点对边界逻辑的简化，到模板参数拓展对自定义比较、内存分配的支持；从迭代器关联类型对算法适配的保障，到边缘情况处理对容器可靠性的提升，每一处细节优化都源于实际开发的需求沉淀。这让我们明白，优秀的代码从来不是“炫技式的复杂”，而是“恰到好处的严谨”——既能够满足多样化的业务场景，又能够保证高效、安全、稳定的运行，还能够让后续开发者轻松理解与维护。这种“于细节处见真章”的工匠精神，值得我们在每一次代码编写中践行。

对于学习C++的开发者而言，set与map的底层实现探索，更像是一次“筑基修炼”。它串联起了二叉树、泛型编程、仿函数、迭代器等多个核心知识点，打破了我们对“孤立知识点”的认知局限，让我们看到不同知识点之间的内在关联。很多时候，我们在学习单一知识点时会觉得“无用”，比如“为什么要学红黑树？日常开发直接用set不就行了？”“仿函数这么复杂，直接写个比较函数不行吗？”而当我们完整走完这段底层探索之旅后，这些疑问都会迎刃而解——红黑树的平衡机制保证了set与map的高效插入与查找，仿函数的抽象则提升了代码的复用性与灵活性，迭代器的标准化则让容器能够与丰富的STL算法协同工作。这些底层知识，就像是建筑的地基，看似看不见摸不着，却决定了我们能够构建的系统高度与稳定性。

当然，这段探索之旅也只是我们C++学习路上的一个驿站，而不是终点。STL的世界还有很多值得我们深入探索的内容——vector的动态扩容机制、list的双向链表实现、hash_table与unordered_set/unordered_map的底层逻辑，以及内存分配器的详细实现等。每一个容器的底层都藏着相似的设计哲学，也有着独特的优化思路。比如vector的连续内存与动态扩容策略，兼顾了随机访问的高效性与内存的灵活性；list的双向链表设计，则擅长频繁的插入与删除操作；hash_table则通过哈希函数实现了近似O(1)的查找效率，弥补了红黑树O(logN)效率的不足。这些容器的设计，都是对“不同场景下效率与可用性平衡”的最佳诠释。

在未来的学习与开发中，希望大家能够带着这段探索之旅中收获的“底层思维”，去审视每一个用过的工具、每一段写过的代码。当我们再使用set去重时，能够想起其底层红黑树的有序性与去重逻辑；当我们用map的[]运算符快速插入键值对时，能够明白其底层是insert函数的复用与value引用的返回；当我们选择不同容器时，能够根据业务场景的需求，结合容器的底层特性做出最优选择——比如需要有序遍历与快速查找时选择set/map，需要频繁随机访问时选择vector，需要频繁插入删除时选择list，需要极致查找效率时选择unordered_set/unordered_map。这种“知其然，更知其所以然”的能力，将是我们从“初级开发者”成长为“高级开发者”的核心竞争力。

同时，也希望大家能够保持“动手实践”的习惯。正如前文所说，纸上谈兵终觉浅，底层逻辑的理解离不开代码的落地实现。或许我们最初实现的版本并不完美，可能存在内存泄漏、边界处理不完善、效率不高等问题，但每一次动手都是一次成长。我们可以先实现简化版本，再逐步补充细节；可以对比不同的实现方案，分析其优劣；可以尝试模仿SGI-STL的优化思路，为自己的代码增加哨兵节点、拓展模板参数、处理迭代器失效问题。在这个过程中，我们不仅能够深化对底层逻辑的理解，还能够提升代码编写、问题排查、性能优化的能力。

学习编程的路上，从来没有捷径可走。每一个优秀的开发者，都是在一次次的探索、实践、反思中成长起来的。可能我们会在理解红黑树旋转逻辑时感到困惑，会在实现迭代器边界处理时遇到瓶颈，会在对比源码时惊叹于工业级实现的严谨，但请不要放弃。每一次困惑都是对认知的挑战，每一次瓶颈都是突破的契机，每一次惊叹都是学习的动力。正如红黑树通过旋转与变色维持平衡一样，我们的学习之路也需要在“探索新知识点”与“巩固旧知识”之间找到平衡，在“仰望工业级实现的高度”与“脚踏实地编写每一行代码”之间稳步前行。

最后，愿每一位走在C++学习路上的开发者，都能够以底层为基，筑牢知识的根基；以探索为翼，拓展能力的边界；以实践为径，通往进阶的彼岸。当我们能够从容地穿梭于容器的底层实现与上层应用之间，能够自如地运用设计哲学解决实际问题时，我们会发现，编程不仅是一门技术，更是一门艺术。而这段关于set与map底层实现的探索之旅，正是我们通往这门艺术殿堂的重要一步。未来可期，让我们继续在技术的海洋中深耕细作，不断沉淀，不断成长，写出更优雅、更高效、更可靠的代码，成为更好的自己。