在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容器，希望对大家有帮助，祝生活愉快！