map + set 的模拟实现

什么是set？

set - C++ Reference (cplusplus.com)1、set 是按照一定顺序存储数据的容器，且数据都是唯一的，没有重复值

2、set 中的数据不可以修改，但是可以对它们进行插入和删除操作

3、若没有特殊声明，set 一般按照升序排序

4、set 是由二叉搜索树实现的

什么是map？

map - C++ Reference (cplusplus.com)

1、map 是按照一定顺序存储数据的容器，map里面的数据由键值对组成

2、在键值对中，键（key）用于排序和查找，key 在map 中是唯一的，没有重复值，且不可修改；值（mapped value）存储与 key 相关联的内容， 可以有重复值，可以修改

3、 map 支持下标访问，可以用 [key] 得到 mapped value 的值

4、map 由二叉搜索树实现

怎么用红黑树封装 map 和 set ？

红黑树结点的定义：

我们用模板 T 来区分 set 和 map，如果是 set，T 传的是 key，如果是 map，T 传的是 pair<K,V>，如果不用 class T ，而是实现 set 时用 class K 作为模板，实现 map 时，用 class K, class V 作为模板，会导致代码的冗余

enum Color
{//枚举，限定红黑树结点的颜色
	BLACK,
	RED
};
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _parent;
	T _data;
	Color _col;

	RBTreeNode(const T& data)
		:_right(nullptr)
		, _left(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)//初始化为红色，方便插入
	{ }
};

 红黑树迭代器的实现：

迭代器的前置 ++：

由于红黑树是中序遍历（左子树 根 右子树），我们以下面图示树为例，忽略树的颜色

中序遍历为：1  6  7  8  11  13  15  17  22  25  27 

假设迭代器名字为 it，设想下面几种情况：

1、假如 it 现在访问 1 结点，1 的右子树存在，由中序遍历，++it，就访问 1 的左子树的根（ 6 结点）

2、假设 it 现在访问 22 结点，22 的左右子树皆为空，故 ++it，访问 22 的父亲节点 25

3、假设 it 现在访问 7 结点，7 的左右子树皆为空，按照中序遍历，++it 应该访问 8 结点， 8 并不是  7 的父亲结点，而是 7 的祖先结点

由情况2、3可知，++it 并不是简单的访问 it 的父亲节点，而是要分情况讨论，我们假设 parent 是 it 当前结点的父亲结点：

1、当 it 访问 22 结点时，parent 为 25，it 是 parent 的左孩子。由中序遍历可知，25 还没有访问过且是我们下一个要访问的结点，所以 ++it ，访问 25 结点

2、 当 it 访问 7 结点时，parent 为 6，it 为 parent 的右孩子，根据中序遍历可知，6已经访问过了，我们迭代， it 为 6 结点，parent 为 1 结点，此时 it 依旧为 parent 的右孩子，且 1 已经访问过了，继续迭代，it 为 1 结点，parent 为 8 结点，此时 it 为 parent 的左子树，且 8 还没有访问过，故 8 就是我们想要的结点，++it 便访问 8 结点

总结：

1、当 it 为 parent 的左孩子时，++it 直接访问 parent 结点

2、当 it 为 parent 的右孩子时，一直迭代至 it 为 parent 的左孩子，此时 ++it 才可以访问 parent 结点

template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;

	Node* _node;

	RBTreeIterator(Node* node)
		:_node(node)
	{ }

	T& operator*()
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		if (_node->_right)
		{
			//当前结点的右子树不为空时，说明右子树还没有访问过，故访问右子树的最左节点
			Node* subLeft = _node->_right;
			//while (subLeft)，这样的判断方式，如果subLeft走到空了，想找它的父亲结点，会导致空指针的解引用
			while (subLeft->_left)
			{
				//当前结点的左子树不为空才迭代
				subLeft = subLeft->_left;
			}
			_node = subLeft;
		}
		else
		{
			//当前结点的右子树为空时
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				//根据中序遍历：左子树 根 右子树
				//若cur存在且cur在父亲节点的右边，说明parent已经访问过了，故迭代
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

红黑树的实现：

红黑树用了3个模板参数，class K 表示 map 和 set 中 key 的类型，class T 用于区分 set 和 map，如果是 set，T 传的是 key，如果是 map，T 传的是 pair<K,V> 

问题：我们已经用了 class T 来区分 set 和 map 了，可以不要 class K 吗？

不可以，调用 Find 来查找红黑树中的某个值时，

1、如果 Find 的参数类型为 K，则如果是 set，传的是 key，如果是 map，传的是键值对 pair<K,V> 中 K 的值

2、如果 Find 的参数类型为 T，则如果是 set，传的是 key，如果是 map，传的是键值对 pair<K,V> ，假设我们只知道键值对中键 key 的值，并不知道键值对中 mapped value 的值，那 调用 map 的 Find 时，传不了参数。

Node* Find(const K& key);

Node* Find(const T& key);

class KeyofT 是仿函数，那什么是仿函数？

仿函数(functor)，使一个类的使用看上去像一个函数。实现就是在类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

KeyofT：

KeyofT 用于取出 T 中的 key 值。因为 RBTreeNode 中的 _data 是 T 类型，假设我们需要比较结点中的值来找到我们要插入的位置，如果是 set，T 传的是 key，我们直接比较 key 的大小即可，如果是 map，T 传的是 pair<K,V>， 我们希望比较键值对中的 key ，此时写一个仿函数来满足我们的需求，来取出键值对中的 key。

迭代器 begin：

红黑树的最左结点作为迭代器的开始。

迭代器 end：

由于迭代器 end 是红黑树中序遍历的最后一个结点的下一个结点，而这个结点为空，故 end 也处理为空结点即可。

//K便于Find
//T用来区分是map还是set，map->K，set->pair<K,V>
//KeyofT：决定T取出来的对象是K，还是<K,V>.first
template<class K,class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;//不需要对外公开
public:
	typedef RBTreeIterator<T> iterator;//需要对外公开
	iterator begin()
	{
		//返回红黑树的最左结点
		Node* cur = _root;
		//while (cur->_left)
		while (cur && cur->_left)//根节点可能为空，故根节点不为空时才迭代
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		//返回红黑树的最右结点的下一个结点
		return iterator(nullptr);
	}
	void RotateL(Node* parent)
	{//左单旋，要转下来的结点作为parent
		Node* subR = parent->_right;//父亲节点的右
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)//避免空指针的解引用
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

		if (parent == _root)
		{//如果转下来的结点是根
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{//如果转下来的结点不是根
			if (ppnode->_left == parent)//parent在ppnode的左边
			{
				ppnode->_left = subR;
			}
			else//parent在ppnode的右边
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}
	void RotateR(Node* parent)
	{//右单旋，要转下来的结点作为parent
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		Node* ppnode = parent->_parent;//先设好ppnode，因为下一句会修改parent的父亲节点，导致ppnode不是我们预想的
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{//树为空
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		//树不为空
		KeyofT kot;
		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 false;//值相等，不插入
		}
		//插入
		cur = new Node(data);
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{//当parent不为空，且为红色时进入while
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{//父亲在爷爷的左
				Node* uncle = grandfather->_right;//叔叔在爷爷的右
				if (uncle && uncle->_col == RED)
				{
					//情况一：叔叔存在且为红
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//此时该子树的根grandfather的颜色为红，
					//grandfather的上半部分可能会出现连续的红色结点，故需要向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//叔叔不存在或叔叔存在且为黑
					if (cur == parent->_left)
					{
						//    g           p
						//  p   u -->  c    g
						//c                    u
						//g右旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;//该子树的根p 的颜色变为黑
					}
					else
					{
						//    g			c
						//  p   u --> p    g
						//   c              u
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;//该子树的根cur 的颜色变为黑
					}
					break;//因为子树的根都变为黑了，没有继续向上更新的必要了
					//因为再往上走，也不会出现破坏红黑树规则的情况（不会出现连续的红色结点）
				}
			}
			else
			{//父亲在爷爷的右
				Node* uncle = grandfather->_left;//叔叔在爷爷的左
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//   g				c
						//u		p -->     g		p
						//	  c			u
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					else
					{
						//	g			p
						//u   p -->	  g    c
						//		c	u
						//左单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
private:
	Node* _root = nullptr;
};

红黑树模拟实现 set：

    template<class K>//set只需要传K类型
	class set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{//给K类型的变量key，直接返回key
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetKeyofT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		//const K 避免对结点的值进行更改
		RBTree<K, const K, SetKeyofT> _t;
	};

红黑树模拟实现 map：

    template<class K,class V>//map传K、V类型
	class map
	{
		struct MapKeyofT
		{
			const K& operator()(const pair<K,V>& key)
			{
				return key.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		bool insert(const pair<K, V>& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyofT> _t;
	};