c++编程(24)——map的模拟实现

欢迎来到博主的专栏：c++编程
博主ID：代码小号

map的底层

map的底层是一个红黑树，关于红黑树的章节博主写在了数据结构专栏当中，因此不再赘述。

template<class key,class T,class keyofT,class valueofT>
class RBtree
{
public:RBtree():_root(nullptr){}typedef RBtreeNode<T> Node;typedef RBtreeIterator<T> iterator;typedef const RBtreeIterator<T> const_iterator;pair<iterator,bool> find(const key& key){Node* cur = _root;while (cur != nullptr){if (key < kot(cur->_data))cur = cur->_left;else if (key > kot(cur->_data))cur = cur->_right;elsereturn make_pair(iterator(_root,cur),true);}return make_pair(iterator(_root,nullptr),false);}pair<iterator,bool> insert(const T& data){Node* newnode = new Node(data);if (_root == nullptr){_root = newnode;_root->_col = BLACK;return make_pair(iterator(_root,_root), true);}Node* cur = _root;Node* parent = _root;while (cur != nullptr){if (kot(newnode->_data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(newnode->_data) >kot( cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(_root,cur), false);}}if (kot(newnode->_data) > kot(parent->_data)){newnode->_parent = parent;parent->_right = newnode;}else{newnode->_parent = parent;parent->_left = newnode;}cur = newnode;keep_balance(parent, cur);return make_pair(iterator(_root,cur), true);}
//省略private:Node* _root;keyofT kot;valueofT vot;};

为了与标准库中函数原型相同，博主将inseet和find函数的返回类型修改成了pair<iterator,bool>。

红黑树的节点

enum colour
{RED,BLACK
};
template<class T>
struct RBtreeNode
{RBtreeNode(const T& data):_data(data),_right(nullptr),_left(nullptr),_parent(nullptr),_col(RED){}T _data;//值RBtreeNode* _right;//右子树RBtreeNode* _left;//左子树RBtreeNode* _parent;//父节点colour _col;//颜色
};

与在数据结构中写的红黑树不同，为了让红黑树能够同时称为set和map的底层，博主不再使用pair<key,value>作为节点数据的类型，而是使用T作为泛型，这是因为set的层是key型的红黑树，而map是key-value型的红黑树，这两者之间的区别就在于节点存的数据的类型。如果用pair<key,value>作为红黑树的节点数据类型，那就不能适配set，因此采用泛型T。

map的模拟实现

template<class key,class value>
class map
{
public:typedef pair<key, value> value_type;private:RBtree<key, value_type, mapkeyofT,valueofT> _t;
};

map需要key值映射value值，因此需要实例化出pair<key,value>类型的红黑树底层。

template<class key,class T,class keyofT,class valueofT>
class RBtree
{
public:RBtree():_root(nullptr){}
//省略private:Node* _root;keyofT kot;valueofT vot;};

在底层RBtree中，有两个私有成员需要注意，kot是key值提取器，vot是value值提取器，为什么要做出这种设计呢？我们以函数insert为例。

pair<iterator,bool> insert(const T& data)
{Node* newnode = new Node(data);if (_root == nullptr){_root = newnode;_root->_col = BLACK;return make_pair(iterator(_root,_root), true);}Node* cur = _root;Node* parent = _root;while (cur != nullptr){if (kot(newnode->_data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(newnode->_data) >kot( cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(_root,cur), false);}}if (kot(newnode->_data) > kot(parent->_data)){newnode->_parent = parent;parent->_right = newnode;}else{newnode->_parent = parent;parent->_left = newnode;}cur = newnode;keep_balance(parent, cur);return make_pair(iterator(_root,cur), true);
}

由于RBtree不仅用于map容器，还需要用于set容器，而set容器的_data只有一个key值，因此使用key值进行比较大小非常方便，而map的_data却是pair<key,value>类型，pair类型对象之间是不支持比较大小的（虽然标准库中也允许pair之间的对象比较大小，但却不是key值之间的比较），因此我们需要将data的key值提取出来。

key值提取器定义在map当中，实现如下：

struct mapkeyofT
{const key& operator()(const pair<key,value>& data){return data.first;}
};

这样我们使用kot(data)时，得到的是data当中的first成员，即key值，而vot则是提取data的second，即value值。

struct valueofT
{const value& operator()(const pair<key,value>& data){return data.second;}
};

map的查找与插入

由于RBtree底层已经设计好了insert和find函数，我们只需要复用RBtree中的对应函数就行，这里很简单。

pair<iterator,bool> insert(const value_type& data)
{return _t.insert(data);
}

pair<iterator, bool> find(const key& key)
{return _t.find(key);
}

map的迭代器

红黑树的迭代器设计就比较麻烦了，RBtree的迭代器是一个双向迭代器，支持前进操作operator++，和后退操作operator--，前进与后退的行为与二叉搜索树的中序遍历完全一致。因此map的实现的难点完全在这里（因为红黑树的底层设计在之前的博客就已经完成了）。

struct RBtreeIterator
{typedef RBtreeNode<T> Node;typedef RBtreeIterator<T> Self;typedef T value_type;RBtreeIterator(Node* root=nullptr,Node* node=nullptr):_root(root),_node(node){}Node* _root;Node* _node;
};

RBtree的迭代器需要存储两个值，一个是存储迭代器指向的树_root，另外一个则是存储指向_root的节点_node。

begin()函数返回_root的最左边的节点，这是因为二叉搜索树中序遍历的第一个节点就是此节点，因此我们将其设置成起始位置begin。

而c++规定，end（）返回的迭代器需要不能指向有效节点，那么我们返回一个空节点（nullptr）即可（实际STL库中并非如此）。

至于operator!=等操作，比较简单，博主直接给上代码。

	template<class T>struct RBtreeIterator{typedef RBtreeNode<T> Node;typedef RBtreeIterator<T> Self;typedef T value_type;RBtreeIterator(Node* root=nullptr,Node* node=nullptr):_root(root),_node(node){}const Self& operator=(const RBtreeIterator it)const{_root = it._root;_node = it._node;}value_type& operator*(){return _node->_data;}value_type* operator->(){return &(_node->_data);}Self& begin(){Node* y = _root;while(y && y->_left != nullptr){y = y->_left;}_node = y;return *this;}const Self& begin() const{Node* y = _root;while (y && y->_left != nullptr){y = y->_left;}_node = y;return *this;}Self& end(){_node = nullptr;return *this;}bool operator!=(Self& it)const{return _node != it._node;}Node* _root;Node* _node;};

接下来就是重点的operator++和operator–操作了，前进的操作需要按照中序遍历的规则。因此我们先来顺一下二叉树的中序遍历规律吧。

情况（1），当前节点的右子树存在时。

根据中序遍历的规则，如果右子树存在，那么下一个遍历的节点就会在右子树的最左节点

情况2，如果当前节点不存在右子树，且是父节点的左节点。

那么下一个遍历的节点就会回溯到其父节点。

情况3，如果当前节点不存在右子树，而且是父节点的右节点

那么就一直回溯，回溯到当前节点是父节点的左子树的父节点处（有点绕，但确实是这样）。

代码如下：

	const Self& operator++(){assert(_node);Node* y = nullptr;if (_node->_right != nullptr){y = _node->_right;while (y->_left != nullptr){y = y->_left;}_node = y;}else{Node* parent = _node->_parent;if (parent->_left == _node)_node = parent;else{y = _node;while (parent&&y == parent->_right){y = parent;parent = y->_parent;}_node = parent;}}return RBtreeIterator(_root, _node);}

而后退操作（operator--）则是反过来，我们来看看迭代器是如何实现后退操作的：
情况（1）如果当前节点是空节点（如果是end()返回的迭代器就是空节点）
那么我们就找到搜索二叉树的最右节点。

情况2，如果当前节点的左子树存在。

那么我们寻找左子树的最右节点。

情况（3）当前节点的左子树不存在。

那么我们就回溯到当前节点是父节点的右子节点的父节点处。

代码如下：

const Self& operator--()
{Node* y = nullptr;if (_node == nullptr)//end(){y = _root;while (y && y->_right){y = y->_right;}_node = y;}else if (_node->_left!=nullptr){y = _node->_left;while (y->_right != nullptr){y = y->_right;}_node = y;}else{y = _node;Node* parent = y->_parent;while (parent->_left == y){y = parent;parent = y->_parent;}_node = parent;}return *this;
}