【C++模拟实现】map、set容器的模拟实现

作者：爱写代码的刚子

时间：2023.9.17

前言：本篇博客有关map、set的模拟实现，其底层采用了红黑树的结构，记录了模拟实现时的问题和解决方案。

---

map、set模拟实现的代码（insert部分）

部分一：红黑树的迭代器以及红黑树

enum Colour
{BLACK,RED
};///红黑树的节点///
template<class T>
struct RBTreeNode
{RBTreeNode(const T& kv):_left(nullptr),_parent(nullptr),_right(nullptr),_c(RED),_kv(kv){}RBTreeNode* _left;RBTreeNode* _parent;RBTreeNode* _right;Colour _c; T _kv;};//红黑树的迭代器类
template<class T,class Ref,class Ptr>
class __iterator
{typedef RBTreeNode<T> Node;typedef __iterator<T,Ref,Ptr> Self;typedef __iterator<T,T&,T*> Iterator;
public:__iterator(Node* it):_it(it){}//如果这个对象是const迭代器，实现的是普通迭代器转为const迭代器，//如果这个对象是普通迭代器，实现的是普通迭代器的拷贝构造。__iterator(const Iterator& t):_it(t._it){}Ref operator*(){return _it->_kv;}Ptr operator->(){return &_it->_kv;}Self& operator++()//前置++{if(_it->_right){Node* subLeft=_it->_right;while(subLeft->_left){subLeft=subLeft->_left;}_it=subLeft;}else{Node* cur = _it;Node* parent=_it->_parent;while(parent&&parent->_right==cur){cur=cur->_parent;parent=cur->_parent;}_it=parent;}return *this;}Self operator++(int)//后置++{__iterator tmp(_it);if(_it->_right){Node* subLeft=_it->_right;while(subLeft->_left){subLeft=subLeft->_left;}_it=subLeft;}else{Node* cur = _it;Node* parent=_it->_parent;while(parent&&parent->_right==cur){cur=cur->_parent;parent=cur->_parent;}_it=parent;}return tmp;}
///对--的重载暂时不实现(思路和++相反,将operator++中的_left换成_right,将_right换成_left即可)bool operator!=(const Self& l) const{return _it!=l._it;}bool operator==(const Self& l) const{return _it==l._it;}Node* _it;
};
//红黑树的模拟实现
template<class K,class T,class SetKeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;typedef __iterator<T,T&,T*> iterator;typedef __iterator<T,const T&,const T*> const_iterator;RBTree():_root(nullptr){}
//红黑树迭代器begin和end///iterator begin(){Node* cur=_root;if(!_root){return nullptr;}while(cur->_left){cur=cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur=_root;if(!_root){return nullptr;}while(cur->_left){cur=cur->_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}Node* Find(const K& key){Node* cur = _root;SetKeyOfT k;while (cur){if (k(cur->_data) < key){cur = cur->_right;}else if (k(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}pair<iterator,bool> insert(const T& kv){if(_root==nullptr){_root=new Node(kv);_root->_c=BLACK;return make_pair(iterator(_root),true);}Node* cur=_root;Node* parent=nullptr;SetKeyOfT k;while(cur){if(k(cur->_kv)>k(kv)){parent=cur;cur=cur->_left;}else if(k(cur->_kv)<k(kv)){parent=cur;cur=cur->_right;}else{return make_pair(iterator(cur),false);}}cur=new Node(kv);Node* newnode = cur;/if(k(parent->_kv)>k(kv)){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;//需要调整的情况while(parent&&parent->_c==RED){Node* grandfather=parent->_parent;if(grandfather->_left==parent){Node* uncle=grandfather->_right;//判断uncle的几种情况if(uncle&&uncle->_c==RED){uncle->_c=parent->_c=BLACK;grandfather->_c=RED;cur=grandfather;parent=cur->_parent;}else {if(cur==parent->_left){_RotateR(grandfather);grandfather->_c=RED;parent->_c=BLACK;}else{_RotateL(parent);_RotateR(grandfather);grandfather->_c=RED;cur->_c=BLACK;}break;}}else{Node* uncle=grandfather->_left;if(uncle&&uncle->_c==RED){uncle->_c=parent->_c=BLACK;grandfather->_c=RED;cur=grandfather;parent=cur->_parent;}else {if(cur==parent->_right){_RotateL(grandfather);parent->_c=BLACK;grandfather->_c=RED;}else{_RotateR(parent);_RotateL(grandfather);cur->_c=BLACK;grandfather->_c=RED;}break;}}}_root->_c=BLACK;return make_pair(iterator(newnode),true);}void _RotateR(Node* parent){Node*cur=parent->_left;Node*curRight=cur->_right;Node*ppnode=parent->_parent;cur->_right=parent;parent->_left=curRight;if(curRight){curRight->_parent=parent;}parent->_parent=cur;//处理ppnodeif(parent==_root){_root=cur;cur->_parent=nullptr;}else{if(ppnode->_left==parent){ppnode->_left=cur;}else{ppnode->_right=cur;}cur->_parent=ppnode;}}void _RotateL(Node* parent){Node* cur=parent->_right;Node* curLeft=cur->_left;Node* ppnode=parent->_parent;cur->_left=parent;parent->_right=curLeft;if(curLeft){curLeft->_parent=cur;}parent->_parent=cur;if(parent==_root){_root=cur;cur->_parent=nullptr;}else{if(ppnode->_left==parent){ppnode->_left=cur;}else{ppnode->_right=cur;}cur->_parent=ppnode;}  }Node* _root;
};

部分二：对set进行封装

template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key)//仿函数{return key; }};
public:typedef typename RBTree<K,K,SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K,K,SetKeyOfT>::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();}pair<iterator,bool> insert(const K& key){pair<typename RBTree<K,K,SetKeyOfT>::iterator,bool> ret= _t.insert(key);//这边我们需要注意，右边是普通迭代器，左边是const迭代器，我们需要实现普通迭代器构造const迭代器return pair<iterator,bool>(ret.first,ret.second);}private:RBTree<K,K,SetKeyOfT> _t;};

部分三：对map进行封装

template<class K,class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<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();}pair<iterator,bool> insert(const pair<K,V>& kv){return _t.insert(kv);}V& operator[](const K&key){pair<iterator,bool> ret = insert(make_pair(key,V()));return ret.first->second;}private:RBTree<K,pair<const K,V>,MapKeyOfT> _t;
};

遇到的问题以及解决方案

• 【问题】：由于map和set共用一颗树的结构，但是传入的数据类型并不相同，set直接插入key，而map要插入pair。在树里面全部采用统一的模版参数T。在insert的比较大小环节会出现错误，pair不能直接进行大小的比较（虽然库里面pair有进行大小比较的重载函数但是效果并不符合预期）

  【解决】：在set和map的结构体里写一个仿函数，在树里面调用名称相同但是功能不同的仿函数，达到对数据的统一比较的效果。

  map：

  
  

  set：

红黑树：

红黑树中的SetKeyOfT可以是其他名字，不要和set中的SetKeyOfT搞混了。

• 【问题】：普通迭代器如何构造const迭代器？

  由于set不能对数据进行修改，所以set的迭代器的下面使用红黑树的const迭代器实现的：

  

  观察set对insert函数的封装：
  

​ 由于set调用红黑树的insert函数而红黑树中insert函数默认返回iterator迭代器，而```pair<iterator,bool> insert(const K& key)``使用的是set中对红黑树中const迭代器封装后的迭代器，insert的返回值和该函数的返回值不相同，需要进行转换，由于红黑树中的迭代器没有实现转换就会出现以下报错：

【解决】：在红黑树的迭代器中实现普通迭代器对const迭代器的转换：

• 【问题】：如何实现map的pair中的key不能被修改？

  【解决】：

  注意！以下传入红黑树的模版参数中也需要加上const：

• 留意红黑树迭代器中的iterator++中的算法：

• 在实现迭代器时，这两个运算符是一定要重载的：
  

• Map中对[]的重载方法：