当前位置：首页 > ds >正文

【C++】封装红黑树模拟实现set和map

ds 2025/7/13 14:37:19

前言

一、实现出复用红黑树的框架，并支持insert

二、实现迭代器iterator

三、实现map支持[ ]

四、实现Find接口

五、完整代码

总结

前言

前面我们学习了红黑树，本文我们主要是封装红黑树用于模拟实现set和map，所以，学习本文前一定要先学习完红黑树哦。

一、实现出复用红黑树的框架，并支持insert

我们之前写的红黑树（来自上一篇文章），需要改造几处才能用于模拟实现set和map的底层框架。

原版红黑树：RBTree.h

#pragma once
#include <iostream>
using namespace std;//用枚举定义红黑颜色
enum Colour
{RED,BLACK
};//定义红黑树节点
template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;//数据RBTreeNode<K, V>* _left;//左孩子指针RBTreeNode<K, V>* _right;//右孩子指针RBTreeNode<K, V>* _parent;//父结点指针Colour _col;//颜色RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr),_parent(nullptr){ }
};//红黑树定义
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;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;//新增节点为红色if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//红黑树的调整while (parent && parent->_col == RED)//父节点存在且为红色{Node* grandfather = parent->_parent;//父父节点if (grandfather->_left == parent)//parent为左孩子{Node* uncle = grandfather->_right;//叔叔节点（父节点的兄弟节点）if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_left)//cur为parent的左孩子{//形状：此时需要右单旋//    g//  p   u//cRotateR(grandfather);//右单旋parent->_col = BLACK;grandfather->_col = RED;}else//cur为parent的右孩子，需要双旋{//形状//     g//  p    u//   cRotateL(parent);//先对p进行左单旋RotateR(grandfather);//再对整体进行右单旋grandfather->_col = RED;cur->_col = BLACK;}break;}}else//parent为右孩子，与上面类似，相当于翻个面{Node* uncle = grandfather->_left;//叔叔节点变为左孩子if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_right)//cur为parent的右孩子{//形状：此时需要左单旋//    g//  u   p//        cRotateL(grandfather);//左单旋parent->_col = BLACK;grandfather->_col = RED;}else//cur为parent的左孩子，需要双旋{//形状//     g//  u    p//      cRotateR(parent);//先对p进行右单旋RotateL(grandfather);//再对整体进行左单旋grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;//强制根节点为黑色return true;}//查找Node* Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_kv.first){cur = cur->_right;}else if (key < cur->_kv.first){cur = cur->_left;}else{return cur;}}return nullptr;}private://右单旋void RotateR(Node* parent){Node* subL = parent->_left;//左孩子Node* subLR = subL->_right;//左孩子的右孩子//旋转过去parent->_left = subLR;subL->_right = parent;Node* ppNode = parent->_parent;//记录父父节点//更新父节点指针if (subLR)subLR->_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 RotateL(Node* parent){Node* subR = parent->_right;//右孩子Node* subRL = subR->_left;//右孩子的左孩子//旋转过去parent->_right = subRL;subR->_left = parent;Node* ppNode = parent->_parent;//父父节点//更新父节点指针if (subRL)subRL->_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;}}
};

改造1：模板参数的修改

问题：

我们在上一篇文章中写的红黑树，其底层数据类型我们是直接写死为pair类型的。
set和map的模拟实现需要使用红黑树作为底层结构，所以需要复用红黑树。
而set底层数据并不是pair类型。所以导致set和map不能同时复用上面的红黑树用于底层结构。

解决方法：

参考STL库中的解决方法，map和set向红黑树传两个参数。
具体方法：原版我们需要向红黑树传递K,V两个模板参数，现在我们需要向红黑树传递K,T两个参数，K参数传递数据底层类型，比如set储存数据是什么类型就传什么，map是其底层数据类型pair<K,V>中K的数据类型是什么就传什么。对于T，set依旧传储存的数据类型即可，map传具体的pair<K,V>类型。简单点说，set传给红黑树的两个模板参数都为K，map传K和pair<K,V>。
疑惑解答：你可能会觉得红黑树用两个模板参数控制数据类型有点多余，直接去掉K而只使用T不更方便吗。其实这是因为K还有一个重要的作用，就是用于find函数的参数类型，参考原版红黑树，Find是根据K来查找数据的。

初步改造的红黑树：RBTree.h

#pragma once
#include <iostream>
using namespace std;//用枚举定义红黑颜色
enum Colour
{RED,BLACK
};//定义红黑树节点
template<class T>
struct RBTreeNode
{T _data;//使用T来控制节点类型RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr),_parent(nullptr){ }
};//红黑树定义
template<class K,class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:bool Insert(const T& data){//...}
private://旋转...Node* _root = nullptr;
};

注意：除了RBTree模板参数变为了K,T，RBTreeNode模版参数变为了T，因为T就能控制具体数据类型。
还有insert的参数，类型改为T，名字也修改一下。

set的初步框架：myset.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K>class set{public:bool insert(const K& key){//...}private:RBTree<K, K> _rbtree;};
}

map的初步框架：mymap.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K, class V>class map{public:bool insert(const pair<K, V>& kv){//...}private:RBTree<K, pair<K, V>> _rbtree;};
}

注意，set和map的类使用命名空间封装起来，避免与STL库中的冲突。

改造2：使用仿函数替换insert中的数据比较

问题：

虽然上面我们解决了set和map复用同一个红黑树的问题，但是原版红黑树中，我们数据比较依旧是使用pair类型。如下：
很明显，map虽然能适配，但是set不行，这该怎么解决呢？

解决方法：仿函数

仿函数我就不过多介绍了，之前文章详细介绍过，简单点说，仿函数就是一个类，这个类重载了()这个运算符，功能就是我们可以用：对象名+()的方式调用这个函数。
而我们解决红黑树值insert中比较大小的方法就是，在set和map类中再分别定义一个仿函数的类，这个仿函数用于返回红黑树中需要比较的数据，对于set来说，该仿函数直接返回存储的数据即可，对于map来说，需要返回kv->first对应的数据，因为pair是根据其第一个参数比较大小的。红黑树加一个模板参数专门接收这个类，通过set和map传过来的不同仿函数，使用该类实例出一个对象统一格式比较数据大小。

具体操作：

myset.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key)//仿函数，返回需要用于比较的数据{return key;//对于set来说就是key}};public:bool insert(const K& key){return _rbtree.Insert(key);//直接复用红黑树的insert}private:RBTree<K, K, SetKeyOfT> _rbtree;};
}

mymap.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv)//仿函数，返回需要比较的数据{return kv.first;//对于map来说，用于比较的就是first}};public:bool insert(const pair<K, V>& kv){return _rbtree.Insert(kv);//直接复用红黑树的insert}private:RBTree<K, pair<K, V>, MapKeyOfT> _rbtree;};
}

RBTree.h（修改内容：模板参数、数据比较。其他不变）

#pragma once
#include <iostream>
using namespace std;//用枚举定义红黑颜色
enum Colour
{RED,BLACK
};//定义红黑树节点
template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr),_parent(nullptr){ }
};//红黑树定义
template<class K,class T, class KeyOfT>//第三个参数接收仿函数的类
class RBTree
{typedef RBTreeNode<T> Node;
public:bool Insert(const T& data){//先按照搜索二叉树的方式查找插入点if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点为黑色return true;}KeyOfT kot;//示例一个仿函数类对象Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_data))//用kot返回map或者set类真正需要比较的数据，其他地方同理{parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);cur->_col = RED;//新增节点为红色if (kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//变色...(省略)return true;}private://旋转...（省略）Node* _root = nullptr;
};

总之，这两种改造都是为了使map能和set共用一个红黑树模板，当然实例出的肯定是两颗红黑树，注意是节省了我们的代码量，减少冗余。
关于set和map的insert接口实现，是直接复用红黑树的insert，本质都是往各自的树中插入，这就是改造后的好处。

二、实现迭代器iterator

1.基本框架

基本框架，其实和之前模拟实现链表的迭代器差不多。单独一个类定义迭代器，并且使用struct而不是class定义，因为这样方便红黑树的类直接调用，避免友元等一系列问题。

RBTree.h

//迭代器实现
template<class T>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T> Self;//构造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Node* _node;Node* _root;T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}//前置++Self& operator++(){}//前置--Self& operator--(){}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//红黑树定义
template<class K,class T, class KeyOfT>//第三个参数接收仿函数的类
class RBTree
{typedef RBTreeNode<T> Node;
public://迭代器框架typedef RBTreeIterator<T> Iterator;Iterator Begin(){}Iterator End(){}//其余暂时一样，省略...
private://旋转（省略）Node* _root = nullptr;
}

myset.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key)//仿函数，返回需要用于比较的数据{return key;//对于set来说就是key}};public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, K, SetKeyOfT>::Iterator iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}bool insert(const K& key){return _rbtree.Insert(key);}private:RBTree<K, K, SetKeyOfT> _rbtree;};
}

mymap.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv)//仿函数，返回需要比较的数据{return kv.first;//对于map来说，用于比较的就是first}};public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}bool insert(const pair<K, V>& kv){return _rbtree.Insert(kv);}private:RBTree<K, pair<K, V>, MapKeyOfT> _rbtree;};
}

对于RBTree.h，已经实现的接口就不必多说了，参考链表。其中的operator->提一嘴，它返回的是data的指针，对于map来说就是pair<>*，也就是说我们想要拿到pair中的first或者second理论上还需要对pair的指针使用->，但我们实际上对于map的迭代器，直接 it->first，所以实际省略了一个箭头和中间的_data，是编译器帮我们优化了。
myset.h 和 mymap.h，它们两个关于迭代器的框架差不多。对于迭代器的实现，比如begin和end其实都是对红黑树中迭代器的套壳，重点是typename。
然后补充一下，map和set的迭代器都是双向迭代器，双向迭代器支持++、--但不支持+、-。另外迭代器实现中实现了 == 和 !=，这是方便后续迭代器比较（比如迭代器遍历）。++和--是迭代器实现中的难点，具体在下面讲解实现。
关于_node和_root，_node就是当前节点，也就是当前封装的迭代器。_root是当前红黑树的根节点，这个主要用于待会的operator--实现。

typename：

一开始，typename和class都可以作为定义模板参数的关键字。但我们多数使用的还是class。
所以现在我们就得了解typename的另一个作用：当我们在一个类中想使用另一个类中定义的类型时，此时我们不能直接突破类域（::）使用，因为此时并没有实例化红黑树的类，编译器默认你访问的是一个静态变量，在类型名前面加上typename就是向编译器指示其为类型名而不是静态变量。

2.实现红黑树中的Begin和End

这两个函数实现起来其实很简单：

//红黑树定义
template<class K,class T, class KeyOfT>//第三个参数接收仿函数的类
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T> Iterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}//...(省略)
}

Begin其实就是返回红黑树遍历的第一个节点，红黑树也是二叉搜索树变过来的，是按照中序输出遍历，所以我们找到最左的节点即可，然后将该节点封装成迭代器返回即可。
End返回红黑树最后一个节点的下一个节点，理论上我们应该实现一个哨兵位，End返回的节点应是哨兵位节点，但是实现哨兵位后续维护也是有代价的，所以现在我们可以简单一点，用空结点代替。
空节点为什么能代替呢，比如现在红黑树是一棵空树，Begin返回的也是一个空迭代器，在迭代器遍历中，我们需要比较 it != myset.end()，此时 it 和 end返回的都是空迭代器，所以比较不成立，遍历也就终止了。对于迭代器正常++遍历到结尾时，怎么和end比较，这个我们在下面讲。

3.实现迭代器的前置++

大致逻辑：

迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下一个结点。
迭代器++时，如果it指向的结点的右子树不为空，代表当前结点已经访问完了，要访问下一个结点是右子树的中序第一个，一棵树中序第一个是最左结点，所以直接找右子树的最左结点即可。
迭代器++时，如果it指向的结点的右子树空，代表当前结点已经访问完了且当前结点所在的子树也访问完了，要访问的下一个结点在当前结点的祖先里面，所以要沿着当前结点到根的祖先路径向上找。

解释：

以上面这棵红黑树举例，此时中序遍历的第一个节点就是黑色节点10，也就是begin返回的节点。此时当 ++it 时，it就应该访问到红色节点15。当然此时不能找到规律
如上，假如it走到了黑色结点18，一般情况下，18可能是整棵树的根节点，也可能是局部子树的根节点。无论如何，上面说到了，我们不看全局，只看局部。此时 it 既然走到了18，说明什么？说明18的左子树访问完毕，对于中序遍历来说，按照左->根->右，访问完当前节点18后，应该访问右子树，很明显右子树有很多节点，对于中序来说，我们需要访问右子树中最左节点，因此 ++it 下一个节点应该是黑色结点25。
小结：通过以上两个例子，以局部的眼光去看，此时我们得到++的第一种情况：假如当前节点的右子树存在，那么++it，it访问的下一个节点应是右子树中最左节点。
既然存在第一个情况，那么就存在右子树为空的第二种情况了。
观察上面三种情况，它们都是右子树为空的情况。按照中序遍历，对于最左边第一种情况中的红色节点15来说，它的下一跳应该是黑色结点18。对于中间第二种情况的黑色结点25来说，它的下一跳应该是红色节点30。对于右边第三种情况的红色节点50来说，此时它是最后一个有效节点，它的下一跳应该为nullptr。
我们依旧以一个局部的眼光来看，既然右子树为空，说明什么？说明以当前节点的父节点为根节点的整棵子树（也可能是整棵树），现在都遍历完成，那么对于一棵子树来说，我们需要往上找父节点的父节点，最终确认为下一跳的这个节点应满足一个条件，即该节点的左子树是刚刚遍历完的子树。这是一个需要一直往上查找的过程，这句话可以换一个方式说，我们当前节点是父节点的右孩子节点，那么下一跳的节点应该是其父节点的左孩子。参考上面第一种情况中，18的左孩子是10，刚刚遍历完成的以10为根的子树已经遍历完成，所以遍历完成的子树应是下一跳节点18的左子树，因为要按照中序遍历。同理以上第二种情况也是一样，需要往上查找，只不过刚好当前节点是其父节点的左孩子节点，所以下一跳为30。那么对于情况三就有点特殊了，它会不断向上查找，但是找不到当前节点是其父节点的左孩子的这个节点，这时不用担心，因为最终会走到根节点的父节点，也就是走到空，走到空就结束，将判空作为向上查找的判定条件之一就行。
小结：++的另一种情况：当前节点的右孩子节点为空，此时需要循环向上查找，查到一个节点是其父节点的左孩子节点即可，此时下一跳即是当前节点的父节点。

说了这么多可能一下子看不明白，我们直接看实现++代码，利于理解：

//前置++
Self& operator++()
{//右子树不为空，相当于当前节点是局部子树根节点if (_node->_right){//找右子树中最左节点Node* minleft = _node->_right;while (minleft->_left){minleft = minleft->_left;}_node = minleft;}else//右子树为空，说明当前节点以及父节点为根的子树遍历完毕{//找"当前"节点是父亲左孩子的祖先节点，找不到说明整棵树遍历完成Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//父存在，但当前节点是父的右孩子{//需要继续往上找，因为右孩子说明局部树遍历完毕cur = parent;parent = parent->_parent;}_node = parent;//无论父节点是不是空，一样}return *this;
}

首先，_node是当前迭代器封装的节点，我们的目的是++，将_node指向下一跳的节点。
if...else中的判断就是判断当前节点的右子树是否为空。1.不为空，按照前面所说，找到右子树中最左节点即可，然后将 _node 指向该节点，代码很好理解。2.为空，按照前面所说，需要往上寻找当前节点为其父节点的左孩子节点，因此需要 cur 和 parent两个节点往上查找，查找的条件就是父节点不为空并且当前节点是其父节点的右孩子，如果条件判断为真，说明需要继续向上更新查找。如果条件为假，这时有两种情况，一是找到了，那么将_node指向其父节点即可，二是没找到，父节点为空导致循环结束，说明整棵树已经遍历完成，需要将_node指向nullptr，因为此时父节点就是nullptr，所以_node更新方式不用变。
以上就是迭代器前置++的实现，仔细看自行理解应该不难看懂嘿嘿。

补充一点：

我上面提到STL库中迭代器end()返回的是哨兵位而不是nullptr，这哨兵位头结点和根互为父亲，左指向最左结点，右指向最右结点。相比我们用nullptr作为end()，差别不大，他能实现的，我们也能实现。
哨兵位的存在可以很快捷的找到最左节点和最右节点，以至于有些功能实现起来相对也容易一点（比如begin和end），唯一麻烦的就是需要维护，当插入或者删除影响的节点是最左或者最右或者是根节点时，需要更新哨兵位的指向，所以使用哨兵位也是有代价的，我们这里简化一下，直接使用nullptr空节点。

完成以上内容后，我们可以使用迭代器遍历来验证代码是否正确：

#include <iostream>
#include "mymap.h"
#include "myset.h"
using namespace std;void test1()
{txp::set<int> s1;s1.insert(3);s1.insert(2);s1.insert(1);s1.insert(4);s1.insert(5);txp::map<int, int> m1;m1.insert({ 4,1 });m1.insert({ 2,1 });m1.insert({ 1,1 });m1.insert({ 5,1 });m1.insert({ 3,1 });txp::set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;txp::map<int, int>::iterator it2 = m1.begin();while (it2 != m1.end()){cout << it2->first << ":" << it2->second << " ";++it2;}cout << endl;for (auto& e : s1){cout << e << " ";}cout << endl;for (auto& e : m1){cout << e.first << ":" << e.second << " ";}cout << endl;
}int main()
{test1();return 0;
}

运行结果：

结果显示，无论是迭代器还是范围for，结果显示正确。

4.实现迭代器的前置--

迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右子树->根结点-> 左子树，具体参考下面代码实现。

//前置--
Self& operator--()
{//比如整棵树已经走完了（--end()）if (_node == nullptr){Node* rightmost = _root;while (rightmost && rightmost->_right){rightmost = rightmost->_right;}_node = rightmost;}else if (_node->_left)//左不为空{Node* maxright = _node->_left;while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else//左为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

这段代码与前置++的实现唯一区别就是，多了一个_node=nullptr的情况，也就是此时节点是“哨兵位”，也是end()返回的节点，此时相当于是 --end()，很明显，--end()就是跳到最后一个有效节点，最后一个有效节点就是最右节点，因此找到rightMost即可。
因为查找rightMost需要从根节点往右查找，所以需要根节点_root，前面我们定义框架中带上了_root，其作用就在这里。
关于剩下两种情况，左子树为空和左子树不为空，这两种情况就和前置++的实现思路一模一样了。1.当左子树不为空时，找出左子树中最右节点即可。2.当左子树为空时，说明以当前节点的父节点为根的子树已经全部访问完毕，需要往上找到一个节点是其父节点右孩子的节点。

我们可以遍历验证一下前置--的正确性：

#include <iostream>
#include "mymap.h"
#include "myset.h"
using namespace std;void test1()
{txp::set<int> s1;s1.insert(3);s1.insert(2);s1.insert(1);s1.insert(4);s1.insert(5);txp::map<int, int> m1;m1.insert({ 4,1 });m1.insert({ 2,1 });m1.insert({ 1,1 });m1.insert({ 5,1 });m1.insert({ 3,1 });txp::set<int>::iterator it1 = s1.end();while (it1 != s1.begin()){--it1;cout << *it1 << " ";}cout << endl;txp::map<int, int>::iterator it2 = m1.end();while (it2 != m1.begin()){--it2;cout << it2->first << ":" << it2->second << " ";}cout << endl;
}int main()
{test1();return 0;
}

运行结果：

补充：

以上我们实现了迭代器的前置++和前置--，你可能会会困惑为什么不实现后置，其实也可以实现，后置++和后置--（operator++(int) ）的函数括号中记得加上int。然后实现方法就是在最前面保存一份原_node节点，在最后面返回原_node即可。

5.const迭代器实现

在实现const迭代器之前呢，我们先修复一下上面遗留的一点容器的特性问题，也就是：set的数据是不支持修改的，所以其迭代器返回值也是不能修改的。对于map，map的pair<K,V>中的K不能修改，V可以修改，所以其迭代器返回值中的K也不能修改。
修复这一点很简单，我们把set的第二个模板参数改成const K即可，我们把map的第二个模板参数pair的第一个参数改成const K即可。只修改第二个模板参数，因为只有第二个模板参数是用来增删的，第一个模板参数是Find查询用的。

修改代码：

set:

#pragma once
#include "RBTree.h"namespace txp
{//...(省略)public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;//...(省略)		private:RBTree<K, const K, SetKeyOfT> _rbtree;};
}

map:

#pragma once
#include "RBTree.h"namespace txp
{//...(省略)public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;//...(省略)		private:RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;};
}

接下来我们实现const迭代器：

const迭代器实现也不复杂，为了避免代码冗余，所以普通迭代器和const迭代器是共用一个模板的，这样我们迭代器模板就需要增加两个参数Ref和Ptr，template<class T, class Ref, class Ptr>。
普通迭代器和const迭代器的区别就在于Ref和Ptr的参数不同，普通迭代器这两个传T&、T*，const迭代器这两个传const T&、const T*。
对于set来说，普通迭代器和const迭代器是一样的，因为set的特性所以普通迭代器返回值本来也不能随意修改。主要是对于map来说，普通迭代器是只能修改pair中的V，const迭代器是K,V这两个都不能修改。

代码实现和修改：

RBTree.h

#pragma once
#include <iostream>
using namespace std;//...(省略)//迭代器实现
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;//构造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Node* _node;Node* _root;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){//...(省略)}//前置--Self& operator--(){//...(省略)}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//红黑树定义
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*> ConstIterator;Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}//...(省略)}

myset.h

#pragma once
#include "RBTree.h"namespace txp
{//...(省略)public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}bool insert(const K& key){return _rbtree.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _rbtree;};
}

mymap.h

#pragma once
#include "RBTree.h"namespace txp
{//...(省略)public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}bool insert(const pair<K, V>& kv){return _rbtree.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;};
}

const迭代器使用验证：

我们先看set：

#include <iostream>
#include "mymap.h"
#include "myset.h"
using namespace std;void test1()
{txp::set<int> s1;s1.insert(3);s1.insert(2);s1.insert(1);s1.insert(4);s1.insert(5);txp::set<int>::const_iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;txp::set<int>::const_iterator it2 = s1.end();while (it2 != s1.begin()){--it2;cout << *it2 << " ";}cout << endl;}int main()
{test1();return 0;
}

运行结果：

很明显，set的const迭代器使用起来并未问题，下面我会解释。

接着，我们继续验证map:

#include <iostream>
#include "mymap.h"
#include "myset.h"
using namespace std;void test1()
{txp::map<int, int> m1;m1.insert({ 4,1 });m1.insert({ 2,1 });m1.insert({ 1,1 });m1.insert({ 5,1 });m1.insert({ 3,1 });txp::map<int, int>::const_iterator it1 = m1.begin();while (it1 != m1.end()){cout << it1->first << ":" << it1->second << " ";++it1;}cout << endl;txp::map<int, int>::const_iterator it2 = m1.end();while (it2 != m1.begin()){--it2;cout << it2->first << ":" << it2->second << " ";}cout << endl;
}int main()
{test1();return 0;
}

运行结果：

报错原因：

原m1是普通map类型，map<int, int>::const_iterator it1 = m1.begin(); 其中it1是const迭代器，m1.begin()返回的是普通迭代器。
很明显这中间缺少一样东西，也就是拷贝构造。自动生成的拷贝构造不够用的原因下面会解释。

解决方法：在迭代器模板中添加拷贝构造

#pragma once
#include <iostream>
using namespace std;//...(省略)//迭代器实现
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;typedef RBTreeIterator<T, T&, T*> Iterator;Node* _node;Node* _root;//构造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}//拷贝构造RBTreeIterator(const Iterator& s):_node(s._node), _root(s._root){}//...(省略)}

这里有一个细节，很明显，我添加了一个 typedef RBTreeIterator<T, T&, T*> Iterator;
这是因为，我们需要的拷贝构造是将一个普通迭代器转化为const迭代器，而在上面问题中，拷贝构造的调用方是const迭代器，所以如果我们不定义一个普通迭代器的话，将无法实现普通迭代器向const迭代器的转化。这也是为啥拷贝我们构造不写，自动生成的无法满足要求，显示报错的原因。

修改后我们继续运行：

这一次没有问题。
我们再谈一下，为什么set没有出现这个问题，这是因为set普通迭代器和const迭代器没有区别，因为我们set第二个模板参数传的是 const K，所以在迭代器中模板参数T已经是 const类型了，所以本质上，set的普通迭代器和const迭代器是一样的，所以它自动生成的拷贝构造够用。
那么为什么map会出现问题，这是因为map的第二个模板参数是pair<const K, V>，而对于const迭代器来说，其中 Ref 和 Ptr 是 const pair<const K,V>& 和 const pair<const K,V>*，对于pair来说，在其前面加上const那么K,V就都不能修改，这一点和set就不一样。所以map就需要自己定义一个拷贝构造解决这个问题。

6.迭代器实现的完整代码

//迭代器实现
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;typedef RBTreeIterator<T, T&, T*> Iterator;Node* _node;Node* _root;//构造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}////拷贝构造RBTreeIterator(const Iterator& s):_node(s._node), _root(s._root){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){//右子树不为空，相当于当前节点是局部子树根节点if (_node->_right){//找右子树中最左节点Node* minleft = _node->_right;while (minleft->_left){minleft = minleft->_left;}_node = minleft;}else//右子树为空，说明当前节点以及父节点为根的子树遍历完毕{//找"当前"节点是父亲左孩子的祖先节点，找不到说明整棵树遍历完成Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//父存在，但当前节点是父的右孩子{//需要继续往上找，因为右孩子说明局部树遍历完毕cur = parent;parent = parent->_parent;}_node = parent;//无论父节点是不是空，一样}return *this;}//前置--Self& operator--(){//比如整棵树已经走完了（--end()）if (_node == nullptr){Node* rightmost = _root;while (rightmost && rightmost->_right){rightmost = rightmost->_right;}_node = rightmost;}else if (_node->_left)//左不为空{Node* maxright = _node->_left;while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else//左为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

三、实现map支持[ ]

[ ] 的功能探讨：

首先，我们平时使用map的 [ ] 主要是通过传 Key 来得到 value，进而对 value 进行一些修改操作。
那么，[ ] 的功能就应该包括查找和返回 value，但我们可能忽略了 [ ] 的另一个功能，它还有插入值的功能，也就是我们传 Key，但是当 Key 不存在时，[ ] 会向 map 插入Key，其 Value 对应的是Key这个类型的默认值。
这个功能是我们常常忽略的，但是平时我们使用的也不少，比如 m1["苹果"]++，可能 m1 中就没有“苹果”这个值，但是不会报错，m1中会自动添加“苹果”并默认其值Value是0，++后变为1。

[ ] 的功能实现：

其实 [ ] 的功能实现起来并不难，因为它是完全依靠 insert 进行实现的，这一点完全能理解，因为其功能实现和 insert 很相似。
当然，我们需要对 insert 进行改造，首先是 insert 的返回值需要修改为：pair<Iterator, bool> Insert(const T& data)。也就是其返回值变为一个 pair 类型，这个pair和map底层pair是两个不同的pair。返回值的这个pair，它的first是一个迭代器，也就是插入节点的迭代器，它的second是一个bool值，bool是表示当前值是否插入成功，插入失败返回false。
pair<Iterator, bool> Insert(const T& data)的设计目的就是为map的 [ ] 服务，在 [ ] 的实现中，我们形参是一个Key，我们就将 Key 和其Value的默认值组成一个pair结构插入红黑树，然后依据其返回值中的迭代器iterator，该迭代器就是Key对于的节点，这个节点可能是map中已经存在的，也可能是我们插入的，不管怎样，[ ] 需要返回 value，那么我们就返回 iterator 中的 second 即可。

Insert的改造：

pair<Iterator, bool> Insert(const T& data)
{//先按照搜索二叉树的方式查找插入点if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点为黑色return make_pair(Iterator(_root, _root), true);//插入成功，根节点返回值}KeyOfT kot;//示例一个仿函数类对象Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_data))//用kot返回map或者set类真正需要比较的数据，其他地方同理{parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return make_pair(Iterator(cur, _root), false);//插入失败，直接返回当前节点}}cur = new Node(data);Node* newnode = cur;//先保存一份插入节点，避免后续cur更新导致找不到cur->_col = RED;//新增节点为红色if (kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//变色while (parent && parent->_col == RED)//父节点存在且为红色{Node* grandfather = parent->_parent;//父父节点if (grandfather->_left == parent)//parent为左孩子{Node* uncle = grandfather->_right;//叔叔节点（父节点的兄弟节点）if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_left)//cur为parent的左孩子{//形状：此时需要右单旋//    g//  p   u//cRotateR(grandfather);//右单旋parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else//cur为parent的右孩子，需要双旋{//形状//     g//  p    u//   cRotateL(parent);//先对p进行左单旋RotateR(grandfather);//再对整体进行右单旋parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else//parent为右孩子，与上面类似，相当于翻个面{Node* uncle = grandfather->_left;//叔叔节点变为左孩子if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_right)//cur为parent的右孩子{//形状：此时需要左单旋//    g//  u   p//        cRotateL(grandfather);//左单旋parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else//cur为parent的左孩子，需要双旋{//形状//     g//  u    p//      cRotateR(parent);//先对p进行右单旋RotateL(grandfather);//再对整体进行左单旋parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;//强制根节点为黑色return make_pair(Iterator(newnode, _root), true);
}

Insert具体改造的地方：

首先是函数返回值改为 pair<Iterator, bool>。
然后是几处return，可以使用 make_pair进行构造pair，也可以直接使用{ }进行构造。
还有一处细节，在cur找到插入位置，准备插入新节点时，我们使用 Node* newnode = cur 提前储存一份新节点，目的是因为cur可能在后续变色向上更新颜色时被改变了指向，所以需要提前保存。

因为Insert的返回值被改变，所以set中的insert也需要改变：

#pragma once
#include "RBTree.h"namespace txp
{template<class K>class set{//...(省略)public://...(省略)pair<iterator, bool> insert(const K& key){return _rbtree.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _rbtree;};
}

然后就是重头戏，map中的 [ ] 实现：

#pragma once
#include "RBTree.h"namespace txp
{template<class K, class V>class map{//...(省略)public://...(省略)pair<iterator, bool> insert(const pair<K, V>& kv){return _rbtree.Insert(kv);}V& operator[](const K& key) {pair<iterator, bool> ret = _rbtree.Insert({ key, V() });return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;};
}

[ ] 的实现中，这两处再提一下：
首先是 pair<iterator, bool> ret = _rbtree.Insert({ key, V() }) 中的 V()，这是模板参数中表示默认构造的标志，也就是说，会根据V的类型自动调用默认构造，比如对于int来说，默认构造就是0。
第二处就是 return ret.first->second，ret.first是访问外层pair中的iterator，->second是访问内层pair中的value，也就是节点的value。

接下来，我们可以简单验证一下 [ ] 的正确性：

#include <iostream>
#include "mymap.h"
#include "myset.h"
using namespace std;void test1()
{txp::map<string, string> m1;m1.insert({ "sort", "排序" });m1.insert({ "left", "左边" });m1.insert({ "right", "右边" });m1["left"] = "左边，剩余";m1["insert"] = "插入";m1["string"];txp::map<string, string>::iterator it = m1.begin();while (it != m1.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}void test2()
{string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香港" };txp::map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& e : countMap){cout << e.first << ":" << e.second << endl;}
}int main()
{test1();test2();return 0;
}

运行结果：

结果显示，[ ] 的实现没有出现问题。

四、实现Find接口

RBTree

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

set

iterator find(const K& key)
{return _rbtree.Find(key);
}

map

iterator find(const K& key)
{return _rbtree.Find(key);
}

Find 返回值为迭代器，其余实现很简单，就不多说了。

五、完整代码

RBTree.h

#pragma once
#include <iostream>
using namespace std;//用枚举定义红黑颜色
enum Colour
{RED,BLACK
};//定义红黑树节点
template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr),_parent(nullptr){ }
};//迭代器实现
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;typedef RBTreeIterator<T, T&, T*> Iterator;Node* _node;Node* _root;//构造RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}////拷贝构造RBTreeIterator(const Iterator& s):_node(s._node), _root(s._root){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){//右子树不为空，相当于当前节点是局部子树根节点if (_node->_right){//找右子树中最左节点Node* minleft = _node->_right;while (minleft->_left){minleft = minleft->_left;}_node = minleft;}else//右子树为空，说明当前节点以及父节点为根的子树遍历完毕{//找"当前"节点是父亲左孩子的祖先节点，找不到说明整棵树遍历完成Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//父存在，但当前节点是父的右孩子{//需要继续往上找，因为右孩子说明局部树遍历完毕cur = parent;parent = parent->_parent;}_node = parent;//无论父节点是不是空，一样}return *this;}//前置--Self& operator--(){//比如整棵树已经走完了（--end()）if (_node == nullptr){Node* rightmost = _root;while (rightmost && rightmost->_right){rightmost = rightmost->_right;}_node = rightmost;}else if (_node->_left)//左不为空{Node* maxright = _node->_left;while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else//左为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//红黑树定义
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*> ConstIterator;//析构~RBTree(){Destroy(_root);_root = nullptr;}Iterator Begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}pair<Iterator, bool> Insert(const T& data){//先按照搜索二叉树的方式查找插入点if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根节点为黑色return make_pair(Iterator(_root, _root), true);//插入成功，根节点返回值}KeyOfT kot;//示例一个仿函数类对象Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_data))//用kot返回map或者set类真正需要比较的数据，其他地方同理{parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return make_pair(Iterator(cur, _root), false);//插入失败，直接返回当前节点}}cur = new Node(data);Node* newnode = cur;//先保存一份插入节点，避免后续cur更新导致找不到cur->_col = RED;//新增节点为红色if (kot(data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//变色while (parent && parent->_col == RED)//父节点存在且为红色{Node* grandfather = parent->_parent;//父父节点if (grandfather->_left == parent)//parent为左孩子{Node* uncle = grandfather->_right;//叔叔节点（父节点的兄弟节点）if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_left)//cur为parent的左孩子{//形状：此时需要右单旋//    g//  p   u//cRotateR(grandfather);//右单旋parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else//cur为parent的右孩子，需要双旋{//形状//     g//  p    u//   cRotateL(parent);//先对p进行左单旋RotateR(grandfather);//再对整体进行右单旋parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}else//parent为右孩子，与上面类似，相当于翻个面{Node* uncle = grandfather->_left;//叔叔节点变为左孩子if (uncle && uncle->_col == RED)//情况1：父节点为红色，叔叔节点也为红色{//变色parent->_col = uncle->_col = BLACK;//将父节点和兄弟节点变为黑grandfather->_col = RED;//父父节点变为红//继续往上处理cur = grandfather;parent = cur->_parent;}else//情况2：叔叔节点不存在或者存在且为黑，需要旋转+变色{if (cur == parent->_right)//cur为parent的右孩子{//形状：此时需要左单旋//    g//  u   p//        cRotateL(grandfather);//左单旋parent->_col = BLACK;cur->_col = grandfather->_col = RED;}else//cur为parent的左孩子，需要双旋{//形状//     g//  u    p//      cRotateR(parent);//先对p进行右单旋RotateL(grandfather);//再对整体进行左单旋parent->_col = grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;//强制根节点为黑色return make_pair(Iterator(newnode, _root), true);}//查找Iterator Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (key > kot(cur->_data)){cur = cur->_right;}else if (key < kot(cur->_data)){cur = cur->_left;}else{return Iterator(cur, _root);}}return End();}
private://析构void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;//左孩子Node* subLR = subL->_right;//左孩子的右孩子//旋转过去parent->_left = subLR;subL->_right = parent;Node* ppNode = parent->_parent;//记录父父节点//更新父节点指针if (subLR)subLR->_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 RotateL(Node* parent){Node* subR = parent->_right;//右孩子Node* subRL = subR->_left;//右孩子的左孩子//旋转过去parent->_right = subRL;subR->_left = parent;Node* ppNode = parent->_parent;//父父节点//更新父节点指针if (subRL)subRL->_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;}}Node* _root = nullptr;
};

加入了析构函数。

myset.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key)//仿函数，返回需要用于比较的数据{return key;//对于set来说就是key}};public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}pair<iterator, bool> insert(const K& key){return _rbtree.Insert(key);}iterator find(const K& key){return _rbtree.Find(key);}private:RBTree<K, const K, SetKeyOfT> _rbtree;};
}

mymap.h

#pragma once
#include "RBTree.h"namespace txp
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv)//仿函数，返回需要比较的数据{return kv.first;//对于map来说，用于比较的就是first}};public://typename声明iterator是类型而不是静态变量typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;iterator begin(){return _rbtree.Begin();}iterator end(){return _rbtree.End();}const_iterator begin() const{return _rbtree.Begin();}const_iterator end() const{return _rbtree.End();}pair<iterator, bool> insert(const pair<K, V>& kv){return _rbtree.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _rbtree.Insert({ key, V() });return ret.first->second;}iterator find(const K& key){return _rbtree.Find(key);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _rbtree;};
}