用红黑树封装实现map和set

enum Color {RED,BLACK};
template<class T>//节点存储对象类型，可能是键值对也有可能是key
class RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;

	RBTreeNode(const T& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template<class K>
class set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:

private:
	RBTree<K, K, SetKeyOfT> _t;
};

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:

private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:

private:
	Node* _root = nullptr;
};

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;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}

			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		//右子树 根 左子树
		if (_node->_left)
		{
			//找左子树的最右结点，其实就是次大的结点
			_node = _node->_left;
			while (_node->_right)
			{
				_node = _node->_right;
			}
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;

			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//如果cur是parent的右，则直接让_node指向到parent即可
			_node = parent;
		}

		return *this;//返回迭代器对象
	}
	bool operator!=(const Self& it)const//const修饰表示在该成员函数内部，不能修改对象的任何成员变量
	{
		return this->_node != it._node;
	}

	bool operator==(const Self& it)const//const对象和非const对象都可以调用
	{
		return this->_node == it._node;
	}
};

template <class K>	
	class set
	{
	public:
		//set表层的普通迭代器底层用的依旧是const_iterator，就是不允许对set的迭代器指向内容进行修改
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
		iterator begin()  const   //为了防止权限的放大，我们直接使用const，如果对象是const，调用const的begin，不是const也调用const的begin和end
		{
			return _t.begin();
		}
		iterator end()  const
		{
			return _t.end();
		}

template <class K, class V>
class map
{
public:

	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;

	//map的迭代器需要提供两个版本
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator begin()const
	{
		return _t.begin();
	}
	const_iterator end()const
	{
		return _t.end();
	}
private:
	RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

pair<iterator, bool> Insert(const T& data)
//红黑树必须通过结点里面存储的key来进行比较才可以插入结点，所以出现了kot仿函数对象
{
	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}

	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);
		}
	}
	cur = new Node(data);
	Node* curit = cur;//保存一下cur的位置否则下面旋转调色过程中，cur有可能被改了
	if (kot(parent->_data) > kot(data))
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left)
		{
			Node* uncle = grandparent->_right;

			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_left)
			{
				RotateR(grandparent);
				grandparent->_col = RED;
				parent->_col = BLACK;
				break;
			}
			else if (cur == parent->_right)
			{
				RotateL(parent);
				RotateR(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
		else
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)
			{
				grandparent->_col = RED;
				uncle->_col = parent->_col = BLACK;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_right)
			{
				RotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
				break;
			}

			else if (cur == parent->_left)
			{
				RotateR(parent);
				RotateL(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
	}
	_root->_col = BLACK;
	
	return make_pair(iterator(curit), true);
}

template <class K, class V>
class map
{
public:
	pair<iterator, bool> insert(const pair<const 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<K,V>> _t;
};