C++红黑树封装map和set

一、map和set的value兼容

set里面的key就是value，而map里面的value是pair<key,value>；在封装map和set时，要使用同一个红黑树的类模板去封装，也就是说，红黑树的类模板只有一份；但是两者的value不同，首先对于map来说，传key和value需要两个模板参数，为了兼容map，要求set也传两个模板参数，那么set的value也传key；此时就能保证共用一个红黑树类模板了；

但是由于两者数据的不同，数据比较的逻辑也不同；对于set直接比较，对于map数据类型是pair类型的，库中的pair比较是先比较first，first小那么整个pair就小，若是first相同，就比较second，second小的pair就小；但是对于map要求只用key来比较，也就是pair里面的first，那么就不能和set使用相同的比较逻辑了；这里使用到仿函数：需要第三个模板参数，传的是set和map各自的仿函数，这里的set写仿函数也是因为共用一个类模板，去兼容map的；对于set直接返回key，对于map重载()运算符时，返回pair里面的first，那么在进行数据比较时，使用仿函数所在的类实例化出来的对象加上()，去取数据里面作为比较的部分；

二、迭代器

map和set的使用的是红黑树的类模板，那么在写迭代器时，实例化的应该也是红黑树的类模板；红黑树是节点构成的，那么这里的迭代器和list里面实现的逻辑基本相同，唯一不同的就是map和set走的是中序，不想list那么++、--都是单纯的向后向前。这里的++和--要看具体情况；

先看++：中序走的是左根右。无论是哪个节点++时，都把它看作根节点，去右子树找++后的结果；当右子树不为空时，找右子树的最左节点（第一种情况）；当右子树为空时，若这个节点是父节点的左子树，那么说明父节点的左子树访问完毕，开始访问根也就是这个父节点（第二种），若是这个节点是父节点的右子树，那么说明父节点所在的树都访问完毕，向上找需要访问的，找到当前节点是其父节点的左节点时，停止向上寻找，此时和第二种情况相同，当找到的父节点是空节点时，那么说明还没有向上寻找时的节点是最右节点，也就是说父节点找到空才停止寻找的情况就是整棵树都访问完毕，此时++让迭代器里面的节点走到end(）,end()用指向的节点是nullptr（情况三）

--:基本思路和++相反（左根右）;当end()--时要特殊处理，因为此时的节点为空，不能进入循环进行判断；处理办法就是：利用根节点向下找到整棵树的最右节点；

红黑树的Begin是中序的第一个，也就是整棵树的最左节点；End就用nullptr代表.

三、map里面的[]重载

将Insert的返回值改成pair<iterator,bool>类型的；这个类型含义在文章map的使用里面右说明；

四、具体代码：

一、set头文件：

#pragma once
#include"RBTree.h"


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

		//要加typedef，因为从类域里面可以取类型名，也可以取静态成员变量
		//未实例化时，编译器不知道取得到底是说明，加上typedef表示取的是类型
		//K前面加上const和成员变量类型保持一致
		typedef typename RBTree<K, const K, setKeyofT>::Iterator iterator;
		typedef typename RBTree<K, const K, setKeyofT>::ConstIterator const_iterator;
		pair<iterator, bool> insert(const K& data = K())
		{
			return _t.Insert(data);
		}
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator cbegin()const
		{
			return _t.cBegin();
		}
		const_iterator cend()const
		{
			return _t.cEnd();
		}
	private:
		RBTree<K, const K, setKeyofT> _t;
	};
}

二、map头文件：

#pragma once
#include"RBTree.h"

namespace MAP
{
	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;
		typedef typename RBTree<K, pair<const K,V>, mapKeyofT>::ConstIterator const_iterator;
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator cbegin()const
		{
			return _t.cBegin();
		}
		const_iterator cend()const
		{
			return _t.cEnd();
		}
		//[]重载
		V& operator[](const K& key)
		{
			//使用V()不影响，因为在使用[]时会改变V也就是value，最终的value是我们自己赋值的
			pair<iterator, bool> ret = insert({key, V()});
			return ret.first->second;//ret.first->表示data的指针，second就是value 
		}
	private:
		RBTree<K, pair<const K,V>, mapKeyofT> _t;
	};
}

三、RBTree头文件：

#pragma once
#include<iostream>
#include <utility>
using namespace std;


enum Color
{
	RED,
	BLACK
};

template<class T>//T表示set或者是mpa的数据类型
struct RBTreeNode
{
	Color _col;
	T _data;
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;

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

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	typedef RBTreeNode<T> Node;
	//构造函数
	RBTreeIterator( Node* node,Node* root)
		:_node(node)
		,_root(root)
	{}
	Self operator++()
	{
		//右不为空，访问右子树的最左节点
		if (_node && _node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;//最后改变_node，因为迭代器实际上就是节点的指针
		}
		//右为空，说明这颗子树访问完了，向上找根节点
		//找的根节点：当前节点是这个根节点的左节点（说明左子树完，开始访问根节点）
		else if (_node && !_node->_right)
		{
			Node* cur = _node, * parent = cur->_parent;
			while (parent && parent->_right == cur)//parent为空，说明减一次就到了end()
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	//--和++相反，把当前节点看作基准，减一下就是找左子树(右、根、左)
	Self operator--()
	{
		if (_node && _node->_left)
		{
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		//左为空，就要去找当前节点是父节点的右子树的节点
		else if (_node && !_node->_left)
		{
			Node* cur = _node, * parent = _node->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		// end()可以--；当_node 为空时也就是当前迭代器指向的是end()，特殊处理
		//end()--,找到的是整棵树的最右节点
		else if (!_node)
		{
			Node* cur = _root;//这就是为什么迭代器的成员变量要加一个根节点指针
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		return *this;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& it)const
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)const
	{
		return _node != it._node;
	}
private:
	Node* _node;
	Node* _root;
};
template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//实现const迭代器和迭代器共用一个类模板
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
	Iterator Begin()
	{
		//中序的第一个，也就是树的最左节点
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return { cur, _root };
	}
	Iterator End()
	{
		return { nullptr,_root };
	}
	ConstIterator cBegin()const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return { cur,_root };
	}
	ConstIterator cEnd()const
	{
		return { nullptr,_root };
	}
	pair<Iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return  { Iterator(_root,_root),true };
		}
		KeyofT kot;//仿函数所在的类实现的对象
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(data)< kot(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) > kot(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{//插入失败，已经有这个数据
				return { Iterator(cur,_root),false };
			}
		}
		cur = new Node(data);
		//后面返回值不能用cur，因为cur在调整平衡因子时已经变化，不再是开始插入的那个值，所以要提前记录
		Node* newnode = cur;
		if (kot(data) < kot(parent->_data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		cur->_col = RED;

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

			}
		}
		_root->_col = BLACK;
		return {  Iterator(newnode,_root),true };
	}
	Node* Find(const K& k)
	{
		Node* cur = _root;
		while (cur)
		{
			if (k < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if (k > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
	}
	void Print()
	{
		_Print(_root);
		cout << endl;
	}
	//析构函数
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
private:
	Node* _root = nullptr;
	//递归删除节点
	void Destroy(Node* root)
	{
		if (!root) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
	//右单旋
	void RotateR(Node* sub)
	{
		Node* subl = sub->_left;
		Node* sublr = subl->_right;

		sub->_left = sublr;
		if (sublr)
			sublr->_parent = sub;

		Node* sub_P = sub->_parent;
		subl->_right = sub;
		sub->_parent = subl;

		if (!sub_P)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (sub_P->_left == sub)
			{
				sub_P->_left = subl;
			}
			else
			{
				sub_P->_right = subl;
			}
			subl->_parent = sub_P;
		}
	}
	//左单旋
	void RotateL(Node* sub)
	{
		Node* subr = sub->_right;
		Node* subrl = subr->_left;

		sub->_right = subrl;
		if (subrl)
		{
			subrl->_parent = sub;
		}

		Node* sub_P = sub->_parent;
		subr->_left = sub;
		sub->_parent = subr;

		if (!sub_P)
		{
			_root = subr;
			subr->_parent = nullptr;
		}
		else
		{
			if (sub_P->_left == sub)
			{
				sub_P->_left = subr;
			}
			else
			{
				sub_P->_right = subr;
			}
			subr->_parent = sub_P;
		}
	}
	void _Print(Node* root)
	{
		if (!root)
		{
			return;
		}
		_Print(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Print(root->_right);
	}
};