【c++篇】：解读Set和Map的封装原理--编程中的数据结构优化秘籍

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客

前言

在之前的文章中，我们知道，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就是MapKeyOfTKeyOfT 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文件//增加一个新的模板参数KeyOfT
template<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://这里的类模板还没有实例化对象，所以要加上关键字typenametypedef 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的普通迭代器iteratortypedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::iterator iterator;//map的const类型迭代器const_iteratortypedef 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://这里的类模板还没有实例化对象，所以要加上关键字typenametypedef 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的封装讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！