用红黑树封装出set和map

因为STL库中的set和map就是用红黑树封装出来的，所以下面我们将对一棵KV模型的红黑树进行封装，去模拟实现set和map

Q：如何理解STL库中的set和map是用红黑树封装的 这句话？

A：set和map的成员变量是一个红黑树的对象，set和map的任何函数以及迭代器的调用本质都是调用这个红黑树对象的对应的函数和迭代器！

本博客基于手撕红黑树-CSDN博客的基础上讲解，所以红黑树的起始代码如下：

#pragma once
#include<vector>
//枚举
enum Colour
{RED,BLACK
};//节点类
template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;//颜色变量RBTreeNode(const pair<K, V>& kv)//节点类的构造函数:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};//红黑树类
template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://插入函数bool Insert(const pair<K, V>& kv){//空树情况if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;//直接return了}//开始找插入的位置Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else//发现已经存在了相同的值 则返回假{return false;}}//走到这里代表找到了插入的位置//将cur进行插入        cur = new Node(kv); //新的节点已经被设置为红色的if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//父亲存在且父亲为红代表要继续循环while (parent && parent->_col == RED){    //记录gNode* grandfather = parent->_parent;//p为g的左if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else//情况二{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//p为g的左且c为p的左 则右单旋if (cur == parent->_left){//       g//    p    u(存在且为黑或不存在)// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//p为g的左且c为p的右 则左右双旋{//       g//    p     u((存在且为黑或不存在))//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转后代表红黑树已经合理 所以break 不再通过循环判断break;}}else//p是g的右{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//         g//   u(...)     p//           c//p是g的右且c是p的右  左单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//p是g的右且c是p的左  右左单旋{//         g//   u(...)     p//           cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}//旋转后代表红黑树已经合理 所以break 不再通过循环判断break;}}}//最后的根一定为黑 不再在代码中进行特判 直接暴力解决_root->_col = BLACK;return true;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){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(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}//检查函数			路径的黑色个数   计算好的标准值bool Check(Node* cur, int blackNum, int refBlackNum){	//执行这里则代表：空树或算完一条路径了if (cur == nullptr){//某条路径的黑色值和标准值不相等?if (refBlackNum != blackNum){cout << "黑色节点的数量不相等" << endl;return false;}return true;}//有连续的红?if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}//遇到黑色节点则++lackNumif (cur->_col == BLACK)++blackNum;//递归 本质是前序遍历return Check(cur->_left, blackNum, refBlackNum)&& Check(cur->_right, blackNum, refBlackNum);}bool IsBalance(){//根节点为红?if (_root && _root->_col == RED)return false;int refBlackNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refBlackNum++;//计算一条路径的黑色个数cur = cur->_left;}//然后以这条路径的黑色个数为标准值 去看其余的每条路径是否都一样return Check(_root, 0, refBlackNum);}//节点个数函数size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}//查找函数Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}//高度函数int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int Height(){return _Height(_root);}private:Node* _root = nullptr;
};

引入：我们的红黑树有什么不足？

先看一下库中的set和map的使用：

int main()
{//体现原有红黑树需要实现set的迭代器set<int> s;s.insert(1);s.insert(3);s.insert(2);s.insert(4);s.insert(5);set<int>::iterator it1 = s.begin();while (it1 != s.end()){cout << *it1 << " ";it1++;}cout << endl;//体现原有红黑树需要实现map的迭代器map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));m.insert(make_pair(4, 4));m.insert(make_pair(5, 5));map<int, int>::iterator it2 = m.begin();while (it2 != m.end()){cout << it2->first << ":" << it2->second << " ";it2++;}cout << endl;//体现原有红黑树需要实现map的[ ]string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;
}

运行如下： 

由此得到我们的红黑树相比与库中去封装set和map的红黑树的四点不足：

四个不足：

①：我们红黑树结构需要优化，以便既能够成为K模型，又要能成为KV模型

从库中的set和map的使用可以看出，set<int> s; map<int, int> m; 无论是K模型还是KV模型都能使用红黑树，而我们的红黑树已经固定了为KV模型，所以我们红黑树结构要改为既能够成为K模型，又要能成为KV模型

②：比较节点的值的方法优化，以便既能比较K模型的K值，又要能比较KV模型的K值

③：我们的红黑树还需要实现出迭代器

④：map的[ ]的实现

一：优化红黑树的结构

回顾：

Q：如何理解STL库中的set和map是用红黑树封装的 这句话？

A：即set和map的成员变量是一个红黑树的对象，set和map的任何函数以及迭代器的调用本质都是调用这个红黑树对象的对应的函数和迭代器！

所以我们的更改红黑树的结构分为两步：

①：在set和map的内部分别创建红黑树对象时，能分别适配出K模型和KV模型

②：所以要更改红黑树的模版参数

这是一个很妙的地方，仅仅更改红黑树的模版参数，仅能达到效果

①：在set和map的内部分别创建红黑树对象时，能分别适配出K模型和KV模型

set：

    //set类template<class K>class set{//.......private:成员变量即红黑树对象RBTree<K,  K> _t;};

map： 

    //map类template<class K, class V>class map{private://成员变量即红黑树对象RBTree<K, pair< K, V> > _t;};

②：更改红黑树的模版参数

//枚举
enum Colour
{RED,BLACK
};//节点类
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;//T是K模型即创建K类型的变量 KV模型即创建pair类型的变量RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};//红黑树类
template<class K, class T>
class RBTree
{//节点类的简写Nodetypedef RBTreeNode<T> Node;}

解释：

Q：为什么这样就能做到像库中的set<int> s; map<int, int> m;的使用了？

A：先看set：

再看map：

总结：（红黑树类的第二个模板参数，就是红黑树节点存储的类型）

①：我们的set和map的内部，创建红黑树对象的时候，

不再只传：K和pair<K, V>；

而是传：K，K 和 K，pair<K, V>

②：红黑树类的模版参数是K 和 T ，T就负责接收传过来的第二个参数，用去创建一个节点

③：set即K给T，去创建一个类型为k的节点        

       map即pair<K, V>给T，去创建一个类型为pair<K, V>的节点

所以就做到了红黑树既能成为K模型又能成为KV模型！

Q：那红黑树的一个模版参数K的意义岂不是多余了，能不写吗？

A：不可以，尽管红黑树的第二个模板参数T当中也是有K值的，但实际上红黑树的第一个模板参数是不能省略的。因为：在map中像find这种函数 参数包含红黑树的第一个模板参数K的就必须要第一个模版参数的存在才可以：

其的函数声明为：iterator find(const K& key)  这里接收的类型就需要 第一个模版参数K！

二：比较节点的值的优化

我们之前红黑树写死了为KV模型，所以我们比较节点的值的时候，也是写死了取pair类型的first来比较

但是现在我们红黑树的比较既要适用K模型的比较又要适用KV模型的比较，也就是说：

现在由于结点当中存储的是T，这个T可能是K，也可能是<K, V>键值对，不管是哪种，我们都需要取其中的K比较，所以我们用仿函数来解决即可，仿函数的功能就是取出其中的K值即可，这样我们红黑树中得到了两个类型的K值，自行比较就可以了！

Q：我们的仿函数写在哪里？

A：当然是写在set和map中最好，以便set将仿函数类传给红黑树，map将仿函数类传给红黑树

set类：

template<class K>
class set
{//仿函数struct SetKeyOfT{const K& operator()(const K& key) //返回键值Key{return key;}};
public://...
private:RBTree<K, K, SetKeyOfT> _t;
};

map类：

template<class K, class V>
class map
{//仿函数struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key{return kv.first;}};
public://...
private:RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

Q：set不写仿函数不可以吗，其类型就是K值，可以直接比对啊？

A：对于底层红黑树来说，它并不知道上层容器是set还是map，因此当需要进行两个结点K值的比较时，底层红黑树都会通过传入的仿函数来获取值K，进而进行两个结点键值的比较。所以为了统一，你必须写。

仿函数作用如下：

所以我们的红黑树的模版参数又得增加一个参数去接收仿函数对象 

取名KeyOfT(意为取T中的K值)，当我们在需要比较K值的函数中，会先创建一个 KeyOfT类的对象，以便去触发重载的()的作用

template<class K, class T, class KeyOfT>
class RBTree
{//.......
}

用需要比较Key值的函数体现仿函数的作用--->以Find函数为例吧：

//查找函数iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}

 解释：

kot(cur->_data)

触发重载的()，获取到了_data的K值 

set为K，map为pair.first

三：迭代器的实现

①：正向迭代器的实现

老生常谈了，必然是对节点指针进行封装为一个迭代器类，在该类中重载++，--等运算符，以达到我们想要的效果，但是难就难在如何达到我们想要的效果~，先看看封装吧：

//红黑树的迭代器类
template<class T, class Ptr, class Ref>
struct RBTreeIterator
{//节点类的简写Nodetypedef RBTreeNode<T> Node;//返回值为迭代器简写为Selftypedef RBTreeIterator<T, Ptr, Ref> Self;//成员变量Node* _node;//构造函数//对接收到的节点指针赋给迭代器类的成员变量(节点指针)//接收方式一般为begin()函数的返回值--> it.begin();RBTreeIterator(Node* node):_node(node){}//....重载运算符
};

解释：

这样正向迭代器不管是否为const迭代器都能适用~

先重载一下简单的运算符：

    //对*重载Ref operator*(){return _node->_data;}//对->重载Ptr operator->(){return &_node->_data;}//对!=重载bool operator!=(const Self& s){return _node != s._node;}//对==重载bool operator==(const Self& s){return _node == s._node;}

++的重载：

++的效果应该是按照中序遍历的顺序进行遍历

左 根 右

例子：

需要知道的是，迭代器一般是按照以下方法调用

set<int>::iterator it1 = s.begin();

此时这里的begin()函数返回了中序遍历的第一个节点的指针，即图中的1的节点指针

所以我们的++此时的参数就是这个K值为1的节点指针

Q：那怎么找1的下一个呢：

A：具体逻辑如下：(中序：左 根 右)

①：如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。

解释：右子树的最左节点 就是当前节点的 直接后继。

②：如果当前结点的右子树为空，就向上找，直到遇到某个祖先节点是它父节点的左孩子，这个父节点就是后继节点。

解释：向上回溯，找到第一个 某个节点是其父节点的左孩子 的这个父节点。

这样我们就可以按照中序的遍历走完所有节点，如果你还懵逼，放心，我将会继续距离详细解释~

例子：

①：以节点8为例，找8的下一个节点

如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。

当前结点的右子树不为空。所以8的右子树中的最左节点即下一个

因为：

1：右子树即代表都比当前节点8大

2：右子树的 最左节点 是右子树中最小的节点，因此它是最接近当前节点的更大值。

②：以节点6为例，找6的下一个节点

如果当前结点的右子树为空，就向上找，直到遇到某个祖先节点是它父节点的左孩子，这个父节点就是后继节点。（切记是父节点，而不是这个孩子节点~）

因为：

6的右子树为空，下一个则是8，因为此时向上找，1不是1的父节点的左孩子，再向上找，8是8的父节点的左孩子

那②这条规则的原理是什么？原理是中序的顺序：左 根 右

当6节点的右为空，再结合中序的顺序：左 根 右，则代表6节点为根节点的子树已经全部按照中序访问完了，此时就该回到上层调用6节点的节点，但此时有两种可能：

可能1：6节点是被上一个节点按照中序的顺序：左 根 右  中的左调用的

可能2：6节点是被上一个节点按照中序的顺序：左 根 右  中的右调用的

而是不管是哪一种可能，6节点都是已经结束了的

但是若是可能1，则直接回到上层节点即可，因为此时的上层节点还未访问 根 右 这两步

若是可能2，则代表上层节点也已经结束，要找到某个上层节点且该节点是被一个节点按照可能1（中序的顺序：左 根 右  中的左调用的来调用的）

总结一下，要找到某个祖先节点是它父节点的左孩子，这个父节点就是后继节点。

尽力了，只能解释到这个地步了，画图理解理解吧~

所以++的代码：

//前置++
Self operator++()
{if (_node->_right) //结点的右子树不为空{//寻找该结点右子树当中的最左结点Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left; //++后变为该结点}else //结点的右子树为空{//寻找孩子不在父亲右的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent&&cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent; //++后变为该结点}return *this;
}

--的重载：

--的效果应该是按照中序遍历的相反顺序进行遍历 即 右 左 根

所以：

具体逻辑如下：

①：如果当前结点的左子树不为空，则--操作后应该找到其左子树当中的最右结点。

解释：左子树当中的最右结点。 就是当前节点的 直接前驱。
②：如果当前结点的左子树为空，就向上找，直到遇到某个祖先节点是它父节点的右孩子，这个父节点就是前驱节点。

解释：向上回溯，找到第一个 某个节点是其父节点的右孩子 的这个父节点。

继续举例子讲解：

例子：

①：以节点8为例

当前结点的左子树不为空，则--操作后应该找到其左子树当中的最右结点。就是节点6

因为：

1：左子树即代表都比当前节点8小

2：左子树的 最右节点 是左子树中最大的节点，因此它是最接近当前节点的更小值。

②：以节点6为例

当前结点的左子树为空，就向上找，直到遇到某个祖先节点是它父节点的右孩子，这个父节点就是前驱节点。就是节点1

所以6的左子树为空，此时向上找，6是6的父节点的右孩子，所以就是1

原理：中序颠倒：右 根 左 

不再赘述........

所以--的代码：

//前置--
Self operator--()
{if (_node->_left) //结点的左子树不为空{//寻找该结点左子树当中的最右结点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right; //--后变为该结点}else //结点的左子树为空{//寻找孩子不在父亲左的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent&&cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent; //--后变为该结点}return *this;
}

 所以：总的迭代器类的代码如下：

template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}//对*重载Ref operator*() {				return _node->_data;}//对->重载Ptr operator->(){return &_node->_data;}//对++重载Self& operator++(){if (_node->_right){// 右子树的中序第一个(最左节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//对--重载Self& operator--(){// 跟++逻辑相反return *this;}//对!=重载bool operator!=(const Self& s){return _node != s._node;}//对==重载bool operator==(const Self& s){return _node == s._node;}
};

②：几个类之间的模版传递以便使用迭代器

Q：我们现在在红黑树这个.h文件中实现出了一个迭代器类，那我们怎么让这个迭代器类达到贯穿全文的去使用呢？

我们平时的set和map大多是像下面这样使用迭代器：

//set：
set<int>::iterator it = s.begin();//map：
map<int, int>::iterator it = m.begin();

第一步：

所以在红黑树的.h当中实现了迭代器类后，还需要在红黑树类域中进行迭代器类的typedef。

然后再在红黑树当中实现调用迭代器begin和end：

template<class K, class T, class KeyOfT>
class RBTree
{//节点类的简写Nodetypedef RBTreeNode<T> Node;//T = const K
public://红黑树类中的迭代器类的typedeftypedef RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, const T*, const T&> const_iterator;//迭代器beginiterator begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}//迭代器enditerator end(){return iterator(nullptr);}

解释：

①：begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点；当空树的时候，begin返回的就是nullptr
②：end函数返回中序序列当中最后一个结点下一个位置的正向迭代器(左闭右开)，这里直接返回nullptr就好了

③：这样我们在遍历的时候begin()!=end()，即能完美作为判断条件

第二步：

首先由我们上面set map使用迭代器的方式中的“: :”这个符号可知，在set和map的类域中，一定是有一个迭代器类型的，且还有begin() end()这种调用迭代器的函数；

所以，set和map一定是在自己的类域中对红黑树的迭代器进行了typedef成了自己的迭代器，毕竟set和map什么都靠红黑树：

//set类域中：
typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;//set自己的begin 也是 复用的红黑树.h文件里面的begin
iterator begin()
{return _t.begin();
}//同理 复用
iterator end()
{return _t.end();
}//------------------------------------------------------//map类域中：
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;//同理 复用
iterator begin()
{return _t.begin();
}//同理 复用
iterator end()
{return _t.end();
}//解释：需要 typename 来明确 ::iterator 这是一个类型 否则会报错

这样我们set和map都能像上面的例子那样调用迭代器了~

最后需要注意的一点是：

博主在最前面的set和map的类域中创建红黑树对象的时候，博主传的参数如下： 

//set类中：
RBTree<K, K, SetKeyOfT> _t;//map类中：
RBTree<K, pair< K, V>, MapKeyOfT> _t;

解释：其实这是错的，这样传只是方便前面的讲解，为什么错？因为我们的set和map的K值，都是不允许被修改的，这是库中的set和map的性质所以，更改如下：

//set类中：
RBTree<K, const K, SetKeyOfT> _t;//map类中：
RBTree<K, pair<const K, V>, MapKeyOfT> _t;

这样我们set用迭代器，就能达到K值不能被修改，map用迭代器，能达到K值不能修改，V值可以修改的效果！

由于程序的模版过多，所以博主画了set使用迭代器时，整个程序的模板参数的传递过程！

由于宽度有限，建议保存下来再打开看

set：

map和这个是类似的，只不过是set中的const int变成了pair<const int，int> ，然后迭代器中的Ptr变成了pair<const int，int>*，Ref变成了pair<const int，int>&，均达到了map的K值无法被修改，但是map的V值可以被修改

测试一下迭代器：

写在set类中的测试用例：

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()){//*it += 100;cout << *it << " ";++it;}cout << endl;}

效果如下：

释放开测试用例的注释代码，也就是试一下修改set的K值，报错如下：

写在map类中的测试用例：

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()){//it->first += 100;it->second += 100;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}

效果如下：

 成功的修改了V值

释放开测试用例的注释代码，也就是试一下修改map的K值，报错如下：

 至此，一个简单的正向非const迭代器，就完成了！

注意：

如果你想知道正向const迭代器，和反向非const迭代器和反向const迭代器，如何写，博主将其作为额外了解卸载了本篇博客的文末，这部分，个人觉得是红黑树的重难点，但理解了，有助于你对红黑树的认识

四：map的[ ]的实现

在map类中进行以下操作即可：

	pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}

[ ]的功能，博主已经在map的[ ]的解析_如果用map读取ref([])对象-CSDN博客 中讲过

在map类中进行[ ]的测试：

void test_map2(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}

效果如下：

五：源码

①：RBTerr.h (红黑树的头文件)

#pragma once
#include<vector>//枚举
enum Colour
{RED,BLACK
};//节点类
template<class T>// T = const K 
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};
//map：<T = pair<const int, int> ，T* = pair<const int, int>*，T& = pair<const int, int>&>
//set：因为T是const int
//             ↓
//迭代器类的模版参数：<T = const int， Ptr = const int*， Ref = const int&>//map：因为T是 pair<const int, int>
//             ↓
//迭代器类的模版参数：<T =  pair<const int, int>， Ptr =  pair<const int, int>*， Ref =  pair<const int, int>&>
template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}//对*重载Ref operator*() //返回值为：const int& 意味着set的k无法修改{				//返回值为：pair<const int, int>& 意味着map的k无法修改 但v可以return _node->_data;}//对->重载Ptr operator->()//返回值为:const int* 意味着不能通过指针修改K值{				//返回值为：pair<const int, int>* 意味着不能通过指针修改K值 但V可以return &_node->_data;}//对++重载Self& operator++(){if (_node->_right){// 右子树的中序第一个(最左节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//对--重载Self& operator--(){// 跟++逻辑相反return *this;}//对!=重载bool operator!=(const Self& s){return _node != s._node;}//对==重载bool operator==(const Self& s){return _node == s._node;}
};//红黑树类
template<class K, class T, class KeyOfT>
class RBTree
{//节点类的简写Nodetypedef RBTreeNode<T> Node;//T = const int
public://set：<T = const int ，T* = const int* ，T& = const int&>//map：<T = pair<const int, int> ，T* = pair<const int, int>* ，T& = pair<const int, int>&>typedef RBTreeIterator<T, T*, T&> iterator;//正向迭代器beginiterator begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}//正向迭代器enditerator end(){return iterator(nullptr);}//查找函数iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}//插入函数 库中的insert返回的就是一个pair类型 因为其是和[ ]搭配的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(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data); // 红色的Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){//       g//    p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//       g//    p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){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;}}private:Node* _root = nullptr;
};

②：MySet.h (set的头文件)

#pragma once
#include"RBTree.h"
namespace bit
{template<class K>class set{// 仿函数（函数对象）// 功能：提取key值// operator()接收一个K类型的参数，返回这个k就行（即key）struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;//set自己的begin 也是 复用的红黑树.h文件里面的beginiterator begin(){return _t.begin();}//同理 复用iterator end(){return _t.end();}//同理 复用pair<iterator, bool> insert(const K& key){return _t.Insert(key);}//同理 复用iterator find(const K& key){return _t.Find(key);}private://所以map的成员变量->一个红黑树类的对象RBTree<K, const K, SetKeyOfT> _t;};//------------------------------------------------------------------//测试用例//测试迭代器是否达到无法修改K值的效果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()){//*it += 100;cout << *it << " ";++it;}cout << endl;}
};

③：MyMap.h (map的头文件)

#pragma once
#include"RBTree.h"
namespace bit
{template<class K, class V>class map{// 仿函数（函数对象）// 功能：从pair<K, V>中提取key值// operator()接收一个pair<K, V>类型的参数，返回其first成员（即key）struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;//同理 复用iterator begin(){return _t.begin();}//同理 复用iterator end(){return _t.end();}//同理 复用pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}//同理 复用iterator find(const K& key){return _t.Find(key);}//无法复用，因为这是map自己独有的东西，写在map类中//1：若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回一个pair对象，该对象包含插入后元素的迭代器和true。//2：若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回一个pair对象，该对象包含map当中已经存在的键值为key元素的迭代器和false。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;};//------------------------------------------------------------------//测试用例//测试map的迭代器能修改K值 但不能修改V值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()){//it->first += 100;it->second += 100;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}//测试map的[]void test_map2(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
};

④：test.cpp(main函数所在的.cpp)

int main()
{//bit::test_set1();//cout << endl;//bit::test_map1();//cout << endl;//bit::test_map2();//cout << endl;return 0;
}

六：实现所有迭代器

Q：迭代器是什么？普通迭代器和const迭代器的区别是什么？

A：迭代器是一种遍历方式，C++中的任何的容器都能以它这种统一的方式进行遍历

A:在聊普通迭代器和const迭代器的区别之前，我们先汇总一下迭代器的全部操作有哪些，如下：

迭代器的核心操作包括：

①：it++ / ++it（向后移动）

②：it-- / --it（向前移动）

③：*it（解引用，获取元素）

④：it->（成员访问，用于结构体/类对象）

下面分别说明它们的用途，以及普通迭代器和 const 迭代器的区别。

1：迭代器的四种操作的典型使用场景

(1) it++ / ++it（向后移动）

• 用途：遍历容器（如 vector、list、map）

• 示例：

  std::vector<int> vec = {1, 2, 3};for (auto it = vec.begin(); 
  it != vec.end(); ++it) 
  {std::cout << *it << " "; // 输出 1 2 3
  }

(2) it-- / --it（向前移动）

• 用途：反向遍历（如 vector、list、deque）。

• 示例

  std::list<int> lst = {1, 2, 3};auto it = lst.end();
  while (it != lst.begin()) 
  {--it; // 必须先减，否则访问 end() 是未定义行为std::cout << *it << " "; // 输出 3 2 1
  }

(3) *it（解引用，获取元素）

• 用途：访问迭代器指向的元素。

• 示例：

  std::vector<int> vec = {10, 20, 30};
  auto it = vec.begin();
  int x = *it; // x = 10
  *it = 100;   // 修改 vec[0] = 100//it既能读又能写

 (4) it->（成员访问）

• 用途：访问结构体或类的成员（如 map 的 pair）。

• 示例：

  std::map<int, std::string> m = {{1, "Alice"}, {2, "Bob"}};
  auto it = m.begin();
  std::cout << it->first << ": " << it->second << std::endl; // 输出 1: Alice

2. 普通迭代器 和 const 迭代器的区别  

关键区别

1：*it 和 it-> 的返回值是否带 const：

• 普通迭代器：可修改元素。

• const 迭代器：不可修改元素（即使容器本身不是 const）。

2：移动操作（++/--）不受影响：

• 无论是普通迭代器还是 const 迭代器，都可以移动。

3：vector容器的迭代器行为对比

总结：iterator和const_iterato的异同点：

共同点在于 ：都可以遍历，如++/--

不同点在于：iterator支持通过*it和it->来修改成员；而const_iterator不支持

对*和->的解释：

“* 是解引用，用于 访问迭代器指向的元素（可能读取或修改，取决于迭代器类型）”。

“-> 是用于访问元素的成员（如map中的pair 的 first/second），而 * 是访问元素本身。两者用途不同，但都能修改值（如果迭代器允许）”。

3：C++对set和map的迭代器的特殊设计

Q：为什么说C++对set和map的迭代器进行了特殊设计

A：原本应该是：

set的iterator迭代器，可以修改成员K 

set的const_iterator迭代器，无法修改成员K 

map的iterator迭代器，可以修改成员K V

map的iterator迭代器，无法修改成员K V

而对其特殊处理后的迭代器：

set无论是什么迭代器，都无法修改成员K 

map的iterator允许修改 V，但禁止修改 K；const_iterator下的KV都不允许修改

其实本质就是遵循了K模型和KV模型的二叉搜索树的规则罢了~

特殊处理总结如图：

所以C++库中的set类中对于自己的iterator和const_iterator，本质都是调用了红黑树的const_iterator！

set类中的成员变量传参如下：

//set类的成员变量private://所以map的成员变量->一个红黑树类的对象RBTree<K, const K, SetKeyOfT> _t;

 set类中的迭代器如下：(两个迭代器都是红黑树的const_iterator)

set类中：typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;

解释：这就达到了，set无论如何都无法改变K

而map呢，则是如下：

map的成员变量传参如下：

private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;

  set类中的迭代器如下：(iterator即红黑树的iterator；const_iterator则红黑树的const_iterator)

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
//K不可改 V可以改
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
//KV都不能改

 解释： 这就达到了，map的iterator允许修改 V，但禁止修改 K；const_iterator下的KV都不允许修改

此外红黑树类中也要进行迭代器的typedef：

//红黑树类中：
typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;

此外，我们还需在红黑树类和set类和map类中补齐一系列的begin end cbegin cend函数，如下：

红黑树类中补齐begin end cbegin cend函数：

/正向迭代器beginiterator begin(){Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}//正向迭代器enditerator end(){return iterator(nullptr);}//正向const迭代器const_iterator cbegin() const{Node* subleft = _root;while (subleft && subleft->_left){subleft = subleft->_left;}return const_iterator(subleft);}const_iterator cend() const{return const_iterator(nullptr);}

set类中补齐begin end cbegin cend函数：

        //同理 复用iterator begin(){return _t.begin();}//同理 复用iterator end(){return _t.end();}//同理 复用const_iterator cbegin() const{return _t.cbegin();}//同理 复用const_iterator cend() const{return _t.cend();}

map类中补齐begin end cbegin cend函数：

        //同理 复用iterator begin(){return _t.begin();}//同理 复用iterator end(){return _t.end();}//同理 复用const_iterator cbegin() const{return _t.cbegin();}//同理 复用const_iterator cend() const{return _t.cend();}

Q:set由于 普通迭代器（iterator）和 const_iterator 底层都是红黑树的 const_iterator，是否可以直接复用 begin()/end()，而省略 cbegin()/cend()？

A：不能

①：一定要符合 STL 设计规范（所有容器都提供 cbegin()/cend()）。

②：

这里就不演示const对象用cbegin和cend了，因为我们的insert没有实现const版本，set的构造也没有实现其他的，理解了这个点就OK了 

至此呢，正向迭代器和正向const迭代器我们就完成了！

4：反向迭代器和反向const迭代器

理解正向迭代器和正向const迭代器，反向就很简单了！

红黑树的反向迭代器实际上就是对正向迭代器的一个封装，因此红黑树的反向迭代器就是一个迭代器适配器；在反向迭代器当中只有一个成员变量，那就是反向迭代器封装的正向迭代器。反向迭代器的中成员函数，都是通过调用正向迭代器对应的函数来完成相应功能的。 

正向迭代器是封装一个节点，而反向迭代器是封装一个正向迭代器，实在是妙啊~

反向迭代器代码如下：

//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator
{typedef ReverseIterator<Iterator> Self; //反向迭代器的类型typedef typename Iterator::reference Ref; //结点指针的引用typedef typename Iterator::pointer Ptr; //结点指针Iterator _it; //反向迭代器所封装的正向迭代器//构造函数ReverseIterator(Iterator it):_it(it) //根据所给正向迭代器构造一个反向迭代器{}Ref operator*(){return *_it; //通过调用正向迭代器的operator*返回结点数据的引用}Ptr operator->(){return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针}//前置++Self& operator++(){--_it; //调用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //调用正向迭代器的前置++return *this;}bool operator!=(const Self& s){return _it != s._it; //调用正向迭代器的operator!=}bool operator==(const Self& s){return _it == s._it; //调用正向迭代器的operator==}
};

注意：

反向迭代器只接收了一个模板参数，即正向迭代器的类型，也就是说，反向迭代器不知道结点的引用类型和结点的指针类型，因此我们需要在正向迭代器当中对这两个类型进行typedef，这样反向迭代器才能通过正向迭代器获取结点的引用类型和结点的指针类型。

正向迭代器类还要加上一下代码：

template<class T, class Ptr, class Ref>
struct RBTreeIterator
{//加上这两行typedef Ref reference; //结点指针的引用typedef Ptr pointer; //结点指针
};

和正向迭代器同样的道理，反向迭代器实现后，我们也需要在红黑树的实现当中进行迭代器类型的typedef，并在红黑树当中实现成员函数rbegin和rend

//红黑树类：   typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器reverse_iterator rbegin(){//寻找最右结点Node* right = _root;while (right && right->_right){right = right->_right;}//返回最右结点的反向迭代器return reverse_iterator(iterator(right));}reverse_iterator rend(){//返回由nullptr构造得到的反向迭代器（不严谨）return reverse_iterator(iterator(nullptr));}

解释：

• rbegin函数返回中序序列当中最后一个结点的反向迭代器，即最右结点。
• rend函数返回中序序列当中第一个结点前一个位置的反向迭代器，这里直接用空指针构造一个反向迭代器。

说白了rbegin和begin相反的，前者找最右，后者找最左 ，而rend都是一样的

然后呢就是set和map类中的typedef和rbegin和rend的实现：

set类中：

typedef typename RBTree<K, const K, SetKeyOfT>::const_reverse_iterator reverse_iterator; //反向迭代器

    reverse_iterator rbegin(){return _t.rbegin();}reverse_iterator rend(){return _t.rend();}

map类中：

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;

    //同理 复用reverse_iterator rbegin(){return _t.rbegin();}//同理 复用reverse_iterator rend(){return _t.rend();}

 到这里，反向迭代器也就OK了，下面实现反向const迭代器

红黑树类增加：

typedef ReverseIterator<const_iterator> const_reverse_iterator; //反向const迭代器const_reverse_iterator crbegin() const{//寻找最右结点Node* right = _root;while (right && right->_right){right = right->_right;}//返回最右结点的反向迭代器return const_reverse_iterator(const_iterator(right));}const_reverse_iterator crend() const{//返回由nullptr构造得到的反向迭代器（不严谨）return const_reverse_iterator(const_iterator(nullptr));}

set类增加：

typedef typename RBTree<K, const K, SetKeyOfT>::const_reverse_iterator const_reverse_iterator; //反向const迭代器

        const_reverse_iterator crbegin() const{return _t.crbegin();}const_reverse_iterator crend() const{return _t.crend();}

 map类增加： 

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_reverse_iterator const_reverse_iterator;

        //同理 复用const_reverse_iterator crbegin() const{return _t.crbegin();}//同理 复用const_reverse_iterator crend() const{return _t.crend();}

总结反向迭代器：

反向迭代器和反向const迭代器和正向的是一个道理，set虽然有reverse_iterator和const_reverse_iterator之分，但是二者其实都是红黑树的const_reverse_iterator

七：源码

①：红黑树类

#pragma once//枚举
enum Colour
{RED,BLACK
};//节点类
template<class T>// T = const K 
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};//注释是对模版参数的传递演示
//set：
//在红黑树类中得知<T = const int， Ptr = const int*， Ref = const int&>
//map：
//在红黑树类中得知<T = pair<const int, int> ，Ptr = pair<const int, int>*，Ref = pair<const int, int>&>template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;//节点类的简写typedef RBTreeIterator<T, Ptr, Ref> Self;//内部函数返回值的简写//这两行是反向迭代器所需typedef Ref reference; //结点指针的引用typedef Ptr pointer; //结点指针//成员变量是一个结点指针 因为正向迭代器类是对一个结点指针的封装 再去实现一系列的操作符重载Node* _node;//构造函数 说白了就是用一个节点指针去接受一个节点指针RBTreeIterator(Node* node):_node(node){}//对*重载Ref operator*() //set：返回值为：const int& 意味着set的k无法修改{				//map：返回值为：pair<const int, int>& 意味着map的k无法修改 但v可以return _node->_data;}//对->重载Ptr operator->()//set：返回值为:const int* 意味着不能通过指针修改K值{				//map：返回值为：pair<const int, int>* 意味着不能通过指针修改K值 但V可以return &_node->_data;}//对++重载Self& operator++(){if (_node->_right){// 右子树的中序第一个(最左节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//对--重载Self& operator--(){// 跟++逻辑相反if (_node->_left) //结点的左子树不为空{//寻找该结点左子树当中的最右结点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right; //--后变为该结点}else //结点的左子树为空{//寻找孩子不在父亲左的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent; //--后变为该结点}return *this;}//对!=重载bool operator!=(const Self& s){return _node != s._node;}//对==重载bool operator==(const Self& s){return _node == s._node;}
};//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator
{typedef ReverseIterator<Iterator> Self; //反向迭代器的类型typedef typename Iterator::reference Ref; //结点指针的引用typedef typename Iterator::pointer Ptr; //结点指针Iterator _it; //正向迭代器的对象//构造函数 对一个正向迭代器进行封装ReverseIterator(Iterator it):_it(it) //用一个正向迭代器接受一个正向迭代器			{}		     //和正向迭代器的用一个节点指针去接受一个节点指针类似Ref operator*(){return *_it; //通过调用正向迭代器的operator*}Ptr operator->(){return _it.operator->(); //通过调用正向迭代器的operator->}//前置++Self& operator++(){--_it; //调用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //调用正向迭代器的前置++return *this;}bool operator!=(const Self& s){return _it != s._it; //调用正向迭代器的operator!=}bool operator==(const Self& s){return _it == s._it; //调用正向迭代器的operator==}
};//红黑树类//注释是对模版参数的传递演示//红黑树的模版的变化过程
// ①：set
//set内部传给红黑树的参数-->RBTree<K, const K, SetKeyOfT>
//            ↓影响红黑树的模版参数
//红黑树模版参数：template<class K = K, class T = const K, class KeyOfT = SetKeyOfT>//②：map
//map内部传给红黑树的参数-->RBTree<K, pair<const K, V>, MapKeyOfT>
//            ↓影响红黑树的模版参数
//红黑树模版参数：template<class K = K, class T = pair<const K, V>, class KeyOfT =  MapKeyOfT>
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;//节点类的简写Node  这里体现了讲的红黑树的第二个参数被专门用来传递给节点类的模版参数
public://普通迭代器//以下注释演示了传给迭代器类的模版参数是什么//map：因为红黑树的模版参数T为pair<const int, int>，所以iterator模版参数为：<T = pair<const int, int> ，T* = pair<const int, int>* ，T& = pair<const int, int>&>// //注意：//而set不会用到iterator，因为set的的iterator和const_iterator都是调用的红黑树的const_iteratortypedef RBTreeIterator<T, T*, T&> iterator;//const迭代器 同理//set：因为红黑树的模版参数T为const int，所以const_iterator模版参数为：<T = const int, const T* = const const int, const T& = const const int&>//而两个const会缩减为一个-> <T = const int, const T* =  const int*, const T& =  const int&> // //map：因为红黑树的模版参数T为pair<const int, int>，所以const_iterator模版参数为：<T = pair<const int, int> ，const T* = const pair<const int, int>* ，const T& = const pair<const int, int>&>//虽然看起来的map的iterator一样，但是调用const_iterator的时候，其cbegin和cend 都会让 pair<const int, int> 被const修饰typedef RBTreeIterator<T, const T*, const T&> const_iterator;//同理 不再解释typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器typedef ReverseIterator<const_iterator> const_reverse_iterator; //反向const迭代器//正向迭代器beginiterator begin(){//寻找最左结点Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}//正向迭代器enditerator end(){return iterator(nullptr);}//正向const迭代器const_iterator cbegin() const//这个const会让map调用const_iterator时，其中用的cbegin的返回值会被const修饰 达到KV都不能改{//寻找最左结点Node* subleft = _root;while (subleft && subleft->_left){subleft = subleft->_left;}return const_iterator(subleft);}const_iterator cend() const//这个const会让map调用const_iterator时，其中用的cend的返回值会被const修饰 达到KV都不能改{return const_iterator(nullptr);}//以下是反向的迭代器和const迭代器 同理不再赘述reverse_iterator rbegin(){//寻找最右结点Node* right = _root;while (right && right->_right){right = right->_right;}return reverse_iterator(iterator(right));}reverse_iterator rend(){//返回由nullptr构造得到的反向迭代器（不严谨）return reverse_iterator(iterator(nullptr));}const_reverse_iterator crbegin() const{//寻找最右结点Node* right = _root;while (right && right->_right){right = right->_right;}return const_reverse_iterator(const_iterator(right));}const_reverse_iterator crend() const{//返回由nullptr构造得到的反向迭代器（不严谨）return const_reverse_iterator(const_iterator(nullptr));}//查找函数iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}//插入函数 库中的insert返回的就是一个pair类型 因为其是和[ ]搭配的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(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data); // 红色的Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色if (cur == parent->_left){//       g//    p    u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//       g//    p     u//      cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}else{// 情况二：叔叔不存在或者存在且为黑// 旋转+变色//      g//   u     p//            cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		g//   u     p//      cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){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;}}private:Node* _root = nullptr;
};

②：set类

#pragma once
#include"RBTree.h"
namespace bit
{template<class K>class set{// 仿函数（函数对象）// 功能：提取key值// operator()接收一个K类型的参数，返回这个k就行（即key）struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://对于set而言 只会用到红黑树的const_iterator 和 const_reverse_iteratortypedef typename RBTree<K, const K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, const K, SetKeyOfT>::const_reverse_iterator reverse_iterator;typedef typename RBTree<K, const K, SetKeyOfT>::const_reverse_iterator const_reverse_iterator;//复用iterator begin(){return _t.begin();}//同理iterator end(){return _t.end();}const_iterator cbegin() const{return _t.cbegin();}//同理const_iterator cend() const{return _t.cend();}//同理reverse_iterator rbegin(){return _t.rbegin();}//同理 reverse_iterator rend(){return _t.rend();}//同理 const_reverse_iterator crbegin() const{return _t.crbegin();}const_reverse_iterator crend() const{return _t.crend();}//同理pair<iterator, bool> insert(const K& key){return _t.Insert(key);}//同理iterator find(const K& key){return _t.Find(key);}private://所以map的成员变量->一个红黑树类的对象RBTree<K, const K, SetKeyOfT> _t;};//------------------------------------------------------------------//测试用例//测试迭代器是否达到无法修改K值的效果//测试set用iterator //效果：K无法修改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()){//*it += 100; 接触注释会报错 因为set的iterater和const_iterater都无法修改Kcout << *it << " ";++it;}cout << endl;}//测试set用const_iterator //效果：K无法修改void test_set2(){set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}set<int>::const_iterator it = s.begin();while (it != s.end()){//*it += 100;接触注释会报错 因为set的iterater和const_iterater都无法修改Kcout << *it << " ";++it;}cout << endl;}//测试set用reverse_iterator//效果：倒着遍历，K无法修改void test_set3(){set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}set<int>::reverse_iterator it = s.rbegin();while (it != s.rend()){cout << *it << " ";++it;}cout << endl;}//测试set用const_reverse_iterator//效果：倒着遍历，K无法修改void test_set4(){set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}set<int>::const_reverse_iterator it = s.crbegin();while (it != s.crend()){cout << *it << " ";++it;}cout << endl;}};

③：map类

#pragma once
#include"RBTree.h"
namespace bit
{template<class K, class V>class map{// 仿函数（函数对象）// 功能：从pair<K, V>中提取key值// operator()接收一个pair<K, V>类型的参数，返回其first成员（即key）struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_reverse_iterator const_reverse_iterator;//复用iterator begin(){return _t.begin();}//同理iterator end(){return _t.end();}//同理const_iterator cbegin() const{return _t.cbegin();}//同理const_iterator cend() const{return _t.cend();}//同理reverse_iterator rbegin(){return _t.rbegin();}//同理reverse_iterator rend(){return _t.rend();}//同理const_reverse_iterator crbegin() const{return _t.crbegin();}//同理const_reverse_iterator crend() const{return _t.crend();}//同理pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}//同理iterator find(const K& key){return _t.Find(key);}//无法复用，因为这是map自己独有的东西，写在map类中//[]的意义： //1：若待插入元素的键值key在map当中不存在，则insert函数插入成功，并返回一个pair对象，该对象包含插入后元素的迭代器和true。//2：若待插入元素的键值key在map当中已经存在，则insert函数插入失败，并返回一个pair对象，该对象包含map当中已经存在的键值为key元素的迭代器和false。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;};//------------------------------------------------------------------//测试用例//测试map用iterator//效果：K无法修改，V可以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()){//it->first += 100;//放开注释则报错it->second += 100;//但能修改Vcout << it->first << ":" << it->second << endl;++it;}cout << endl;}//测试map用:const_iterator//效果：K无法修改，V也不可以void test_map2(){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>::const_iterator it = m.cbegin();while (it != m.cend()){//it->first += 100;//放开注释则报错//it->second += 100;//放开注释则报错cout << it->first << ":" << it->second << endl;++it;}cout << endl;}//测试map用:reverse_iterator//效果：倒着遍历，K无法修改，V可以void test_map3(){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>::reverse_iterator it = m.rbegin();while (it != m.rend()){//it->first += 100;//放开注释则报错it->second += 100;//但能修改Vcout << it->first << ":" << it->second << endl;++it;}cout << endl;}//测试map用:const_reverse_iterator//效果：倒着遍历，K无法修改，V也不可以void test_map4(){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>::const_reverse_iterator it = m.crbegin();while (it != m.crend()){//it->first += 100;//放开注释则报错//it->second += 100;//放开注释则报错cout << it->first << ":" << it->second << endl;++it;}cout << endl;}//测试map的[]void test_map5(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
};

④：test.cpp

 

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;#include"MyMap.h"
#include"MySet.h"int main()
{//想测试哪个 放开对应的注释即可//bit::test_set1();//测试set的iterator 体现无法更改set的K//cout << endl;//bit::test_set2();//测试set的const_iterator 体现无法更改set的K //cout << endl;//bit::test_set3();//测试set的reverse_iterator 体现倒着遍历且无法更改set的K//cout << endl;//bit::test_set4();//测试set的const_reverse_iterator 体现倒着遍历且无法更改set的K//cout << endl;//bit::test_map1();//测试map的iterator 体现无法更改map的K，但可以改map的V//cout << endl;//bit::test_map2();//测试map的const_iterator 体现无法更改map的KV//cout << endl;//bit::test_map3();//测试map的reverse_iterator 体现倒着遍历，无法更改map的K，但可以改map的V//cout << endl;//bit::test_map4();//测试map的const_reverse_iterator 体现倒着遍历，无法更改map的KV//cout << endl;//bit::test_map5();//测试map的[ ] //cout << endl;return 0;
}

⑤：测试效果

"代码或有bug，思想或有局限，欢迎issue和PR！"