【C++】用红黑树封装set和map

在C++标准库中，set容器和map容器的底层都是红黑树，它们的各种接口都是基于红黑树来实现的，我们在这篇文章中已经模拟实现了红黑树 ->【C++】红黑树，接下来我们在此红黑树的基础上来看看如何封装set和map。

一、共用一颗红黑树

我们在这篇文章中 ->【C++】set容器和map容器的基本使用，清楚set是key搜索场景的结构，map是key/value搜索场景的结构。所以要用红黑树封装它们两个就需要2棵红黑树，这两颗红黑树整体逻辑差不多一样，只是结点中的元素数据类型不一样，一个是K类型，一个是pair<K,V>类型。两棵极为相似的树，只是一点不同，如果实现两个会显得冗余，那么我们就可以考虑使用模板来将结点中的数据类型泛型化，使set和map底层共用一个红黑树。

我在先前的文章中已经实现了红黑树，它是解决key/value搜索场景的，我将那篇文章的源代码裁剪了一些重要的部分，大家这里只需看懂这部分的功能：

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* 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;elsereturn false;}cur = new Node(kv);cur->_col = RED; if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_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){RotateR(grandfather);parent->_col = BLACK; grandfather->_col = RED;}else {RotateL(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{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}
private:Node* _root = nullptr; 
};

此时，结点中数据类型是pair，这样我们就把这个结点的数据类型写"死"了，set容器底层就不能用这个红黑树，我们要实现set和map共用一棵红黑树，所以就需要把结点的数据类型泛型化(根据传来的类型来确定具体的类型)：

template<class T>  //如果是set就传K，如果是map就传pair<K,V>
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){}
};

那么，RBTree也要跟着改：

template<class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data.first < data.first)parent = cur,cur = cur->_right;else if (cur->_data.first > data.first)parent = cur,cur = cur->_left;elsereturn false;}cur = new Node(data);cur->_col = RED; if (parent->_data.first < data.first)parent->_right = cur;elseparent->_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){RotateR(grandfather);parent->_col = BLACK; grandfather->_col = RED;}else {RotateL(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{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}
private:Node* _root = nullptr; 
};

封装set：

//MySet.h
#include "RBTree.h"
namespace blue
{template<class K>class set{public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K> _t;};
}

封装map：

//MyMap.h
#include "RBTree.h"
namespace blue
{template<class K,class V>class map{public:bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<pair<K, V>> _t;};
}

这样我们就可以通过模板参数T来控制set和map共用一棵红黑树了！

二、 红黑树中Insert带来的问题

通过观察上面红黑中Insert中的代码，其实会有问题：

我们的data可能是K类型，也可能是pair<K,V>类型。如果是后者，那么这样比较当然没问题，那如果是前者，就不能这样比较，所以我们要对这个部分进行修改。

怎么修改呢？去掉.first吗？

我们如果去掉.first，那么不管是K还是pair<K,V>都可以进行比较，以pair<K,V>类型为例，两个pair类型进行比较时先比较K，如果K相同则比较V，这与我们的本意相违背，我们的要求是只比较K的值，不能让V的值参与比较！所以我们要解决问题，不能仅仅是去掉.first。

我们可以在set和map类中写一个仿函数，通过仿函数来获取K，具体做法如下：

#include "RBTree.h"
namespace blue
{template<class K>class set{struct KeyOfSet{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K,KeyOfSet> _t;};
}#include "RBTree.h"
namespace blue
{template<class K,class V>class map{struct KeyOfMap{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<pair<K, V>,KeyOfMap> _t;};
}

 这时我们就需要在红黑树中加一个模板参数：

我们明确知道map是需要这个仿函数来获取K值的，但是在set中也写一个仿函数来获取K值，有人开始会觉得这是多余的，因为set中的元素类型本身就是K类型，但是不要忽略一点，set和map是共用同一份模板的，map需要这个仿函数，那么set也必须有这个仿函数，set这里的仿函数就是为了兼容map，这时，红黑树的第二个模板参数KeyOfT就出现了。

三、erase和find带的来问题

我们知道set容器和map容器都有erase和find接口，这两个接口都是根据K值来进行的，如果我们要在红黑树中实现这两个接口那么必须知道K的值，我们根据K的值来进行删除和查找。但是现在，我们自己实现的这个红黑树中并没有办法拿到K的值，也就是说在我们目前这棵红黑树中若要实现erase和find是做不到的！

为了获取K的值，我们可以在RBTree中再添加一个模板参数K，专门用来获取K的值：

在set中：

在map中：

其实，这里的set中传了两个K，第一个K就是兼容map的。因为map需要这个K，那么在TRBTree中就必须增加一个模板参数，所以set就必须传一个K。

那么在RBTree中erase和find接口就可以这样写：

bool find(const K& key)
{//...
}bool erase(const K& key)
{//...
}

 四、迭代器

红黑树的迭代器和我们在模拟实现list时思路是一样的，因为红黑树的底层空间是不连续的，所以我们不能直接"typedef Node* iterator"，我们要单独用一个类型封装结点的指针，再通过重载运算
符实现，让迭代器具有像指针一样访问的行为：

//Ref和Ptr是为了兼容普通迭代器和const迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node; //当前结点指针RBTreeIterator(Node* node):_node(node){}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和map都是双向迭代器，所以它们的迭代器应该要支持++和--操作，由于它们的迭代器是复用红黑树的，所以红黑树中的迭代器也要实现++和--操作，list迭代器的++或--操作实现起来非常简单，只需利用next指针就好；反观红黑树，它的++/--操作要求必须满足中序遍历规则，红黑树的中序遍历是有序的，假设某棵红黑树的中序遍历是"1   3    5    6    7   9" ，如果迭代器在3这个位置，那么++后就必须到5，--后就必须到1。迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

那么如何实现++操作呢？(分为以下几种情况)

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的右子树存在

++后，只需找到右子树的最左结点即可。

2、cur的右子树为空

(1)cur是parent的左孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的右孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。最坏情况下，cur = _root，parent=nullptr，这时直接返回parent即可，我们这里让结束位置为nullptr。

代码实现：

Self& operator++(){Node* cur = _node;Node* parent = cur->_parent;if (cur->_right)  //右子树不为空，找右子树的最左结点{cur = cur->_right;while (cur->_left)cur = cur->_left;_node = cur;}else{while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}//直到cur是parent的左，那么parent就是我们的目标   //极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent)_node = parent;}return  *this;}

那么如何实现--操作呢？(分为以下几种情况) 

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

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的左子树存在

--后，只需找到左子树的最右结点即可。

2、cur的左子树为空

(1)cur是parent的右孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的左孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。

代码实现：

Self& operator--(){Node* cur = _node;Node* parent = cur->_parent;if (cur->_left) //左子树不为空，找左子树的最右结点{cur = cur->_left;while (cur->_right)cur = cur->_right;_node = cur;}else{while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}//直到cur是parent的右，那么parent就是我们的目标   _node = parent;}return *this;}

完成这一步，我们迭代器的封装任务差不多已经完成了，接下来我们需要在红黑树中实现Begin和End：

public:typedef RBTreeIterator<T, T&, T*> Iterator;  //普通迭代器typedef RBTreeIterator<T, const T&,const T*> ConstIterator; //const迭代器Iterator Begin(){Node* cur = _root;while (cur->_left)cur = cur->_left;return Iterator(cur);}Iterator End(){return Iterator(nullptr);  //我们这里让nullptr当最终结点}ConstIterator Begin() const{Node* cur = _root;while (cur->_left)cur = cur->_left;return ConstIterator(cur);}ConstIterator End() const{return ConstIterator(nullptr);}

在set中：

public:typedef typename RBTree<K, K, KeyOfSet>::Iterator iterator;typedef typename RBTree<K, K, KeyOfSet>::ConstIterator 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();}

在map中：

public:typedef typename RBTree<K, pair<K, V>, KeyOfMap>::Iterator iterator;typedef typename RBTree<K, pair<K, V>, KeyOfMap>::ConstIterator 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();}

 我们大致的任务已经完成了，接下来我们来写一段代码验证一下(看看是否会出现错误)：

//Test.cpp
#include "MyMap.h"
#include "MySet.h"void TestSet()
{blue::set<int> s;s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(6);blue::set<int>::iterator sit = s.begin();while (sit != s.end()){cout << *sit << " ";++sit;}cout << endl;
}void TestMap()
{blue::map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });blue::map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}int main()
{TestSet();cout << "-----------------------" << endl;TestMap();return 0;
}

运行结果：

运行结果暂时没有什么问题。

这里有一个bug，看下面测试代码：

void Print(const blue::set<int>& s)
{bit::set<int>::const_iterator it = s.end();while (it != s.begin()){--it;cout << *it << " ";}cout << endl;
}

我们上面将end()指向nullptr，那么如果逆向遍历，--it就会出现错误，所以我们在--it时先判断一下，如果指向空，那么就修改_node为红黑树的最后一个结点，那么，问题又来了，怎么获得最后一个结点呢？所以我们需要知道红黑树的头结点，所以，我们在RBTreeIterator这个类中还需要一个成员变量来记录根节点：

修改operator--如下：

Self& operator--() {if (_node == nullptr){Node* cur = _root;while (cur->_right)cur = cur->_right;_node = cur;return *this;}Node* cur = _node;Node* parent = cur->_parent;if (cur->_left) //左子树不为空，找左子树的最右结点{cur = cur->_left;while (cur->_right)cur = cur->_right;_node = cur;}else{while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}//直到cur是parent的右，那么parent就是我们的目标   _node = parent;}return *this;}

解决完上述问题，还有一个问题，set和map中的K的值是不允许修改的，因为若修改就可能会破坏红黑树的结构，但我们写的代码中通过普通迭代器是能够修改的，如果要解决可以这样修改：

在set中：

在map中：

五、[]

好了，好了，到这里我们将上面的坑都踩完了，接下来最后最后一个功能，也是比较重要的，就是处理map中[]的实现逻辑：

map中的[]的逻辑其实就是利用了insert接口。

我们在红黑树中实现Insert的返回值是bool，接下来我们将它改为pair<Iterator,bool>类型：

pair<Iterator,bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return true;return { Iterator(_root, _root),true };}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;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 false;return { Iterator(cur, _root),false };}cur = new Node(data);Node* newnode = cur;cur->_col = RED; if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_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){RotateR(grandfather);parent->_col = BLACK; grandfather->_col = RED;}else {RotateL(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{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;//return true;return { Iterator(newnode, _root),true };
}

完成对Insert的调整后，在set和map的insert也要跟着调：

在set中：

在map中：

接下来，我们就着手实现[]，在map中：

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

是不是非常简单！ 

六、其他问题

1、构造函数

RBTree() = default;

2、拷贝构造

RBTree(const RBTree<K, T, KeyOfT>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newnode = new Node(root->_data);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;
}

3、赋值重载

RBTree& operator=(RBTree tmp)
{swap(tmp._root);return *this;
}

4、析构函数

~RBTree()
{Destroy(_root);_root = nullptr;
}void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

七、源码 

(1)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){}
};//Ref和Ptr是为了兼容普通迭代器和const迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node; //当前结点指针Node* _root; //记录红黑树的根结点RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}Self& operator++() {Node* cur = _node;Node* parent = cur->_parent;if (cur->_right)   //右子树不为空，找右子树的最左结点{cur = cur->_right;while (cur->_left)cur = cur->_left;_node = cur;}else{while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}//直到cur是parent的左，那么parent就是我们的目标   //极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent) _node = parent;}return  *this;}Self& operator--() {if (_node == nullptr){Node* cur = _root;while (cur->_right)cur = cur->_right;_node = cur;return *this;}Node* cur = _node;Node* parent = cur->_parent;if (cur->_left) //左子树不为空，找左子树的最右结点{cur = cur->_left;while (cur->_right)cur = cur->_right;_node = cur;}else{while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}//直到cur是parent的右，那么parent就是我们的目标   _node = parent;}return *this;}Ref operator*() const{return _node->_data;}Ptr operator->() const{return &(_node->_data);}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
{
public:RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}RBTree& operator=(RBTree tmp){swap(tmp._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T, const T&,const T*> ConstIterator;Iterator Begin(){Node* cur = _root;while (cur->_left)cur = cur->_left;return Iterator(cur,_root);}Iterator End(){return Iterator(nullptr,_root);}ConstIterator Begin() const{Node* cur = _root;while (cur->_left)cur = cur->_left;return ConstIterator(cur,_root);}ConstIterator End() const{return ConstIterator(nullptr,_root);}public:pair<Iterator,bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return true;return { Iterator(_root,_root),true };}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;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 false;return { Iterator(cur,_root),false };}cur = new Node(data);Node* newnode = cur;cur->_col = RED; if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_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){RotateR(grandfather);parent->_col = BLACK; grandfather->_col = RED;}else {RotateL(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{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;//return true;return { Iterator(newnode,_root),true };}private:void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* pParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;subL->_parent = pParent;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left)parentParent->_left = subR;elseparentParent->_right = subR;subR->_parent = parentParent;}}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_data);newnode->_left = Copy(root->_left);newnode->_right = Copy(root->_right);return newnode;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}
private:Node* _root = nullptr; 
};

(2)MySet.h 

#pragma once
#include "RBTree.h"
namespace blue
{template<class K>class set{struct KeyOfSet{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, KeyOfSet>::Iterator iterator;typedef typename RBTree<K, const K, KeyOfSet>::ConstIterator 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();}public:pair<iterator,bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, KeyOfSet> _t;};
}

(3)MyMap.h 

#pragma once
#include "RBTree.h"
namespace blue
{template<class K,class V>class map{struct KeyOfMap{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::ConstIterator 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();}public:pair<iterator,bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert({ key,V() });return (ret.first)->second;}private:RBTree<K, pair<const K, V>, KeyOfMap> _t;};
}

(4)Test.cpp 

#define _CRT_SECURE_NO_WARNINGS 1#include "MyMap.h"
#include "MySet.h"void Print(const blue::set<int>& s)
{blue::set<int>::const_iterator it = s.end();while (it != s.begin()){--it;cout << *it << " ";}cout << endl;
}void TestSet()
{blue::set<int> s;s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(6);blue::set<int>::iterator sit = s.begin();//*sit += 10;while (sit != s.end()){cout << *sit << " ";++sit;}cout << endl;Print(s);}void TestMap()
{blue::map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];blue::map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}int main()
{TestSet();cout << "-----------------------" << endl;TestMap();return 0;
}

八、总结

本篇内容到这里就结束啦，主要讲了如何用红黑树来封装set和map容器，希望对大家有帮助，祝生活愉快！