设计师逛的网站,淘宝网站短链接怎么做,网站页面html静态化,怎么建网站?在C标准库中#xff0c;set容器和map容器的底层都是红黑树#xff0c;它们的各种接口都是基于红黑树来实现的#xff0c;我们在这篇文章中已经模拟实现了红黑树 -【C】红黑树#xff0c;接下来我们在此红黑树的基础上来看看如何封装set和map。
一、共用一颗红黑树
我…在C标准库中set容器和map容器的底层都是红黑树它们的各种接口都是基于红黑树来实现的我们在这篇文章中已经模拟实现了红黑树 -【C】红黑树接下来我们在此红黑树的基础上来看看如何封装set和map。
一、共用一颗红黑树
我们在这篇文章中 -【C】set容器和map容器的基本使用清楚set是key搜索场景的结构map是key/value搜索场景的结构。所以要用红黑树封装它们两个就需要2棵红黑树这两颗红黑树整体逻辑差不多一样只是结点中的元素数据类型不一样一个是K类型一个是pairK,V类型。两棵极为相似的树只是一点不同如果实现两个会显得冗余那么我们就可以考虑使用模板来将结点中的数据类型泛型化使set和map底层共用一个红黑树。
我在先前的文章中已经实现了红黑树它是解决key/value搜索场景的我将那篇文章的源代码裁剪了一些重要的部分大家这里只需看懂这部分的功能
templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent; Colour _col;RBTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, 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共用一棵红黑树所以就需要把结点的数据类型泛型化(根据传来的类型来确定具体的类型)
templateclass T //如果是set就传K如果是map就传pairK,V
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent; Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};
那么RBTree也要跟着改
templateclass T
class RBTree
{typedef RBTreeNodeT 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
{templateclass Kclass set{public:bool insert(const K key){return _t.Insert(key);}private:RBTreeK _t;};
}
封装map
//MyMap.h
#include RBTree.h
namespace blue
{templateclass K,class Vclass map{public:bool insert(const pairK, V kv){return _t.Insert(kv);}private:RBTreepairK, V _t;};
}
这样我们就可以通过模板参数T来控制set和map共用一棵红黑树了
二、 红黑树中Insert带来的问题
通过观察上面红黑中Insert中的代码其实会有问题 我们的data可能是K类型也可能是pairK,V类型。如果是后者那么这样比较当然没问题那如果是前者就不能这样比较所以我们要对这个部分进行修改。
怎么修改呢去掉.first吗
我们如果去掉.first那么不管是K还是pairK,V都可以进行比较以pairK,V类型为例两个pair类型进行比较时先比较K如果K相同则比较V这与我们的本意相违背我们的要求是只比较K的值不能让V的值参与比较所以我们要解决问题不能仅仅是去掉.first。
我们可以在set和map类中写一个仿函数通过仿函数来获取K具体做法如下
#include RBTree.h
namespace blue
{templateclass Kclass set{struct KeyOfSet{const K operator()(const K key){return key;}};public:bool insert(const K key){return _t.Insert(key);}private:RBTreeK,KeyOfSet _t;};
}#include RBTree.h
namespace blue
{templateclass K,class Vclass map{struct KeyOfMap{const K operator()(const pairK, V kv){return kv.first;}};public:bool insert(const pairK, V kv){return _t.Insert(kv);}private:RBTreepairK, 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迭代器
templateclass T,class Ref,class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, 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为根的子树已经遍历完了接下来让curparentparentcur-_parent然后在做判断。最坏情况下cur _rootparentnullptr这时直接返回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为根的子树已经遍历完了接下来让curparentparentcur-_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 RBTreeIteratorT, T, T* Iterator; //普通迭代器typedef RBTreeIteratorT, 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 RBTreeK, K, KeyOfSet::Iterator iterator;typedef typename RBTreeK, 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 RBTreeK, pairK, V, KeyOfMap::Iterator iterator;typedef typename RBTreeK, pairK, 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.hvoid TestSet()
{blue::setint s;s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(6);blue::setint::iterator sit s.begin();while (sit ! s.end()){cout *sit ;sit;}cout endl;
}void TestMap()
{blue::mapstring, string dict;dict.insert({ sort, 排序 });dict.insert({ left, 左边 });dict.insert({ right, 右边 });blue::mapstring, 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::setint s)
{bit::setint::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接下来我们将它改为pairIterator,bool类型
pairIterator,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)
{pairiterator, bool ret _t.Insert({ key,V() });return (ret.first)-second;
}
是不是非常简单
六、其他问题
1、构造函数
RBTree() default;
2、拷贝构造
RBTree(const RBTreeK, 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
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent; Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};//Ref和Ptr是为了兼容普通迭代器和const迭代器
templateclass T,class Ref,class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, 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;}
};templateclass K,class T,class KeyOfT
class RBTree
{
public:RBTree() default;RBTree(const RBTreeK, T, KeyOfT t){_root Copy(t._root);}RBTree operator(RBTree tmp){swap(tmp._root);return *this;}~RBTree(){Destroy(_root);_root nullptr;}public:typedef RBTreeNodeT Node;typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, 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:pairIterator,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
{templateclass Kclass set{struct KeyOfSet{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, const K, KeyOfSet::Iterator iterator;typedef typename RBTreeK, 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:pairiterator,bool insert(const K key){return _t.Insert(key);}private:RBTreeK, const K, KeyOfSet _t;};
}
(3)MyMap.h
#pragma once
#include RBTree.h
namespace blue
{templateclass K,class Vclass map{struct KeyOfMap{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, KeyOfMap::Iterator iterator;typedef typename RBTreeK, pairconst 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:pairiterator,bool insert(const pairK, V kv){return _t.Insert(kv);}V operator[](const K key){pairiterator, bool ret _t.Insert({ key,V() });return (ret.first)-second;}private:RBTreeK, pairconst K, V, KeyOfMap _t;};
}
(4)Test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include MyMap.h
#include MySet.hvoid Print(const blue::setint s)
{blue::setint::const_iterator it s.end();while (it ! s.begin()){--it;cout *it ;}cout endl;
}void TestSet()
{blue::setint s;s.insert(5);s.insert(1);s.insert(3);s.insert(2);s.insert(6);blue::setint::iterator sit s.begin();//*sit 10;while (sit ! s.end()){cout *sit ;sit;}cout endl;Print(s);}void TestMap()
{blue::mapstring, string dict;dict.insert({ sort, 排序 });dict.insert({ left, 左边 });dict.insert({ right, 右边 });dict[left] 左边剩余;dict[insert] 插入;dict[string];blue::mapstring, 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容器希望对大家有帮助祝生活愉快
