前言
书接上篇博客《手撕红黑树》，我们学习到了红黑树是如何通过其内部方式来管理数据的，本篇文章将基于上篇文章继续探讨红黑树的更多应用。set，map是STL库中很重要的容器，他们就是利用红黑树作为底层来实现的，今天让我们一起走进set与map的世界，通过模拟的方式理解其设计，揭开这两位容器的神秘面纱。
目录
前言
一、STL源码中的设计
1、bool值代替颜色
2、采用相同红黑树模板
3、红黑树结构中的泛型节点
4、红黑树的一个模板参数
5、红黑树的其他模板参数
二、map、set模拟封装
1、红黑树改造
（1）、红黑树节点改造
（2）红黑树节点比较
（3）、红黑树第一个模板参数
（4）、红黑树迭代器
1、迭代器结构
2、begin（）与end（）
3、operator++（）
4、operator--()
5、迭代器的其他操作
6、const迭代器的完善
（5）、insert返回值
2、map与set封装
1、红黑树实例化参数
2、红黑树节点比较
3、map，set迭代器
4、set、map对其他函数的封装
5、map方括号【】
结束语
附录
改造后的红黑树类模板
set封装代码
map封装代码
测试代码
一、STL源码中的设计
Set结构设计
Map结构设计
上图重点已用红色框图圈出
我们可以发现对于map和set来说，他们在STL库中的实现底层都是红黑树，这也证明了红黑树应用更加多的一个说法，下面我们具体来分析一下STL中利用红黑树对map与set实现的细节。
1、bool值代替颜色
库中采用bool值来代表红黑树的颜色，红色则为1，黑色则为0
2、采用相同红黑树模板
首先明确一点，我们希望利用红黑树来管理不同类型的数据，于是将红黑树写成泛型，适配各种类型数据。将红黑树写成模板，以管理不同类型的红黑树
set是一个k（key）结构，而map是一个kv（key，value）结构，按道理来说set与map容器的实现应该是k，kv两个不同模式的红黑树来实现（也就是不同的红黑树模板），可STL中用的是同一个红黑树模板。仔细观察不难发现，在map中向红黑树模板传递参数时，传递key类型，pair类型，实例化的红黑树为（key，pair）。但在set中向红黑树模板传递参数时，第一个与第二个参数相同，都是key的类型，也就是再传value的位置仍然传递了key的类型，实例化的红黑树为（key，key）。大家在这里记住这个设计，这样设计的原因大家继续往下看就会发现（利用第二个模板参数构造不同结构下的红黑树节点）。
3、红黑树结构中的泛型节点
当map与set都使用复用同一个红黑树模板，该如何使编译器区分这两种结构，并产生不同结构的红黑树节点成了一个艰巨的任务。
STL将红黑树的节点设计为一个模板类型（泛型）（根据传入类型而实例化不同类型的节点），利用红黑树模板参数中的value类型来进行实例化，value类型决定节点里面存什么，map与set的红黑树模板value接收的类型不同最终使得生成的节点类型不同，从而达到使编译器区分这两种结构，是key类型的set，还是（key，value）类型的map，并产生不同结构的红黑树节点。
下图时STL库中的map，set模板参数传递实例化红黑树及红黑树节点的流程展开图
对于在源码中存在很多typedef，可能看起来不太直观，我们将其流程化简，再来看一下map与set复用同一个红黑树模板的流程
利用向红黑树模板传递的第二个参数来构建红黑树节点，是key类型的就是set结构，是pair类型就是map结构。
4、红黑树的一个模板参数
既然我们用了红黑树模板的第二个模板参数来区分是map（kv）还是set（v），而且节点存放的类型也是由第二个模板参数决定的，那么对于第一个看似多余的key类型传递给红黑树有什么必要吗？
答案是非常有必要的，比如红黑树（kv）模式中，查找函数是利用key值查找value值，如果我们只有pair类型,没有key类型，那么如何接收向这个函数传递的参数呢？是不行，所以我们必须要有key值类型这个模板参数，来定义形参接收key值类型的变量。
甚至在有的时候我们要在kv模式下提取pair中的key值，需要有与key类型相同的变量进行接收，都会用到key值类型的模板参数。在这里做初步介绍，在后面部分还会给大家强调第一个模板参数的重大作用，要记住的就是，第一个模板参数不多于，且很重要！！！
5、红黑树的其他模板参数
KeyOfValue：如果这个树是kv结构的树，那么Value参数为pair,KeyOfVal是一个仿函数，作用就是提取value类型对象中的key类型的元素。
Compare：也是一个仿函数，提供红黑树管理某一类型数据时，这类型数据的比较逻辑。
后续模拟实现中，也会实现这两个模板参数，大家可以根据实际模拟更直观清楚的知道其具体作用，并且在使用时能够得心应手传递对应仿函数
二、map、set模拟封装
根据上述源码细节剖析，有些内容还是晦涩难懂。为了理解其细节更加深刻与透彻，依据STL中对set，map封装理念，根据之前博客《手撕红黑树》中的模拟红黑树为基础，实现对set，map的简单模拟封装，一步一步身临其境的体会其设计细节。
1、红黑树改造
我们在这里用T表示红黑树的第二个模板参数！！！！！
（1）、红黑树节点改造
map，set模板参数传递实例化红黑树及红黑树节点的流程展开图在STL分析部分已近展示，由于在源码中存在很多typedef，可能看起来不太直观，我们将其流程化简，再来看一下map与set复用同一个红黑树模板的流程。
利用向红黑树模板传递的第二个参数来构建红黑树节点，是key类型的就是set结构，是pair类型就是map结构。
利用同一个红黑树模板，根据模板参数的不同，构造出不同的节点，成为不同的结构，这就是我们需要改造节点的原因与目的。
下图原来的红黑树节点模板：
我们可以看到原来节点中的存储的数据类型，是利用节点模板的第一个模板参数和第二个模板参数实例化的pair类型对象，这是适用map的红黑树（kv结构）。对于set来说节点存储的数据类型就是k类型，没有v类型数据，更没有pair类型对象。这样就要单独写一个符合k结构的红黑树模板类，创建其独特的节点模板，实例化对应的节点来存储期望类型的数据（即存储k类型的数据），之后才能实例化出k结构的对象。（k结构的节点模板是单模板参数，kv结构的节点模板是两个模板参数）
为了利用同一个红黑树模板，就要在红黑树中使用单模板参数的泛型节点，利用实例化红黑树的第二个模板参数实例化节点，从而使得参数不同，红黑树的节点结构不同（适配不同结构k或者kv结构下的类型数据）。如上面的流程图，map实例化红黑树的模板参数为(k,pair),那么就是用pair类型来实例化红黑树节点,set实例化红黑树的模板参数为(k,k),那么就是用k类型来实例化红黑树节点。综上所述，就是利用红黑树模板的第二个模板参数来实例化节点，使用第二个模板参数为存储数据的类型。如下图改造后的红黑树节点
可以发现数据类型不在是原来固定的pair<k,v>,而是T类型，代表的可能是kv结构下红黑树传递的pair<k,v>类型,也有可能是k结构下红黑树传递的k类型。实现对红黑树模板传参不同，以达到实现不同结构红黑树的效果。
（2）红黑树节点比较
红黑树的底层为搜索二叉树，所以构建，及调整都是需要比较节点的k值大小的。对于节点结构的改变意味着我们的节点比较逻辑也要发生改变。
我们看到原来节点的数据是pair类型对象，那么我们只需要比较该键值对对象的的第一个元素就可以了（即_kv.first），但现在新的节点中数据类型为T。如果 T代表的是k类型（k结构），那么我们利用k类型的比较逻辑直接比较T类型的两个节点数据就可以了。但如果T代表的是pair（kv结构），我们则无法直接比较T类型的数据。因为pair的原比较逻辑是先按照键值对中的第一个元素比较，再按照第二个元素来比较，对于kv结构来说就是先按照k类型数据比较，再按照v类型数据比较。但我们实际对kv结构下的节点比较，期望是只按照k类型的数据来比较，此刻T的默认比较逻辑与实际需求不符，所以我们就要想办法改造他的比较逻辑。
这里采用的方法是利用仿函数取出T类型对象中k类型元素，然后再依据k类型的比较逻辑对k对象比较结果作为红黑树节点的比较结果。
上图就是利用红黑树的第三个模板参数KeyofT，创造该类型对象，借助其内部逻辑取出T类型对象中的k对象，再来比较。对于k结构来说，T代表的就是k，返回的就是T对象本身；对于kv结构来说，T代表的是pair,返回的就是T对象中的k类型对象。比较提取后的返回值。在红黑树中，所有涉及比较节点的代码部分都要修改，添加对节点数据的提取操作；
kv结构（map）与k结构（set）的提取逻辑不同，向红黑树传递的模板参数（仿函数）也不同，我们在后面对map，set的封装中会更加直观的看到。
（3）、红黑树第一个模板参数
第一个模板参数不多于，且很重要！！！
1、我们无法利用第三个模板参数，就是仿函数KeyOfT，取出T类型中的T类型，所以在需要创建或者接受k类型对象时要知道其类型，实例化时要把该类型作为模板参数传递过来。
2、在find中，无论哪种结构都是利用k类型对象来查找，利用到红黑树模板的第一个参数，也就是k类型，作为参数类型定义形参接收k类型对象，完成查找。
（4）、红黑树迭代器
迭代器是以统一的形式，屏蔽不同的底层结构细节，提供统一的访问格式，让我们使用，访问和修改容器数据的难度降低，成本降低。而红黑树的迭代器就是屏蔽红黑树的底层细节，来实现红黑树数据访问，遍历，修改。
1、迭代器结构
红黑树的迭代器本质就是对红黑树节点的封装。如下图可以看到我们红黑树结构的一个模拟，依旧是一个模板，适应不同的红黑树类型。模板参数T是红黑树节存储数据的类型；Ref是重载迭代器重载运算符（*）解引用的返回值类型，是对存储数据的引用类型；Pre是重载运算符（->）箭头的返回值类型，是数据地址的类型。在后面模拟这两个函数的时候也会和大家介绍。
红黑树中的迭代器实例化类型
2、begin（）与end（）
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最后一个元素，此处就不行。这里先保留疑问，关于如何处理在后面讲解。
下图是红黑树中begin（）的模拟实现代码。
3、operator++（）
begin我们知道了它是红黑树中最小节点，也就是最左节点，因为不考虑operator--的实现问题，所以不需要end()位置的迭代器进行--操作，必须要能找最后一个元素，我们就让end()迭代器指向空节点，那么我们先提供只适合++实现的end（）的代码实现：
解决方法：
情况一：迭代器指向节点的右边不为空
++后的下一个节点就是右子树的最左节点
情况二：迭代器指向节点的右边为空
说明这颗子树的中序访问完了，这时候向上不断找，下一个节点是祖先里面，孩子是父亲左的那个父亲节点，这也作为循环的退出条件。改变迭代器中的节点指针，指向parent节点；
细节：
1、在第二种情况处理办法中，最后如果一直没有找到符合退出循环条件的节点，也就是当父亲节点（parent）变成空，说明找到了根节点，返回nullptr，即 end（）；
2、在++过程中改变的是迭代器对象中的指针，最终返回当前对象，即*this
4、operator--()
处理情况与处理方法都与operator++相似，只是处理方向不同。但要注意此刻我们end（）的迭代器中的节点指针是nullptr，对end()位置的迭代器进行--操作，必须要能找最后一个元素，要进行特殊处理。
情况一：迭代器指向节点的左边不为空
--后的下一个节点就是左子树的最右节点
情况二：迭代器指向节点的左边为空
说明这颗子树的中序访问完了，这时候向上不断找，下一个节点是祖先里面，孩子是父亲右的那个父亲节点，这也作为循环的退出条件。改变迭代器中的节点指针，指向parent节点；
情况三：end（）--
阶段一
在这里我们使用的end（）的迭代器中的节点指针是nullptr，我们做一个特殊处理，希望--以后必须要能找最后一个元素。特殊处理就是如果迭代器指向空，那么--操作后就让迭代器指向整棵树的一个最右边节点；。这种解决办法有两个缺陷：
一、是最右边节点找起来很麻烦，此刻迭代器指针指向nullptr就不能采用向上查找的方法找到最祖先节点，再找最右边节点；这就需要我们提前存储一份红黑树最右节点的指针。增加对应的特殊处理办法。
二、对于空树无法处理。
阶段二
此时我们采取一种新的解决方式——增加红黑树哨兵位节点，这也是上文中保留的疑问的解决。
哨兵位节点颜色是红色的，其左右节点分别链接红黑树的最左节点与最右节点，这样就可以直接方便的找到最左节点与最右节点。哨兵位节点为end（）迭代器指向节点，就可以实现end（）--操作，直接找到最右节点。
补充：对于是哨兵位节点的判断（判断是end（）指向的节点）
在本次模拟中，增加哨兵位节点对整个红黑树改变较大，本次没有对此方案进行模拟，大家可以下去之后自己尝试。
5、迭代器的其他操作
解引用操作符
箭头操作符
等于操作符
不等于操作符
6、const迭代器的完善
迭代器是一个模板，只要传递const类型的模板参数给迭代器实例化，那么迭代器中的数据无论如何都不会被修改。
当然还需要提供const版本的begin（），end（）
（5）、insert返回值
为支持map方括号操作，将insert（）的返回值类型修改成pair<iterator,bool>；
返回值规则：
1、如果插入值已经有了，说明插入失败，就返回pair<指向已有节点的红黑树迭代器，false>
2、如果插入值不存在，说明插入成功，就返回pair<指向新插入节点的红黑树迭代器，true>
2、map与set封装
1、红黑树实例化参数
set
实例化化红黑树对象为成员变量（封装）
红黑树节点
和之前对STL中分析的一样，由于k结构，kv结构都是用同一个红黑树模板，第二个参数是区分和构建不同模式的关键,用来构造k结构下的节点及数据。于是set对红黑树的封装实例化，第一个模板参数和第二个模板参数都为k类型。
set中希望数据不能被修改，也就是红黑树中的数据不能修改。由于构建红黑树节点的是红黑树的第二个模板参数，所以将红黑树的第二个模板参数添加const关键字，保证红黑树中的数据不能修改，满足set要求。（防止使用对应迭代器时，数据可以被修改）
map
实例化化红黑树对象为成员变量（封装）
红黑树节点
和之前对STL中分析的一样，由于k结构，kv结构都是用同一个红黑树模板，第二个参数是区分和构建不同模式的关键，用来构造kv结构下的节点及数据。于是map对红黑树的封装实例化，第一个模板参数为k，第二个模板参数为pair类型。
map中希望键值对的键（键值对的第一个元素）不能被修改，也就是kv结构下红黑树中的k数据不能修改。由于构建红黑树节点的是红黑树的第二个模板参数，所以将红黑树的第二个模板参数pair的第一个模板参数添加const关键字，保证红黑树中的键数据不能修改，值可以修改，满足map要求。（防止使用对应迭代器时，数据可以被修改）
2、红黑树节点比较
我们在上面看到set，map对于红黑树的封装还有第三个模板参数，第三个模板参数是一个仿函数，借助其内部逻辑取出T类型对象中的k类型对象，对k类型对象进行比较。
对于set来说，节点的模板参数T代表的就是k，仿函数的重载（）返回值的就是T类型对象本身（添加const，保证其值是不被修改的）；对于仿函数的参数，其类型就是实例化set的模板参数k（添加const，保证其值是不被修改的），固将仿函数写为容器的内部类，在这里就是set的内部类；所以为了具体仿函数如下图：
对于map来说，节点的模板参数T代表的就是pair，仿函数的重载（）返回值的就是T类型对象中的第一个元素，也就是const k类型的元素；对于仿函数的参数，其类型就是实例化map的模板参数k，v构成的键值对类型（添加const关键字，保证其值是不被修改的），固将仿函数写为容器的内部类，在这里就是map的内部类；所以为了具体仿函数如下图：
在使用时创建仿函数对象，利用其内部逻辑取出红黑树数据中的k类型数据，再利用k类型数据的比较逻辑比较k类型的数据，作为红黑树数据的比较结果。
3、map，set迭代器
map，set迭代器，仍然是对其对应实例化出来的的红黑树的迭代器的封装
set迭代器
对应实例化红黑树中迭代器的名称统一（普通迭代器与const迭代器）
注意：类模板里取东西，编译器不知道是类型还是静态成员变量，借助typename告诉编译器是类型
对红黑树对象中迭代器函数的封装调用（普通迭代器与const迭代器）
map迭代器
对应实例化红黑树中迭代器的名称统一（普通迭代器与const迭代器）
对红黑树对象中迭代器函数的封装调用（普通迭代器与const迭代器）
4、set、map对其他函数的封装
1）、插入函数：
set
map
1、各自插入函数的参数类型与各自结果存储数据的类型相同
2、封装后的返回值与对应于红黑树插入返回值相同
2）、查找函数
（set，map相同，都是利用k类型对象查找）
5、map方括号【】
利用插入函数的返回值来完成。
参数为k类型元素，先按照k值向红黑树插入，再提取插入得到的返回值；插入成功返回值是指向新节点的迭代器+true，插入失败说明已存在该数据，返回值的是指向已有节点的迭代器+false。而方括号的返回值是对提取得到的迭代器解引用后的的pair对象的第二个元素的引用。也就是说当你对返回值进行修改操作，也就意味着直接改变迭代器指向节点所存储的键值对的值（value）。
满足以下功能：
1、k类型元素不存在，插入pair键值对，并且修改键值对的v类型对象。
2、k类型元素存在，修改已有键值对中的v类型对象。
利用统计水果个数测试方括号功能：
结束语
本篇文章的内容就到此结束了，希望通过这篇博客大家能够更深刻的理解set与map的底层设计，对红黑树这一结构更加熟悉能够运用自如。对于这方面大家有什么内容不明白的，可以在评论去向我提问，我会一一回答，当然有什么错误或者有什么不足的地方，希望大家可以包容并指出，后续还会更新c++的其他知识，希望大家可以持续关注，向每一位读者送上真诚的小花。
附录
改造后的红黑树类模板
#pragma once
namespace zwb
{
enum Color { RED, BLACK };
//改造红黑树类模板，使mymap，myset适用同一个红黑树类模板
template <class T>
struct RBTreeNode {
typedef RBTreeNode<T> Node;
Node* _parent;
Node* _left;
Node* _right;
Color _col;
T _data;
RBTreeNode(const T& data)
:_parent(nullptr),
_left(nullptr),
_right(nullptr),
_col(RED),
_data(data)
{}
};
//红黑树迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T,Ref,Ptr> self;
RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
//利用箭头取pair中的first，或者second，此处有特殊处理，有一个箭头被省略了（(&pair)->first/second）
return &_node->_data;
}
//迭代器++操作
self& operator++()
{
//1、迭代器指向节点的右边不为空，下一个节点就是右子树的最左节点
if (_node->_right)
{
Node* subleft= _node->_right;
while (subleft->_left)
{
subleft = subleft->_left;
}
_node = subleft;
}
//2、迭代器指向节点的右边为空，说明颗子树的中序访问完了
//向上不断找，下一个节点是祖先里面，孩子==父亲左的那个父亲节点
//当parent变成空，说明找到了根节点，返回nullptr，即 end（）
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
//封装节点指针
//迭代器--操作
self& operator--()
{
//特殊处理end（）节点--操作
if (_node == nullptr)
return *this;
//1、迭代器指向节点的左边不为空，下一个节点就是左子树的最右节点
if (_node->_left)
{
Node* subr = _node->_left;
while (subr->_right)
{
subr = subr->_right;
}
_node = subr;
}
//2、迭代器指向节点的左边为空，说明颗子树的中序访问完了
//向上不断找，下一个节点是祖先里面，孩子==父亲右边的那个祖先节点
//当parent变成空，说明找到了根节点，返回nullptr，即 rend（）
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
Node* _node=nullptr;
};
//需要提供将key值从_data中提取出来的的仿函数keyofT
//map中对应的数据类型是pair，pair支持的比较是先按照first比较，如果first比较失败，则会再根据second来比较
//预期是只用first比较，与逾期不符，利用keyofT从T中取出key，再进行比较
//更新所有的比较方式
template<class K, class T, class KeyofT>
class RBTree {
typedef RBTreeNode<T> Node;
public:
//迭代器
typedef RBTreeIterator<T,T&,T*> iterator;
typedef RBTreeIterator<T,const T&,const T*> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur&&cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
//为支持map方括号操作，这里的返回值修改成pair<iterator,bool>
pair<iterator,bool> Insert(const T& data) {
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
KeyofT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
return make_pair(iterator(cur),false);
}
cur = new Node(data);
//要返回新插节点的迭代器，提前保存节点
Node* newnode = cur;
if (kot(data) < kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* grandfather = nullptr;
Node* uncle = nullptr;
while (parent && parent->_col == RED)
{
//父亲节点为红色，有连续红色，需要特殊处理，此时一定存在爷爷节点
grandfather = parent->_parent;
//一、parent在grandfather的左边，说明uncle在右边
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
//1、uncle存在，且uncle为红色
//parent，uncle变黑色，grandfather变红色，并且继续向上处理
//********* 不关心uncle的方向 *******
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//需要继续向上处理，直到退出循环；
cur = grandfather;
parent = cur->_parent;
}
//2、uncle不存在，或者uncle存在且为黑色, 利用旋转的方式处理，
//********** uncle左右位置不同，处理方式不同
else
{
//(1)cur是parent的左边，右旋grandfather，
// 变色：p变黑，g变红
// g
// p u
// c
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
//(2)cur是parent的有右边，左旋parent，右旋grandfather
//变色： c变黑，g变红
// g
// p u
// c
else
{
RotateL(parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
//旋转后以grandfather为根的子树每条路径的黑色节点数与没插入之前相同，不影响其他路径，不继续向上处理，退出循环
//处理完根是黑的，直接退出；
break;
}
}
//二、parent在grandfather的右边，说明uncle在左边
else
{
uncle = grandfather->_left;
//1、uncle存在，且uncle为红色
//parent，uncle变黑色，grandfather变红色，并且继续向上处理
//********* 不关心uncle的方向 *******
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//需要继续向上处理，直到退出循环；
cur = grandfather;
parent = cur->_parent;
}
//2、uncle不存在，或者uncle存在且为黑色 利用旋转的方式处理
//********** uncle左右位置不同，处理方式不同
else
{
//(1)cur是parent的右边，左旋grandfather，
// 变色：p变黑，g变红
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
//(2)cur是parent的左边，右旋parent，左旋grandfather
//变色： c变黑，g变红
// g
// u p
// c
else
{
RotateR(parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
//旋转后以grandfather为根的子树每条路径的黑色节点数与没插入之前相同，不影响其他路径，不继续向上处理，退出循环；
//处理完根是黑的，直接退出；
break;
}
}
}
//最后让根节点的颜色一定为黑色，不在循环里面单独判断是否为根节点
_root->_col = BLACK;
return make_pair(iterator(newnode),true);
}
//左旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//处理parent与subRL新关系的链接
parent->_right = subRL;
//subRL不为空，其父节点指向parent
if (subRL)
subRL->_parent = parent;
//处理parent与subR新关系的链接
subR->_left = parent;
Node* ppnode = parent->_parent;//保存旧parent的父亲节点与subR节点链接
parent->_parent = subR;
//处理parent的父亲节点与subR节点链接
//parent可能是根节点
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
subR->_parent = ppnode;
}
}
//右旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
//中序遍历
void Inorder()
{
_inorder(_root);
cout << "end" << endl;
}
void _inorder(Node* root)
{
if (root == nullptr)
return;
_inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_inorder(root->_right);
}
iterator find(const K& key)
{
Node* cur = _root;
KeyofT kot;
while (cur)
{
if (key < kot(cur->_data))
{
cur = cur->_left;
}
else if (key > kot(cur->_data))
{
cur = cur->_right;
}
else
return iterator(cur);
}
return iterator(nullptr);
}
private:
Node* _root = nullptr;
};
}
set封装代码
#pragma once
namespace zwb
{
template<class K>
class set
{
struct SetKeyofT
{
const K operator()(const K& data)
{
return data;
}
};
public:
//类模板里取东西，编译器不知道是类型还是静态成员变量，typename告诉编译器是类型，
typedef typename RBTree<K, const K, SetKeyofT>::iterator iterator;
typedef typename RBTree<K, K,SetKeyofT>::const_iterator const_iterator;
const_iterator begin() const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& data)
{
return _t.Insert(data);
}
iterator find(const K& key)
{
return _t.find(key);
}
private:
RBTree<K, const K, SetKeyofT> _t;
};
}map封装代码
namespace zwb
{
template<class K, class V>
class map
{
//用于取出(data)pair<k,v>中的k值
struct MapKeyofT
{
const K operator()(const pair<K, V>& data)
{
return data.first;
}
};
public:
//迭代器
//类模板里取东西，编译器不知道是类型还是静态成员变量，typename告诉编译器是类型，
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
//查找
iterator find(const K& key)
{
return _t.find(key);
}
pair<iterator,bool> insert(const pair<K,V>& data)
{
return _t.Insert(data);
}
//重载方括号
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return (*(ret.first)).second;
}
private:
RBTree<K, pair<const K, V>, MapKeyofT> _t;
};测试代码
void test_set1()
{
set<int> s;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
s.insert(e);
}
set<int>::iterator it = s.begin();
while (it != s.end())
{
/*if(*it % 2 == 0)
*it += 100;*/
//保证迭代器不能修改，传参时候，传参为const类型
cout<< *it << " ";
++it;
}
cout << endl;
}
void test_map1()
{
map<int, int> m;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
m.insert(make_pair(e, e));
}
map<int,int>::iterator it = m.begin();
while (it != m.end())
{
/*if(it->first % 2 == 0)
it->first+= 100;*/
//保证map的key不可修改，在pair中传参const K
cout << it->first<<" : " <<it->second << endl;
++it;
}
cout << endl;
}
void test_find()
{
map<int, int> m;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
m.insert(make_pair(e, e));
}
auto f = m.find(3);
cout << f->first << endl;
set<int> s;
for (auto e : a)
{
s.insert(e);
}
auto sf = s.find(3);
cout <<*sf << endl;
}
void test_sub()
{
map<int, int> m;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
m.insert(make_pair(e, e));
}
auto f = m.find(15);
cout << (--f)->first << endl;
cout << (--f)->first << endl;
cout << (--f)->first << endl;
cout << (--f)->first << endl;
cout << (--f)->first << endl;
set<int> s;
for (auto e : a)
{
s.insert(e);
}
auto sf = s.find(15);
cout << *(--sf) << endl;
cout << *(--sf) << endl;
cout << *(--sf) << endl;
cout << *(--sf) << endl;
cout << *(--sf) << endl;
}
void test_constiterator()
{
const map<int, int> m;
map<int, int>::const_iterator it = m.begin();
while (it != m.end())
{
cout << it->first << " : " << it->second << endl;
++it;
}
cout << endl;
}
void test_bracket()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };
map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main() {
//test_map1();
//test_set1();
//test_find();
//test_sub();
test_bracket();
return 0;
}
