使用一份红黑树封装set和map

set/map简介

我们所熟知的vector、list、deque被称为序列是容器；set和map是c++中的关联式容器，他们都是用来储存数据的。
只不过关联式容器里面存储的不是单个元素，而是一个<key, value>键值对，这种键值对在数据检索时，效率更高。

键值对：用来表示具有一一对应关系的一种结构，该结构中只包含变量key和value，key代表键值，value表示与key对应的信息。比如英汉互译的词典<apple， 苹果> 就是一个键值对。

set特性

• set是按照一定次序存储元素的容器。
• 在set中，存储的是<key, key>这样的键值对，并且每个key必须是唯一的。set中的元素不能在容器中修改。但是可以从容器中，插入或删除他们
• 在内部，set中的元素总是按照一定的顺序排列
• set插入时，只需要插入value即可，不需要构造键值对
• set底层使用红黑树实现

map特性

• map是按照特定顺序存储的容器
• map中存储的是<key, value>这样的键值对。并且每个key必须唯一。但是value值可以修改。也可以从容器中，插入或删除他们
• 在内部，map是按照key的顺序排列的
• map支持下标访问，且非常灵活。
• map插入时，需要插入一个<key, value>键值对
• map底层是用红黑树实现的

红黑树的接口

修改步骤：

1. 将类模板修改为<K, T>， T为存入数据
2. 增加一个仿函数的模板选项，用于获取数据的key
3. 实现迭代器***
4. 迭代器的单参构造（可以实现隐式转换）
5. Insert函数，返回值的修改
6. 迭代器++的逻辑
7. 迭代器的typedef也要好好学学

enum class Color   //结点颜色
	{
		RED,
		BLACK
	};


	//1. 添加了T模板参数
	template<class T>
	struct RBTreeNode
	{

		//红黑树结点，默认红色
		RBTreeNode(const T& data)
			:_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_data(data)
			,_color(Color::RED)
		{}

		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		T _data;
		Color _color;
	};

	//3. 迭代器实现(数据，数据的引用，数据的指针)
	template<class T, class Ref, class Ptr>
	struct RBTreeIterator
	{
		typedef RBTreeNode<T> Node;
		typedef RBTreeIterator<T, Ref, Ptr> Self;
		Node* _node;   //迭代器的成员变量

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



		// *、typedef __RBTreeIterator<T, T&, T*> itertaor;  拷贝构造
		// **、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
		//  支持普通迭代器构造const迭代器的构造函数
		RBTreeIterator(const RBTreeIterator<T, T&, T*>& it)
		{
			_node = it._node;
		}
		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		//左根右
		Self& operator++()     //左根右
		{
			//1.右不为空，下一个就是右子树的最左结点
			if (_node->_right)
			{
				Node* subLeft = _node->_right;
				while (subLeft->_left)
				{
					subLeft = subLeft->_left;
				}

				_node = subLeft;
			}
			else
			{
				//2.右为空，沿着到根的路径，找孩子是父亲左的那个祖先
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent && cur == parent->_right)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_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 && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}

			return *this;
		}

	};


	// 2. 注意添加了KeyOfT这个仿函数接口,用来把T里面的key给拿出来
	template<class K, class T, class KeyOfT>
	class RBTree
	{
	private:
		typedef RBTreeNode<T> Node;
	public:

		//析构函数
		~RBTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}

	public:
		typedef RBTreeIterator<T, T&, T*> iterator;
		typedef RBTreeIterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}

			return iterator(cur);
		}

		iterator end()
		{
			return iterator(nullptr);
		}


		const_iterator begin() const
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}

			return const_iterator(cur);
		}

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


	public:

		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)
		{
			if (_root == nullptr)
			{
				_root = new Node(data);
				_root->_color = Color::BLACK;   //根结点就置为黑色
				return make_pair(iterator(_root), true);
			}
			KeyOfT kot; //仿函数实例化

			//1.找到插入位置
			Node* cur = _root;
			Node* parent = nullptr;
			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);
				}
			}

			//2.找到了直接插入
			Node* newNode = new Node(data);
			cur = newNode;
			if (kot(parent->_data) > kot(data))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;  //记得互联

			//3.检查是否满足红黑树，若满足直接退出
			//不满足，需要调整红黑树
			while(parent && parent->_color == Color::RED)
			{
				//爷爷结点一定存在，因为parent为红，爷爷结点一定为黑！
				Node* grandfather = parent->_parent;

				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					//情况一： cur 为红，p为红，g为黑， u存在且为红
					if (uncle && uncle->_color == Color::RED)  // 只需要叔父爷变色即可
					{
						parent->_color = Color::BLACK;
						grandfather->_color = Color::RED;
						uncle->_color = Color::BLACK;        //子树调整完成

						//把爷爷当作新插入结点，继续调整
						cur = grandfather;
						parent = cur->_parent;
					}
					else   //2.u存在且为黑   3.u不存在    旋转+变色
					{
						//2    g
						//   p    u
						// c
						if (cur == parent->_left)   //父亲爷爷变色
						{
							_RotateR(grandfather);   //以g为轴点右单旋
							parent->_color = Color::BLACK;
							grandfather->_color = Color::RED;
						}
						else    //cur是p的右孩子
						{
							//    g
							//  p    u
							//    c       叔父爷变色
							_RotateL(parent);
							_RotateR(grandfather);
							grandfather->_color = Color::RED;
							cur->_color = Color::BLACK;

						}

						break;
					}
				}
				else   //parent = grandfather->_right
				{
					//   g
					// u    p
					//        c
					Node* uncle = grandfather->_left;
					if (uncle && uncle->_color == Color::RED)   //情况1  u存在且为红
					{
						uncle->_color = Color::BLACK;
						parent->_color = Color::BLACK;
						grandfather->_color = Color::RED;

						//继续往上调整
						cur = grandfather;
						parent = cur->_parent;
						
					}
					else   //u存在为黑    u不存在
					{
						//    g
						//  u   p
						//        c
						if (cur == parent->_right)
						{
							//左单旋
							_RotateL(grandfather);
							parent->_color = Color::BLACK;
							grandfather->_color = Color::RED;
							
						}
						else
						{
							//    g
							//  u    p
							//      c
							_RotateR(parent);
							_RotateL(grandfather);
							grandfather->_color = Color::RED;
							cur->_color = Color::BLACK;
						}


						break;

					}
				}
				
			}
			_root->_color = Color::BLACK;
			return make_pair(iterator(newNode), true);
		}



	private:
		void _Destroy(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
		}

		void _RotateR(Node* parent)
		{
			//右单旋，儿子上位变父亲，父亲被挤到右边
			Node* pParent = parent->_parent;  //爷爷
			Node* childL = parent->_left;   //左孩子

			parent->_left = childL->_right;
			if (childL->_right)
			{
				childL->_right->_parent = parent;   //子指向父
			}
			childL->_right = parent;
			parent->_parent = childL;  //子指向父

			//最后将chldL指向pParent
			childL->_parent = pParent;
			if (pParent == nullptr)  // childL 变成了根
			{
				_root = childL;
				childL->_parent = nullptr;
			}
			else
			{
				if (pParent->_left == parent)
				{
					pParent->_left = childL;
				}
				else
				{
					pParent->_right = childL;
				}
			}

		}

		//左单旋
		void _RotateL(Node* parent)
		{
			Node* childR = parent->_right;   //存右孩子

			parent->_right = childR->_left;    //右孩子的左孩子互连父亲
			if (childR->_left)
			{
				childR->_left->_parent = parent;
			}

			childR->_left = parent;   //parent和childR互联
			Node* pparent = parent->_parent;   //暂存爷爷
			parent->_parent = childR;

			//爷爷和childR互联
			childR->_parent = pparent;
			if (pparent == nullptr)   //爷爷为空，就是根
			{
				_root = childR;
				childR->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent)
				{
					pparent->_left = childR;
				}
				else
				{
					pparent->_right = childR;
				}
			}

		}

	private:
		Node* _root=nullptr;   //根

	};

set的封装

注意问题：

1. 要写一个仿函数，只有自己知道自己的数据类型
2. 因为set不可更改value，所以要使用const迭代器，注意typedef的都是const命名的。
3. 封装的成员变量直接是红黑树。

	template<class K>
	class set
	{
		//我自己直到数据类型是什么样的，仿函数我来写
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

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

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

	public:
		pair<iterator, bool> Insert(const K& key)
		{
			return _t.Insert(key);
		}


	private:
		RBTree<K, K, SetKeyOfT> _t;    //定义为红黑树
	};

map的封装

封装步骤：

1. 模板参数不需要加仿函数！！
2. 定义仿函数时，注意此参数设置应该具体
3. 迭代器只需实现一份即可
4. 注意[]的实现注意事项

	//template<class K, class T, class KeyOfT>   自己写的，写的不好
	template<class K, class V>
	class map
	{
		
		struct MapKeyOfT
		{
			const K& operator()(const pair<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();
		}


		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.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;
	};

总结

map和set的封装，重点是封装的思想。多学学这里代码的套路。