C++之map和set的模拟实现

目录

引言

红黑树迭代器实现

红黑树元素的插入

map模拟实现 

set模拟实现

---

之前我们已经学习了map和set的基本使用，但是因为map和set的底层都是用红黑树进行封装实现的，上期我们已经学习了红黑树的模拟实现，所以本期我们在红黑树模拟实现的基础之上，对红黑树进行进一步封装，实现map和set的模拟实现。

引言

首先大家思考一个问题，map和set既然它们底层都是使用红黑树进行模拟实现的，我们知道map是搜索二叉树中的kv模型，set是搜索二叉树中的k模型，那么两种模型难道使用两颗红黑树实现吗？

当然不是，map和set底层都是使用同一颗红黑树实现的，我们通过使用模板达到这一目的，这也体现了泛式编程的重要性。

我们对上期红黑树模拟实现的代码进行一点点改造，基于下述代码来进行map和set的模拟实现。

红黑树迭代器实现

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;RBTreeIterator(Node* node){_node = node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){Node* cur = _node;if (cur->_right){cur = cur->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = cur->_parent;while (parent){if (cur == parent->_left){_node = parent;break;}else{while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;break;}}}return *this;}Self& operator--(){Node* cur = _node;if (cur->_left){cur = cur->_left;while (cur->_left){cur = cur->_right;}_node = cur;}else{Node* parent = cur->_parent;while (parent){if (cur == parent->_right){_node = parent;break;}else{while (cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;break;}}}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s)  const{return _node == s._node;}Node* _node;
};

 上述代码有两个难点，分别是迭代器的++和迭代器的--。迭代器的++和迭代器的--操作。

搜索二叉树的遍历，++和--操作，一般是按照搜索二叉树的中序遍历为基础来进行进一步封装的。++操作要去判断当前节点是否有右孩子，--操作得先去判断是否有左孩子。

红黑树元素的插入

pair<iterator,bool> Insert(const T& data){//如果当前红黑树为空，则直接插入即可if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}//如果当前红黑树不为空，就要先找到合适的位置，然后进行节点的插入Node* cur = _root;Node* parent = _root->_parent;KeyOfT kot;while (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if(kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur),false);}}cur = new Node(data);Node* newnode = cur;cur->_col = RED;cur->_parent = parent;if ( kot(cur->_data) > kot(parent->_data)){parent->_right = cur;}else{parent->_left = cur;}//调整平衡while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//1.叔叔节点都存在，且都为红色节点，就要进行颜色平衡if (parent == grandfather->_right){Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//2.叔叔节点不存在//3.叔叔节点的颜色为黑色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//强制性的让根节点为黑色，符合红黑树的性质_root->_col = BLACK;return make_pair(iterator(newnode),true);}

在进行元素的插入时，我们需要注意，插入函数的返回值，返回值是一个pair类型的对象，first为迭代器（插入成功返回新插入的元素所对应的节点的迭代器，插入失败，返回已经存在的元素所对应的节点的迭代器），second为一个bool值（插入成功为true，插入失败为false）。

map模拟实现 

#pragma once
#include"RBTree.h"
namespace yjd 
{template<class K,class V >class map{public:struct MapKeyOfT{const K& operator()(const pair<K,V>& pair ){return pair.first;}};typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(){return _rbt.Find();}pair<iterator, bool> insert(const pair<K,V>& pair){return _rbt.Insert(pair);}V& operator[](const K& key){auto ret = _rbt.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<K, V>, MapKeyOfT> _rbt;};void MapTest(){map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("map", "地图"));dict["left"];dict["left"] = "左边";dict["map"] = "地图、映射";auto it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}

通过代码不难发现，map的模拟实现基本上还是套用红黑树的接口，唯一需要注意的就是operator[]这个函数接口，第一步是先转化为元素的插入，第二步通过第一步的返回值，来进一步访问插入元素的元素所对应的pair对象的second成员。简单来说operator[]的返回值就是括号内部key值所对应的pair对象的第二个second成员的引用。

在进行元素的插入时，我们先要找到元素合适的位置，然后再进行元素的插入，但是因为map元素的大小我们是根据pair对象的first成员进行比较的，所以我们使用到了仿函数MapKeyOfT，获取到了pair对象的第一个first成员去进行比较。

运行截图如下。

运行结果符合预期。

set模拟实现

#pragma once
#include"RBTree.h"
namespace yjd
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}iterator find(const K& key){return _rbt.Find(key);}pair<iterator, bool> insert(const K& k){return _rbt.Insert(k);}private:RBTree<K, K, SetKeyOfT> _rbt;};void test_set(){set<int> s;s.insert(1);s.insert(4);s.insert(2);s.insert(24);s.insert(2);s.insert(12);s.insert(6);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it <<" ";++it;}}}

set的模拟实现也是基于红黑树的接口，是对红黑树接口的进一步封装。相比较map的模拟实现，更简单一些。 

运行结果如下。

运行结果符合预期。