✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
文章目录
前言一.`set`和`map`的初步封装1.树的节点封装修改2.`Find()`查找函数3.红黑树的封装修改4.set和map的初步封装框架 二.红黑树的迭代器封装1.基本框架2.常用成员函数3.前置`++`函数4.前置`--`函数5.红黑树封装中的迭代器函数6.红黑树封装中的插入函数修改 三.set封装完整实现1.set的迭代器函数2.set的插入函数3.测试 四.map封装完整实现1.map的迭代器函数2.map的插入函数3.map的`operator[]`函数4.测试 五.完整代码文件1.`RBTree.h`文件2.`Set.h`文件3.`Map.h`文件
前言
在之前的文章中，我们知道，set和map是两种常用的关联容器。他们内部通常使用红黑树来实现高效的查找，插入和删除操作，尽管它们提供了不同的接口函数，但它们依然可以通过共享相同的底层数据结构（也就是同一个红黑树）来实现。下面将详细讲解如何通过改造我们之前的红黑树来实现我们自己的set和map容器。（红黑树的实现在我上一篇文章中有详细讲解，不清楚的可以看我之前的文章）
一.set和map的初步封装
1.树的节点封装修改
首先我们来看一下我们之前的红黑树如何实现节点类的封装：
//节点类封装template<class K,class V>class RBTreeNode{public: //构造函数 RBTreeNode(const pair<K,V>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) ,_col(RED) {} //成员变量 RBTree<K,V>* _left; RBTree<K,V>* _right; RBTree<K,V>* _parent; pair<K,V> _kv; Colour _col;};我们学完set和map应该已经知道，set存储的是一个key值，而map存储的是一个键值对key-value，在上面这段代码中，如果通过这两个模板参数可以实现map，但set却没办法使用，因此，这里节点类的两个模板参数需要使用一个泛型参数来修改，这样就可以实现set和map能够共享一颗树。
修改如下：
//RBTree.h文件template<class T>class RBTreeNode {public: //构造函数 RBTreeNode(const T& data) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_data(data) ,_col(RED) {} //成员变量 RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; Colour _col;};通过上面的修改为一个模板参数就可以实现共享效果：
set存储的是一个键值key，这里的模板参数T就是键值key的类型
map存储的是一个键值对key-value，这里的模板参数T就是容器pair<key，value> 类型
2.Find()查找函数
在上面对节点封装进行修改后，这里又会产生新的问题，如果我们要通过键值Key来查找对应的节点（也就是Find()函数的参数是键值key，对于set来说直接通过键值key就能找到，但是map中的节点存储的是一个键值对key-value，也就是一个，pair(key,value)对象，直接通过参数key并不能查找，具体可以看下面函数
Node* Find(const K& key){ Node* cur=_root; while(cur){ //对于set来说，_data就是key //对于map来说，_data是一个piar(key,value)对象 if(cur->_data<key){ cur=cur->_right; } else if(cur->_data>key){ cur=cur->_left; } else{ return cur; } } return nullptr;}因此为了解决这个问题，这里需要借助一个仿函数来实现两个不同容器的查找
set的仿函数：
struct SetKeyOfT{ const K& operator()(const K& key){ return key; }};map的仿函数：
struct MapKeyOfT{ const K& operator()(const pair<K,V>& kv){ return kv.first; }};Find()函数：
Node* Find(const K& key){ Node* cur=_root; //对于set来说，这里的KeyOfT就是SetKeyOfT //对于map来说，这里的KeyOfT就是MapKeyOfT KeyOfT kot; while(cur){ if(kot(cur->_data)){ cur=cur->_right; } else if(kot(cur->_data)>key){ cur=cur->_left; } else{ return cur; } } return nullptr;}3.红黑树的封装修改
上面了解完如何实现两个不同容器之间的查找之后，这里就需要开始对原本的红黑树进行封装修改，从Find()函数中我们可以看到，需要一个新的模板参数KeyOfT，用来实现不同容器仿函数的查找功能。
修改如下:
//RBTree.h文件//增加一个新的模板参数KeyOfTtemplate<class K,class V,class KeyOfT>class RBTree{ typedef RBTreeNode<T> Node;public: //构造函数 RBTree() :_root(nullptr) {} //Node* Find(const K& key); //...其他成员函数 private: Node* _root;}4.set和map的初步封装框架
有了前面三个的基础这里就可以开始对set和map进行初步的封装，set和map的底层都是借用同一个红黑树。
set的初步封装框架：
//Set.h文件namesapce MySet{ template<class K> class Set{ //将仿函数设置为内部类 struct SetKeyOfT{ const K& operator()(const K& key){ return key; } }; public: //...其他成员函数 private: //第一个模板参数K是set存储的数据类型 RBTree<K,K,SetKeyOfT> _t; };};map的初步封装框架：
//Map.h文件namesapce MyMap{ template<class K,class V> class Map{ //将仿函数设置为内部类 struct MapKeyOfT{ const K& operator()(const pair<K,V>& kv){ return kv.first; } }; public: //...其他成员函数 private: //第一个模板参数K是set存储的数据类型 RBTree<K,pair<const K,V>,MapKeyOfT> _t; };};二.红黑树的迭代器封装
这里红黑树的迭代器封装其实和容器list比较类似，不能像string和vector一样使用原生指针作为迭代器，只能通过封装结点指针来实现迭代器。
1.基本框架
//迭代器封装template<class T,class Ptr,class Ref>class TreeIterator{ //重命名定义 typedef RBTreeNode<T> Node; typedef TreeIterator<T,Ptr,Ref> self; public: //节点指针 Node* _node; //构造函数 TreeIterator(Node* node) :_node(node) {} //...成员函数 }2.常用成员函数
operator*函数：
//T& operator*()//const T& operator*()//用模板参数Ref来实现两个不同返回类型的替换Ref opeartor*(){ return _node->_data;}operator->函数：
//T* operator->()//const T* operator->()//用模板参数Ptr来实现两个不同返回类型的替换Ptr operator->(){ return &_node->_data;}operator!=函数：
bool operator!=(const self& s)const { return _node!=s._node;}operator==函数：
bool operator==(const self& s)const { return _node==s._node;}3.前置++函数
self operator++(){ //如果该节点右子节点不为空，则到右子树中找最左节点 if(_node->_right){ Node* subleft=_node->_right; while(subleft->_left){ subleft=subleft->_left; } _node=subleft; } //如果该节点右子节点为空，则找到该节点父节点的左子节点的祖先节点 else{ Node* cur=_node; Node* parent=cur->_parent; while(parent){ //如果cur节点是父节点的右子节点，继续往上 if(cur==parent->_right){ cur=parent; parent=parent->_parent; } //如果cur节点是父节点的左子节点，停止 else{ break; } } _node=parent; } return *this;}4.前置--函数
self& operator--(){ if(_node->_left){ Node* subright=_node->_left; while(subright->_right){ subright=subright->_right; } _node=subright; } else{ Node* cur=_node; Node* parent=cur->_parent; while(parent){ if(cur==parent->_left){ cur=parent; parent=parent->_parent; } else{ break; } _node=parent; } return *this; }}5.红黑树封装中的迭代器函数
对于红黑树来说，有普通对象迭代器和const对象迭代器。
template<class ,class T,class KeyOfT>class RBTree{ //.... public: //普通对象迭代器 typedef TreeIterator<T,T*,T&> iterator; //const对象迭代器 typedef TreeIterator<T,const T*,const T&> const_iterator; iterator begin(){ Node* cur=_root; while(cur&&cur->_left){ cur=cur->_left; } return cur; } iterator end(){ return nullptr; } const_iterator begin()const { Node* cur=_root; while(cur&&cur->_left){ cur=cur->_left; } return cur; } const_iterator end()const { return nullptr; }}6.红黑树封装中的插入函数修改
有了前面红黑树封装的迭代器，这里插入函数就可以进行修改，从原本的bool类型，变为pair<iterator,bool>类型，其中，iterator表示插入位置的迭代器，如果差人成功，返回插入位置的迭代器和true；如果该值已经存在，返回该值位置的迭代器和false。
//这里第三个模板参数KeyOfT就可以用到pair<iteraotr,bool> insert(const T& data){ if(_root==nullptr){ _root=new Node(data); _root->_col=BLACK; return make_pair(_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 make_pair(cur,false); } } cur=new Node(data); cur=_col=RED; if(kot(parent->_data)<kot(data)){ parent->_right=cur; } else{ parent->_left=cur; } cur->_parent=parent; //更新平衡因子，旋转，变色 //... return make_pair(newnode,true);}三.set封装完整实现
1.set的迭代器函数
在前面通过对红黑树的迭代器进行封装之后，这里就可以直接实现set的迭代器函数
代码实现：namespace MySet{ template<class K> class set{ //内部类，用来获取set存储对象中的key值 struct SetKeyOfT{ const K& operator()(const K& key){ return key; } }; public: //这里的类模板还没有实例化对象，所以要加上关键字typename typedef typename RBTree<K,K,SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K,K,SetKeyOfT>::const_iterator const_iterator; //set的begin()函数 const_iterator begin()const { return _t.begin(); } //set的end()函数 const_iterator end()const { return _t.end(); } private: //第一个模板参数k是set存储的数据类型 RBTree<K,K,SetKeyOfT> _t; };};实现原理：
首先就是要将红黑树原本的迭代器类型进行命名重定义，这里有一个注意点，因为RBTree<K,K,SetKeyOfT>是一个类模板，现在还没有进行实例化，所以直接加上作用域限定符::后面加上迭代器类型会报错，因为编译器并不知道当前模板参数的具体类型，因此要加上关键字typename。
其次set还有一个性质就是对于key值，不能进行修改，所以使用迭代器时，如果对于当前迭代器解引用获取key值，要求只能访问，不能修改。因此我们这里可以将set的普通类型迭代器iterator和const类型迭代器const_iterator全都使用红黑树的const类型迭代器typename RBTree<K,K,SetKeyOfT>::const_iterator。
2.set的插入函数
set的插入函数返回的是一个pair<iterator,bool>类型
pair<iterator,bool> insert(const K& key){ return _t.insert(key);}注意：set的返回类型pair<iterator,bool>表面上看起来是普通类型的迭代器，但其实，我们是将红黑树的const_iterator迭代器重命名定义成了iterator，因此pair<iterator,bool>中的其实是const_iterator，但是红黑树的插入函数返回的又是一个iterator，所以这里直接写成上面的代码显然是错误的。
正确的写法是要进行一次类型转换：
pair<iterator,bool> insert(const K& key){ pair<typename RBTree<K,K,SetKeyOfT>::iterator ret=_t.insert(key); return pair<iterator,bool>(ret.first,ret.second);}为了实现从iterator类型转换为const_iterator，我们要在红黑树的迭代器封装中添加一个构造函数
TreeIterator(Node* node):_node(node){}3.测试
测试代码：
#include"Set.h"int main(){ MySet::set<int> s; s.insert(2); s.insert(10); s.insert(4); s.insert(7); MySet::set<int>::iterator sit=s.begin(); while(sit!=s.end()){ //(*sit)++; //这里修改key值就会报错 cout<<*sit<<" "; ++sit; } cout<<endl; return 0;}测试结果：
四.map封装完整实现
1.map的迭代器函数
这里map的迭代器函数和set的有些不同，因为set要求存储的key值不能被修改，而map只限定了键值对中的key值不能修改，而value值可以修改，所以这里使用红黑树类模板做参数时有些不同，通过pair<const K,V>实现key值不能修改，而value值可以修改。
namespace MyMap{ template<class K,class V> class Map{ struct MapKeyOfT{ const K& operator()(const pair<const K,V>& kv){ return kv.first; } }; public: //map的普通迭代器iterator typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::iterator iterator; //map的const类型迭代器const_iterator typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::const_iterator 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(); } //其他成员函数 //... private: RBTree<K,pair<const K,V>,MapKeyOfT> _t; };};2.map的插入函数
相较于set的插入函数，map的插入函数就比较简单，直接调用函数即可
pair<iterator,bool> insert(const pair<const K,V>& kv){ return _t.insert(kv);}3.map的operator[]函数
map相比于set还有一个其他的使用方法，就是[]，[]可以通过key值，返回value值。如果参数key值不存在map中，会将参数key值插入到map中，然后返回value的对应类型的初始化值，当然还可以通过[]修改对应key值的value值。
V& operator[](const K& key){ //V()是模板参数V的默认构造 pair<iterator,bool> rit=insert(make_pair(key,v())); return rit.first->second;}4.测试
测试代码：
#include"Map.h"void test1(){ MyMap::Map<int,int> m; m.insert(make_pair(3,3)); m.insert(make_pair(2,2)); m.insert(make_pair(1,1)); MyMap::Map<int,int>::iterator it=m.begin(); while(it!=m.end()){ //(it->first)++; //这里对key值修改就会报错 cout<<it->first<<" "<<it->second<<endl; ++it; } cout<<endl; m[3]=1; m[4]; m[5]=100; for(auto e : m){ cout<<e.first<<" "<<e.second<<endl; }}int main(){ test1(); return 0;}测试结果：
五.完整代码文件
1.RBTree.h文件
#include<iostream>#include<utility>#include<vector>#include<time.h>using namespace std;enum Colour { RED, BLACK};template<class T>class RBTreeNode {public: //构造函数 RBTreeNode(const T& data) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_data(data) ,_col(RED) {} //成员变量 RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; Colour _col;};//迭代器类封装template<class T,class Ptr,class Ref>class TreeIterator{ //重命名定义 typedef RBTreeNode<T> Node; typedef TreeIterator<T,Ptr,Ref> self; typedef TreeIterator<T,T*,T&> Iterator;public: Node* _node; TreeIterator(Node* node) :_node(node) {} TreeIterator(const Iterator& it) :_node(it._node) {} Ref operator*(){ return _node->_data; } Ptr operator->(){ return &_node->_data; } bool operator!=(const self& s)const { return _node !=s._node; } bool operator==(const self& s)const { return _node==s._node; } self& operator++(){ //如果该节点右子节点不为空，则到右子树中找最左节点 if(_node->_right){ Node* subleft=_node->_right; while(subleft->_left){ subleft=subleft->_left; } _node=subleft; } //如果该节点右子节点为空，则找到该节点父节点的左子节点的祖先节点 else{ Node* cur=_node; Node* parent=cur->_parent; while(parent){ //如果cur节点是父节点的右子节点，继续往上 if(cur==parent->_right){ cur=parent; parent=parent->_parent; } //如果cur节点是父节点的左子节点，停止 else{ break; } } _node=parent; } return *this; } self& operator--(){ //如果当前节点左子节点不为空，则到该节点的左子树中的最右节点 if(_node->_left){ Node* subright=_node->_left; while(subright->_right){ subright=subright->_right; } _node=subright; } //如果该节点左子节点为空，就到该节点的祖先节点的右子节点 else{ Node* cur=_node; Node* parent=cur->_parent; while(parent){ if(cur==parent->_left){ cur=parent; parent=parent->_parent; } else{ break; } } _node=parent; } return *this; }};template<class K , class T, class KeyOfT>class RBTree { typedef RBTreeNode<T> Node;public: //普通对象迭代器 typedef TreeIterator<T ,T* ,T&> iterator; //const对象迭代器 typedef TreeIterator<T ,const T* ,const T&> const_iterator; //构造函数 RBTree() :_root(nullptr) {} iterator begin(){ Node* cur=_root; while(cur&&cur->_left){ cur=cur->_left; } return cur; } iterator end(){ return nullptr; } const_iterator begin()const { Node* cur=_root; while(cur&&cur->_left){ cur=cur->_left; } return cur; } const_iterator end()const { return nullptr; } Node* Find(const K& key){ Node* cur=_root; KeyOfT kot; while(cur){ //这里参数key已经是K类型的，所以不用调用仿函数kot() if(kot(cur->_data)<key){ cur=cur->_right; } else if(kot(cur->_data)>key){ cur=cur->_left; } else{ return cur; } } return nullptr; } pair<iterator,bool> insert(const T& data) { if(_root==nullptr){ _root=new Node(data); _root->_col=BLACK; return make_pair(_root,true); } Node* parent=nullptr; Node* cur=_root; KeyOfT kot; while(cur) { //这里参数data是T类型的，是容器里存储的对象，不是K类型，所以要调用仿函数kot()获取key值 if(kot(cur->_data)<kot(data)) { parent=cur; cur=cur->_right; } else if(kot(cur->_data)>kot(data)) { parent=cur; cur=cur->_left; } else { return make_pair(cur,false); } } cur=new Node(data); cur->_col=RED; if(kot(parent->_data)<kot(data)){ parent->_right=cur; } else{ parent->_left=cur; } cur->_parent=parent; Node* newnode=cur; while(parent&&parent->_col==RED){ Node* grandfather=parent->_parent; //如果parent节点在左子节点 if(parent==grandfather->_left){ Node* uncle=grandfather->_right; //如果uncle节点存在且节点为红色 if(uncle&&uncle->_col==RED){ //变色 parent->_col=uncle->_col=BLACK; grandfather->_col=RED; //继续往上 cur=grandfather; parent=cur->_parent; } //如果uncle节点不存在 或者 节点为黑色 else{ //如果cur节点在左子节点 if(cur==parent->_left){ //右单旋 RotateR(grandfather); //旋转后变色 grandfather->_col=RED; parent->_col=BLACK; } //如果cur节点在右子节点 else{ //左双旋 //先左单旋，再右单旋 RotateL(parent); RotateR(grandfather); //旋转后变色 cur->_col=BLACK; grandfather->_col=RED; } break; } } //如果parent节点在右子节点 else{ Node* uncle=grandfather->_left; //如果uncle节点存在且节点为红色 if(uncle&&uncle->_col==RED){ //变色 parent->_col=uncle->_col=BLACK; grandfather->_col=RED; //继续往上 cur=grandfather; parent=cur->_parent; } //如果uncle节点不存在 后者 节点为黑色 else{ //如果cur节点在右子节点 if(cur==parent->_right){ //左单旋 RotateL(grandfather); //变色 parent->_col=BLACK; grandfather->_col=RED; } //如果cur节点在左子节点 else{ //右双旋 //先右单旋，再左单旋 RotateR(parent); RotateL(grandfather); //旋转后变色 cur->_col=BLACK; grandfather->_col=RED; } break; } } } _root->_col=BLACK; return make_pair(newnode,true); } int Height(){ return _Height(_root); } bool IsBlance(){ return _IsBlance(_root); }private: int _Height(Node* root){ if(root==nullptr){ return 0; } int leftheight=_Height(root->_left); int rightheight=_Height(root->_right); return leftheight>rightheight ? leftheight+1 : rightheight+1; } bool CheckColour(Node* root,int blacknum,int benchmark){ //如果节点是空，判断黑色节点个数是否等于基准值 if(root==nullptr){ if(blacknum!=benchmark){ return false; } return true; } //如果节点是黑色，黑色个数加加 if(root->_col==BLACK){ blacknum++; } //如果节点是红色，判断父节点是否也是红色，不能出现连续的红色节点 if(root->_col==RED&&root->_parent&&root->_parent->_col==RED){ cout<<root->_kv.first<<"RED False"<<endl; return false; } return CheckColour(root->_left,blacknum,benchmark) &&CheckColour(root->_right,blacknum,benchmark); } bool _IsBlance(Node* root){ if(root==nullptr){ return true; } //如果根节点不是黑色，返回错误 if(root->_col!=BLACK){ return false; } //设置一个基准值 int benchmark=0; Node* cur=root; while(cur){ if(cur->_col==BLACK){ benchmark++; } cur=cur->_left; } return CheckColour(root,0,benchmark); } //左单旋 void RotateL(Node* parent){ Node* cur=parent->_right; Node* curleft=cur->_left; Node* ppnode=parent->_parent; parent->_right=curleft; if(curleft){ curleft->_parent=parent; } cur->_left=parent; parent->_parent=cur; if(ppnode){ if(ppnode->_left==parent){ ppnode->_left=cur; cur->_parent=ppnode; } else{ ppnode->_right=cur; cur->_parent=ppnode; } } else{ cur->_parent=nullptr; _root=cur; } } //右单旋 void RotateR(Node* parent){ Node* cur=parent->_left; Node* curright=cur->_right; Node* ppnode=parent->_parent; parent->_left=curright; if(curright){ curright->_parent=parent; } cur->_right=parent; parent->_parent=cur; if(ppnode){ if(ppnode->_left==parent){ ppnode->_left=cur; cur->_parent=ppnode; } else{ ppnode->_right=cur; cur->_parent=ppnode; } } else{ cur->_parent=nullptr; _root=cur; } }private: Node* _root;};2.Set.h文件
#include"RBTree.h"namespace MySet{ template<class K> class set{ //内部类，用来获取set存储对象中的key值 struct SetKeyOfT{ const K& operator()(const K& key){ return key; } }; public: //这里的类模板还没有实例化对象，所以要加上关键字typename typedef typename RBTree<K,K,SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K,K,SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const { return _t.begin(); } const_iterator end()const { return _t.end(); } //这里返回的是const_iterator类型的迭代器 pair<iterator,bool> insert(const K& key){ //插入返回的是iterator类型的迭代器 pair<typename RBTree<K,K,SetKeyOfT>::iterator,bool> ret=_t.insert(key); return pair<iterator,bool>(ret.first,ret.second); } private: //第一个模板参数k是set存储的数据类型 RBTree<K,K,SetKeyOfT> _t; };};3.Map.h文件
#include"RBTree.h"namespace MyMap{ template<class K,class V> class Map{ struct MapKeyOfT{ const K& operator()(const pair<const K,V>& kv){ return kv.first; } }; public: typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::iterator iterator; typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::const_iterator const_iterator; iterator begin(){ return _t.begin(); } iterator end(){ return _t.end(); } const_iterator begin()const { return _t.begin(); } const_iterator end()const{ return _t.end(); } //operator[],通过key值，返回value值，具备插入和修改 V& operator[](const K& key){ pair<iterator,bool> rit=insert(make_pair(key,V())); return rit.first->second; } pair<iterator,bool> insert(const pair<const K,V>& kv){ return _t.insert(kv); } private: RBTree<K,pair<const K,V>,MapKeyOfT> _t; };};以上就是关于set和map的封装讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
