【C++】map和set的模拟实现

map和set的模拟实现

• 插入模拟实现
• 正向迭代器模拟实现+插入完整实现
• map的[ ]接口模拟实现
• 正向迭代器完整代码+反向迭代器模拟实现

喜欢的点赞，收藏，关注一下把！

在前面几篇C++的博客，讲过了二叉搜索树，AVL树，红黑树。
今天我们就用红黑树模拟实现map和set。

那现在就有一个问题了。给你一颗红黑树你该如果用它模拟实现map和set呢？但是map是KV模型的，set是K模型的。难道分别给一颗红黑树照着改吗？

如果没有思路，我们不妨看一看库里是怎么实现的。

上图分别是我们的map和set，主要看它们传给红黑树第二个模板参数都是value_type，但是map的value_type是pair<const Key，T>，而set的value_type是Key。
我们都知道同一份模板，因为给的参数不同可以示例化不同的类。

所以第二个模板参数传的参数不同，那关于KV模型与K模型的问题就可以解决了，因此map和set底层也可以使用同一份红黑树类模板。

我们再看一个红黑树的库就知道它为什么这样给参数了。

红黑树第二个模板参数决定到底是map(KV模型)，set(K模型)。

那为什么还要传第一个参数Key呢？

这里主要因为find的存在，站在红黑树的角度，它不知道你给它传的到底是什么，就比如insert，上层传什么我就插入什么样值的节点，同样find上层传什么就按什么类型的值去查找。但是不管是K模型，还是KV模型，即使KV模型可以改变值，但是它改的是V而不是K。因此都可以用K去查找。

下面我们就用红黑树模拟实现map和set

enum Coloer
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Coloer _col;

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

template<class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:	
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}


		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(data);
		cur->_col = RED;
		if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//调整
		while (parent && parent->_col == RED)
		{
			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;

					cur = grandfather;
					//如果是整树，就可能发生野指针，
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)//情况二
					{
						RotaleR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三
					{
						RotaleL(parent);
						RotaleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotaleL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotaleR(parent);
						RotaleL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

		}
		_root->_col = BLACK;
		return true;
	}

	void RotaleL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

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

		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

	void RotaleR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

private:
	Node* _root = nullptr;
};

为了方便，传参的时候没有像库那样给。

//Map.h
namespace bit
{
	template<class K,class V>
	class map
	{
	private:
		RBTree<K, pair<const K, V>> _t;
	};
}
//Set.h
namespace bit
{
	template<class K>
	class set
	{
	private:
		RBTree<K, K> _t;
	};
}

下面我们来实现插入。

插入模拟实现

但是实现之前，有一个问题，插入是有比较的。
map给的是pair，set给的是key，而pair的比较规则是first不小于，就比较second（first是pair第一个参数的值,second是第二个参数的值），但是我们只想比较key。那该怎么办呢？

那我们就想办法改变一下，让map和set只比较key。这里当然不是重写一个pair的比较，而是给map和set分别写一个仿函数，也就是给红黑树传第三个模板参数。

//map.h
	template<class K,class V>
	class map
	{
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	private:
		RBTree<K, pair<const K, V>,MapKeyofT> _t;
	};
//set.h
	template<class K>
	class set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		RBTree<K, K,SetKeyofT> _t;
	};
	
//RBTree.h
bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		KeyofT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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 false;
			}
		}

		cur = new Node(data);
		cur->_col = RED;
		if (kot(cur->_data) < kot(parent->_data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//调整
		while (parent && parent->_col == RED)
		{
			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;

					cur = grandfather;
					//如果是整树，就可能发生野指针，
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)//情况二
					{
						RotaleR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三
					{
						RotaleL(parent);
						RotaleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotaleL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotaleR(parent);
						RotaleL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

		}
		_root->_col = BLACK;
		return true;
	}

红黑树的插入实现好了，map和set调用一下就可以了

//map.h
template<class K,class V>
	class map
	{
		struct MapKeyofT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
	};
	public:
		bool Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

	private:
		RBTree<K, pair<const K, V>,MapKeyofT> _t;
	};
	
//set.h
template<class K>
	class set
	{
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool Insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, K,SetKeyofT> _t;
	};

插入暂时先讲到这里，这里还有一些问题，接下来学完迭代器在回来解决。

正向迭代器模拟实现+插入完整实现

先把红黑树迭代器实现好，然后map和set再去调用。

红黑树的迭代器和list迭代器实现方法是一样的，原生指针并不能解决问题，因此我们把它封装+运算符重载实现需要的迭代器。

这里补充说明一点，我们红黑树的结构与库里给的不一样。
库里红黑树有一个头结点，它的左指针指向最左边，右指针指向最右边。
这是因为，迭代器是一个中序，库中这样的设计很容易找到迭代器开始的位置和结束的位置。

而我们的红黑树没有头结点。就是正常的一颗红黑树。接下来迭代器的实现都是按照下图结构实现的。

鉴于有list迭代器模拟实现的底子，我们先实现一个简易的迭代器，然后再一步步加。

template<class T>
class _RBTreeIterator
{
public:
	typedef RBTreeNode<T> Node;
	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;
	}

};

template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef _RBTreeIterator<T> iterator;
	/。。。。。
}

目前我们迭代器还差一个++运算符重载，就可以使用了。
那红黑树应该如何实现这个++呢？

迭代器走的是中序，按照下图也就是说第一个位置应该是5。

按照中序左子树，根，右子树的走法，当我们第一个位置是5的时候。左子树和根都已经走过了。接下来就该右子树了。所以我们现在面临的就是右子树存在和空的两种情况。

右子树不为空， it在8的位置。

下一个位置就是10的位置。也就是下一个右子树最左节点。

右为空 it在7的位置

也就是说5，6都访问完了，下一个位置该访问8了。能直接写访问祖先吗？
那如果7下面还有一个位置，那不就是访问祖先的祖先了。所以不能就访问祖先。

可以这样想。左子树访问完了，该访问根了，而左子树根节点是这个树根的左孩子。只要满足这个条件，我们就找到下一个要访问的位置了。

1.右不为空，找下一个右子树最左节点
2.右为空，去找祖先（孩子是父亲左的那个祖先）

template<class T>
class _RBTreeIterator
{
public:
	typedef RBTreeNode<T> Node;
	Node* _node;
	typedef _RBTreeIterator<T> Self;

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

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

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

	Self& operator++()
	{
		//1.右不为空，找下一个右子树最左节点
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;//_node指向它
		}
		else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//走到最后parent为空
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

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

我们再把begin和end实现一下。
迭代器是一个中序，第一个有效数据位置就是5了，最后一个有效位置的下一个位置那就是nullptr。

template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef _RBTreeIterator<T> iterator;

public:

	iterator begin()
	{
		Node* left = _root->_left;
		while (left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	
	iterator end()
	{
		return iterator(nullptr);
	}
/
}

接下来给map和set加上迭代器

//map.h
	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;
		
		bool Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

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

这里可能有些疑问加typename干什么，因为分不清
RBTree<K, pair<const K, V>, MapKeyofT>::iterator 是静态变量还是里面定义的类型。所以在前面加typename告诉编译器这是一个类型，等实例化之后再去取。

凡是没有实例化的类模板，编译器区分不清楚RBTree<K, pair<const K, V>, MapKeyofT>::iterator中iterator到底是静态变量还是类型，因为静态变量可以这样用，类型也可以这样用，加个typename告诉编译器这个类模板虽然没有实例化，这个是一个类型，你先让我过，等到类模板实例化了再去取。

//map.h
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;

		bool Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

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

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


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


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

		bool Insert(const K& key)
		{
			return _t.Insert(key);
		}

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

		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, K,SetKeyofT> _t;
	};

迭代器目前没有问题，但真的就没有问题吗？
看看我们的set迭代器

普通迭代器当然可以修改值，但在set和map这里还能随意修改Key值吗，随意改之后还能保证是底层红黑树吗？

我们先看看库里是set迭代器怎么实现的。

库里set普通迭代器和const迭代器用的都是红黑树的const迭代器。
所以我们把红黑树的迭代器补充完整。

template<class T,class Ref,class Ptr>
class _RBTreeIterator
{
public:
	typedef RBTreeNode<T> Node;
	Node* _node;
	typedef _RBTreeIterator<T,Ref,Ptr> Self;

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

	Ref operator*()
	{
		return _node->_data;
	}

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

	Self& operator++()
	{
		//1.右不为空，找下一个右子树最左节点
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;//_node指向它
		}
		else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//走到最后parent为空
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

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

template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef _RBTreeIterator<T,T&,T*> iterator;
	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;


public:

	iterator begin()
	{
		Node* left = _root->_left;
		while (left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	
	iterator end()
	{
		return iterator(nullptr);
	}

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

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

再把set的迭代器改一下

	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;

		
		bool Insert(const K& key)
		{
			return _t.Insert(key);
		}
		
		//那这里该如何调用红黑树的const_iterator
		//因为_t.begin();调用的红黑树的iterator
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, K,SetKeyofT> _t;
	};

我们还是参考库，发现它加个const，为什么这样就行了呢？

因为权限可以缩小。所以不管是普通对象和const对象都可以调用。
所以set的正向迭代器，普通的或者的const都用着两个函数就可以了，不用单独在为const迭代器重写一个了。

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;


		bool Insert(const K& key)
		{
			return _t.Insert(key);
		}

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

		iterator end() const
		{
			return _t.end();
		}
	private:
		RBTree<K, K,SetKeyofT> _t;
	};

这样不管set是普通还是cosnt迭代器，都不能修改Key值。

那map呢，也需要这样写迭代器吗？其实不用，map迭代器还和以往一样的写。

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;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;

		bool Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

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

那map就不担心修改Key吗，请看上面pair<const K, V>，第一个参数我们就给了const ，所以你根本无法修改。 并且你只能修改V。同样这也符合我们的想法。

迭代器先讲到这里，还有一个反向迭代器最下面在实现。

我们接着把插入完善一下。

库里insert返回类型是pair，而我们自己写的只有bool。

insert返回类型的意思是。当成功插入时iterator指向最新插入的节点，bool设为true。插入失败时也就是插入相同的key，iterator指向已经插入过的节点。bool设为false。

//RBTree.h
pair<iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		KeyofT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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);
			}
		}

		//这里要重写申请一个指针，记录当前插入节点
		//否则下面调整情况uncle是红色节点,cur会变
		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED;
		if (kot(cur->_data) < kot(parent->_data))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//调整
		while (parent && parent->_col == RED)
		{
			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;

					cur = grandfather;
					//如果是整树，就可能发生野指针，
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)//情况二
					{
						RotaleR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三
					{
						RotaleL(parent);
						RotaleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotaleL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotaleR(parent);
						RotaleL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode),true);
	}

map和set也改一下

//map.h
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;

		pair<iterator,bool> Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}
//set.h
		typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;

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

但是改完就出事了。

set的插入出现了问题，返回时类型不匹配。而map没问题。
这是因为，set的iterator用的是红黑树的const_iterator，而_t.Insert(key)，调用底层的红黑树插入还用的是iterator所导致类型不匹配的问题。
至于map的insert没问题，那是红黑树的迭代器怎么用，它就怎么样的。

对于map和set出现这样的问题。这是因为它们底层用的是同一个黑红树模板，我们遇到这个问题，库肯定也遇到这个问题。

参考库怎么解决的

库里并不是还像刚才遇到迭代器问题那样，在后面加个const。
而是用同类型的iterator接收insert返回的值，然后在返回时，匿名构造一个pair。而这个pair里所用的就是const_iterator。这样就解决了返回时类型不匹配的问题。

那它是如何将iterator构造成const_iterator
看看库里怎么做到的。

乍看这是一个拷贝构造。它真的是吗？我们也写一个拷贝构造看看。

但还是有问题。那它到底是什么？如何将普通迭代器转换成const迭代器。

好了不卖关子，这个关键还是在typedef出一个iterator

我们传第一个参数是T给的Value，这里就相当于是<T,T&,T*>，
而下面这个函数，当你用的是同一类型的迭代器这是拷贝构造。当你用的是不同类型的迭代器，这里相对于构造。

这里就是调用那个构造函数把iterator构造成const_iterator。
把set的插入修改一下。再把刚才的那个函数填上，就解决返回时类型不匹配的问题

//set.h
		pair<iterator,bool> Insert(const K& key)
		{
			pair<typename RBTree<K, K, SetKeyofT>::iterator, bool> ret = _t.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
		}

接下来我们把map中的 [ ]接口实现一下。

map的[ ]接口模拟实现

我们在使用map的[ ]接口方便的很，既可以插入，修改，也可以查找(存在才能查否则就是插入)。那实现一下把。这一部分在【C++】map和set的使用及注意事项的map接口使用有详细结束。这里就只把它实现出来。

V& operator[](const K& key)
{
	//插入key，返回V，然后就可以修改V了
	pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
	return ret.first->second;
}

正向迭代器完整代码+反向迭代器模拟实现

反向迭代器是一个容器适配器，正因为有了正向迭代器我们可以适配出一个反向迭代器。

更为详细内容情况看这里【C++】priority_queue模拟实现+仿函数+反向迭代器

反向迭代器里面的运算符重装调用正向迭代器的就行了。

template<class iterator, class Ref, class Ptr>
class _RBTreeReverseIterator
{
public:
	typedef _RBTreeReverseIterator<iterator, Ref, Ptr> Self;
public:
	_RBTreeReverseIterator(iterator it)
		:_it(it)
	{}


private:
	iterator _it;
};

template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//正向迭代器
	typedef _RBTreeIterator<T,T&,T*> iterator;
	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
	//反向迭代器
	typedef _RBTreeReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef _RBTreeReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
	///
}

我们先把正向迭代器还差的一些东西补上。

主要补充的就是- –
其实 – -完全就是 ++反过来了
it在15的位置，说明这颗以15为根的子树，根和右子树已经访问过了，该访问左子树了，左子树分为两个情况，左子树存在，不存在

1.左不为空，下一个左子树最右节点
2.左为空，去找祖先（孩子是父亲右的那个祖先）

正向迭代器完整代码

template<class T,class Ref,class Ptr>
class _RBTreeIterator
{
public:
	typedef RBTreeNode<T> Node;
	Node* _node;
	typedef _RBTreeIterator<T,Ref,Ptr> Self;
	typedef _RBTreeIterator<T, T&, T*> iterator;


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

	_RBTreeIterator(const iterator& s)
		:_node(s._node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

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

	//++it
	Self& operator++()
	{
		//1.右不为空，找下一个右子树最左节点
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;//_node指向它
		}
		else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//走到最后parent为空
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	//it++
	Self operator(int)
	{
		Self tmp(*this);
		operator++();
		return tmp;
	}

	//--it
	Self& operator--()//1.左不为空，下一个左子树最右节点
	{
		if (_node->_left)
		{
			Node* max = _node->_left;
			while (max->_right)
			{
				max = max->_right;
			}
			_node = max;
		}
		else//2.左为空，去找祖先（孩子是父亲右的那个祖先）
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	//it--
	Self operator--(int)
	{
		Self tmp(*this);
		operator--();
		return tmp;
	}

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

下面开始写反向迭代器，其实很简单直接复用就行了。

++，rit最开始指向15的位置，它++，就相当于正向迭代器的- –

反向迭代器完整代码

template<class iterator, class Ref, class Ptr>
class _RBTreeReverseIterator
{
public:
	typedef _RBTreeReverseIterator<iterator, Ref, Ptr> Self;
public:
	_RBTreeReverseIterator(iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	//++it
	Self& operator++()
	{
		--_it;
		return *this;
	}

	//it++
	Self operator++(int)
	{
		Self tmp(*this);
		++_it;
		return tmp;
	}

	//--it
	Self& operator--()
	{
		++_it;
		return *this;
	}

	//it--
	Self operator--(int)
	{
		Self tmp(*this);
		++_it;
		return tmp;
	}

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

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


private:
	iterator _it;
};

我们再把红黑树，map，set反向迭代器补充一下

//RBTree.h
template<class K, class T,class KeyofT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//正向迭代器
	typedef _RBTreeIterator<T,T&,T*> iterator;
	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
	//反向迭代器
	typedef _RBTreeReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef _RBTreeReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;


public:

	iterator begin()
	{
		Node* left = _root->_left;
		while (left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	
	iterator end()
	{
		return iterator(nullptr);
	}

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

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

	reverse_iterator rbegin()
	{
		Node* right = _root;
		while (right && right->_right)
		{
			right = right->_right;
		}
		return reverse_iterator(right);
	}

	reverse_iterator rend()
	{
		return reverse_iterator(nullptr);
	}

	const_reverse_iterator rbegin() const
	{
		Node* right = _root;
		while (right && right->_right)
		{
			right = right->_right;
		}
		return const_reverse_iterator(right);
	}

	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(nullptr);
	}
	/
}

//map.h
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;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::reverse_iterator reverse_iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_reverse_iterator const_reverse_iterator;
		

		pair<iterator,bool> Insert(const pair<const K, V>& kv)
		{
			return _t.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}

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

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

		const_iterator begin() const
		{
			return _t.begin();
		}

		const_iterator end() const
		{
			return _t.end();
		}

		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.rend();
		}

		const_reverse_iterator rbegin() const
		{
			return _t.rbegin();
		}

		const_reverse_iterator rend() const
		{
			return _t.rend();
		}

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

//set.h
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;
		typedef typename RBTree<K, K, SetKeyofT>::const_reverse_iterator reverse_iterator;
		typedef typename RBTree<K, K, SetKeyofT>::const_reverse_iterator const_reverse_iterator;


		pair<iterator,bool> Insert(const K& key)
		{
			pair<typename RBTree<K, K, SetKeyofT>::iterator, bool> ret = _t.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
		}

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

		iterator end() const
		{
			return _t.end();
		}
		
		reverse_iterator rbegin() const
		{
			return _t.rbegin();
		}

		reverse_iterator rend() const
		{
			return _t.rend();
		}

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

关于map和set的模拟实现就到这里，还有一些接口没有实现，感兴趣的小伙伴可以自己动手实现。