C++使用一棵红黑树同时封装出map和set实例代码

template <class T>
struct RBTreenode
{
	T _data;// 我们不清楚红黑树结点里面存的是什么,可能是string，内置类型，又或是键值对，取决于map和set里面存的是什么
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	enum color _col;

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

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;//pair键值对的关键吗是常量
	};

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 T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;// T代表红黑树结点的存储内容的类型

	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.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<const K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};

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

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

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

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

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

	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>
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	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
		{
			return _t.begin();
			//普通对象调用的begin()返回的是普通迭代器，而set上层要求返回的都是const迭代器，发生类型不兼容问题
			//库是怎么解决的呢？
			// 
			//set的begin和end没有提供两个版本，仅仅只提供了const版本，强制性要求set的普通对象和const对象底层都去调用
			//红黑树const版本的begin()和end()
			//注意：如果是普通对象发生调用const函数，那么在const函数内部，普通对象也会被当作const对象进行处理。
			//      所以底层调用的红黑树的begin，自动就是const版本的begin()
		}
		iterator end()//const
		{
			return _t.end();
		}

template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;// node里面存的是键值对或key类型变量
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
	
	Ref operator*()
	{
		return _node->_data;// 如果是set就是key，如果是map就是键值对,这里返回引用
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
}


template <class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;// T代表红黑树结点的存储内容的类型
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()//给普通对象调用
	{
		Node* left = _root;
		while (left && left->_left)// 这棵树有可能是空树，若不为空树找到左树最小结点
		{
			left = left->_left;
		}

		return iterator(left);// 不能瞎用引用啊，这里的迭代器对象出了begin()作用域就销毁了，引用就出大事了！
	}
	const_iterator begin()const//给const对象调用
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		return const_iterator(left);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator end()const
	{
		return const_iterator(nullptr);
	}

template <class K, class V>
class map
{
public:
	// 1.取未实例化类模板里面的类型时，无论是内部类还是内嵌类型，都需要加typename，告诉编译器类模板后面的东西是类型
	// 因为类模板里面还有可能是静态成员，静态成员也是可以通过类名+域访问符进行访问的，编译器无法确定是类型还是静态成员
	// 2.图纸里面怎么能直接取东西呢？肯定是需要对这样的情况进行特殊处理的
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K,V>>::iterator iterator;
	// 编译器不会编译模板，编译的都是模板实例化之后的代码，所以iterator是静态成员还是内嵌类型，编译器都确定不了。
	//typename就是先告诉一下编译器，这里是类型，先不要取这个类型，等到模板实例化好之后你再去取这个类型。
	//图纸里面有水果，你先不要去拿这个水果，等到按照图纸实例化为苹果树之后，你再取这个苹果
	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);
}

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

int main()
{
	list<int> lt;
	vector<int> v;
	list<int>::const_iterator clit = lt.begin();
	vector<int>::const_iterator cvit = v.begin();

	return 0;
}

template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;// node里面存的是键值对或key类型变量
	typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
	typedef __RBTreeIterator<T, T&, T*> iterator;
	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	//如果是const迭代器调用，这里是构造。如果是普通迭代器调用，这里是拷贝构造。
	__RBTreeIterator(const iterator& it)
		:_node(it._node)
	{}

template <class K>	
class set
{
public:
	pair<iterator, bool> insert(const K& key)//这里的迭代器被替换为const_iterator
	{
		//return _t.Insert(key);
		//Insert返回的是普通迭代器，普通迭代器不能直接拷贝构造给const迭代器，类型不同，但我们可以自己写拷贝构造。
		//这里肯定不能再使用const修饰来进行解决了，因为insert功能就是要写嘛，又不具有读的功能，实现const版本干嘛？？？
	
		pair<typename RBTree<K, K, SetKeyOfT<K>>::iterator, bool> ret = _t.Insert(key);
		//必须用红黑树底层的普通迭代器类型接收Insert返回的键值对，因为set的所有迭代器都是底层const迭代器typedef出来的
	
		return pair<iterator, bool>(ret.first, ret.second);
		//这里在利用Insert的返回值重新拷贝构造一个键值对，用普通迭代器构造const迭代器，然后返回具有const迭代器的键值对
	
	
		//********set这个地方即使自己写了拷贝构造，在返回的时候也依旧不能直接强转，这谁能想到啊？？？？？？？？？？？？
	}
private:
	RBTree<K, K, SetKeyOfT<K>> _t;
};