[C++数据结构]map与set的模拟实现
一、对于map和set的源码分析
想要对于map和set进行模拟实现，我们首先就需要对于map和set的源码进行分析
我们发现在set和map中包含有如下的头文件
于是我们可以先打开这些头文件，我们先不考虑multimap与multiset
我们可能会因为set只有存数据而会误以为他里面使用的是key模型的红黑树，但是其实不是的。在stl库里面map和set使用的是同一棵key-val的红黑树。
如下所示，可以看出来
不过虽然使用的是key-val的红黑树，但是它的key和val都是key
根据上面的结构，难道库里面以空间换时间，为了只使用同一颗树，牺牲了一半的空间吗？当然以上都仅仅只是我们的猜测
我们先再来看一下map的底层
我们似乎发现，这个也很奇怪，val竟然是个pair类型的。
也就是说
- set是<K,K>模型的树
- map是<K，pair>模型的树
因此，我们来观察一下这棵树到底是什么情况了
如下所示，header就是这棵树的根节点，它的类型是通过的两次typedef出来的，我们可以注意到，这个结点的类型，存储的就是value
但是这个val不是我们前面所说的key-val中的val。这里的val对于map而言是pair，对于set而言是key
所以说，真正决定树里面存储的是什么，看的是第二个模板参数，而不是第一个模板参数。
我们现在再来观测一下这个红黑树结点里面是什么，如下所示，这里是通过一个继承关系来搞定的。派生类存储的是value，而基类存储的是三叉链的指针，以及颜色
那么在这里我们似乎看到了，在这棵树里面，我们好像并不是很需要这个key类型的模板参数，那么事实上是如此的吗？其实不是的，这个key还必须得传入，因为有一个接口会使用到他。即对于map而言，find这个接口它是通过key来进行比较的。所以必须传入key的类型
二、红黑树改造
1.基本节奏的改造
因为关联容器中，要想让两者底层使用相同的代码,需要对红黑树进行一定的改造,首先需要改造红黑树的模板参数。set只需要指定key的类型，但是map除了需要指定key的类型还需要指定value的类型，所以原先的模板参数是无法做到通用的，因为你不知道红黑树中存的是key还是pair对象。
因此我们可以设定一个class K接收key的类型，再设定一个class T接收容器内元素的类型。如果是set的话T的类型就是key的类型，如果是map的话T的类型就是一个pair。
如下是map与set的基本结构
可以看到，我们很巧妙的使用了一层红黑树上的泛型，使用同一个树模板来实现的
如下是调用图
2.比较
如下所示，当我们将原来的kv改为了_data的时候，下面的代码也要随之改变，但是下面的代码真的正确吗？
对于set而言，_data就是目标值的类型，这个类型是什么我们是不确定的，所以需要它自己提供一个运算符重载，或者仿函数来解决。
如果是map的话，这里的_data就是pair类型的，我们就需要去取出第一个元素，也就是key类型的来进行比较。（这里需要注意，虽然pair本身提供了比较，但是这里的比较并非我们所期望的比较方式，我们只需要比较first，而库里面的重载先比较first，然后比较second的）
所以，我们先来解决当_data为pair时候，如何取出第一个元素呢？，因为我们的是泛型，所以这个_data的取法还是需要注意的。这里我们可以使用一共仿函数，但是这里的仿函数与之前不同的是这里的仿函数主要集中解决取数的问题
如下所示，我们在map和set里面写两个内部类，这个内部类里面是一个运算符重载，充当仿函数。对于map萃取处它的key，对于set萃取出它本身
这样的话，我们就可以在红黑树中用仿函数了因此我们就解决了map还是set的比较
如下是他们之间的调用关系
对于我们这样的处理,当我们写find函数的时候,也可以使用
然后我们就写出insert的接口了
三、迭代器
1.迭代器
我们前面的插入功能已经完成,现在我们来解决迭代器。
改造后的红黑树，最重要的功能之一就是支持双向迭代器，以最左结点为首，以最右结点为尾。
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node)
: _node(node)
{}
RBTreeIterator(const Iterator& it)
: _node(it._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
迭代器的拷贝构造函数有两个用途：
- 以普通迭代器拷贝出普通迭代器（普通迭代器调用时）
- 以普通迭代器拷贝出const迭代器（const迭代器调用时）
2.operator++
Self& operator++()
{
if (_node->_right)//右不为空，找右子树的最左结点
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else//右为空，向上找孩子是父亲左的那个父亲
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)
{
Self tmp = *this;
++*this;
return tmp;
}
- 前置++的思路：
- 右不为空，找右子树的最左结点
- 右为空，向上找孩子是父亲左的那个父亲
- 后置++：复用前置++，返回临时对象
3.operator--
Self& operator--()
{
if (_node->_left)//左不为空，找左子树的最右结点
{
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else//左为空，向上找孩子是父亲右的那个父亲
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_left == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--(int)
{
Self tmp = *this;
--*this;
return tmp;
}
- 前置- -的思路：
- 左不为空，找左子树的最右结点
- 左为空，向上找孩子是父亲右的那个父亲
- 后置- -：复用前置- -，返回临时对象
4. 与库里面的迭代器的差异
我们自己实现的迭代器，但是与库里面的迭代器还是有很大的区别的
实际上在库里面的红黑树还有一个哨兵位
这个哨兵位的parent指向根节点，左孩子和右孩子分别指向最小和最大，这样的话会使得迭代器找最小结点和最大结点的时候会方便很多
不过虽然如此，但是也是需要付出一定的代价的，那就是对于实现的难度上来说，更加困难了，因为旋转以后这个哨兵位的指针就需要做出一定的改变
而且上面的话对于正常情况下++和–都是没有什么问题的，但是当出现下面的这种特殊情况的时候，就会出现死循环，即parent和cur陷入死循环了。我们就需要额外做出特殊判断了
四、map的[]操作
map的[]操作主要是依靠insert操作完成的。所以我们还得将inser加上一些东西来完成
于是，我们就要从底层开始修改，先处理红黑树的插入操作
如下就是我们想办法将红黑树的插入操作由bool变为了pair的返回值
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
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(iterator(cur), false);
}
}
Node* newnode = new Node(data);
cur = newnode;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (grandparent->_right == parent)//uncle在左，parent在右
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)//uncle为红，变色+向上调整
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle为空或为黑，变色+旋转
{
if (parent->_right == cur)//左单旋
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//右左旋
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
}
}
else//parent在左，uncle在右
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)//右单旋
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//左右旋
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
解决了红黑树的返回值，然后我们可以直接修改map与set的返回值
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
然后下面就很好写了
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}五、完整代码
-
红黑树代码
#pragma once enum Color { RED, BLACK }; template<class T> struct RBTreeNode { T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Color _color; RBTreeNode(const T& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_color(RED) {} }; template<class T, class Ptr, class Ref> struct __TreeIterator { typedef RBTreeNode<T> Node; typedef __TreeIterator<T, Ptr, Ref> Self; typedef __TreeIterator<T, T*, T&> Iterator; 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 = _node->_parent; while (parent) { if (parent->_right == cur) { cur = parent; parent = parent->_parent; } 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 (parent->_left == cur) { 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; typedef __TreeIterator<T, const T*, const T&> const_iterator; iterator begin() { Node* leftMin = _root; while (leftMin && leftMin->_left) { leftMin = leftMin->_left; } return iterator(leftMin); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* leftMin = _root; while (leftMin && leftMin->_left) { leftMin = leftMin->_left; } return const_iterator(leftMin); } const_iterator end() const { return const_iterator(nullptr); } RBTree() :_root(nullptr) {} Node* Find(const K& key) { Node* cur = _root; KeyOfT kot; while (cur) { 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) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_color = BLACK; return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; 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; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else if (kot(parent->_data) > kot(data)) { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_color == RED) { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { Node* uncle = grandfather->_right; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_left == cur) { RotateR(grandfather); parent->_color = BLACK; grandfather->_color = RED; break; } else { RotateL(parent); RotateR(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED) { parent->_color = BLACK; uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_color == BLACK) { if (parent->_right == cur) { RotateL(grandfather); grandfather->_color = RED; parent->_color = BLACK; break; } else { RotateR(parent); RotateL(grandfather); cur->_color = BLACK; grandfather->_color = RED; break; } } } } _root->_color = BLACK; return make_pair(iterator(newnode), true); } void RotateL(Node* parent) { _rotatecount++; Node* cur = parent->_right; Node* curleft = cur->_left; Node* ppnode = parent->_parent; //改变parent parent->_right = curleft; parent->_parent = cur; //改变curleft if (curleft != nullptr) { curleft->_parent = parent; } //改变cur cur->_left = parent; cur->_parent = ppnode; //改变ppnode if (ppnode == nullptr) { _root = cur; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } } void RotateR(Node* parent) { _rotatecount++; Node* cur = parent->_left; Node* curright = cur->_right; Node* ppnode = parent->_parent; //改变parent parent->_left = curright; parent->_parent = cur; //改变curright if (curright != nullptr) { curright->_parent = parent; } //改变cur cur->_right = parent; cur->_parent = ppnode; //改变ppnode if (ppnode == nullptr) { _root = cur; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } } } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) { return true; } if (root->_color == RED) { return false; } int benchmark = 0; Node* cur = root; while (cur) { if (cur->_color == BLACK) { benchmark++; } cur = cur->_left; } return CheckColor(root, 0, benchmark); } bool CheckColor(Node* root, int blacknum, int benchmark) { //检查每条路径的黑色结点数量是否相等 if (root == nullptr) { if (blacknum != benchmark) { return false; } return true; } if (root->_color == BLACK) { blacknum++; } //检查颜色 if (root->_color == RED && root->_parent && root->_parent->_color == RED) { cout << root->_kv.first << ":" << "出现两个连续的红色结点" << endl; return false; } return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark); } int Height() { return Height(_root); } int Height(Node* root) { if (root == nullptr) { return 0; } int leftheight = Height(root->_left); int rightheight = Height(root->_right); return leftheight > rightheight ? 1 + leftheight : 1 + rightheight; } int Getrotatecount() { return _rotatecount; } private: Node* _root; int _rotatecount = 0; }; -
map代码
#pragma once #include"RBTree.h" namespace Snowar { template<class K,class V> class map { public: struct MapKeyOfT { const K& operator()(const pair<K,V>& kv) { return kv.first; } }; 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(); } V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.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代码
#pragma once
#include"RBTree.h"
namespace Snowar
{
template<class K>
class set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
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();
}
pair<iterator,bool> insert(const K& key)
{
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT > _t;
};
}