封装有点难 - . -

---

前言

因为我们要将红黑树封装让map和set使用，所以我们要在原来的基础上将红黑树代码进行修改，最主要的是修改模板参数，下面我们直接进入正题：

---

一、红黑树原先代码的修改

首先我们拿出STL中的源代码，看看大佬是如何进行封装的：

我们可以看到在STL中map的模板参数是Key和T，这没毛病很显然是KV结构，那么底层红黑树key_type和value_type是什么？其中Key是KeyType的别名，value是pair的别名，也就是说map有两个模板参数一个是key，一个是为pair的value,这个pair大家要记住也是一个键值对。那么这到底是怎么回事呢？别急，我们再看看set的实现然后给出答案：

 我们可以看到，set整体的模板参数还是Key,但是在底层红黑树的参数变成了key_type和value_type，而这两个参数都是同一个Key重命名而来的，也就是说set的底层用红黑树是两个Key做模板参数，到这其实我们应该是明白了，真正在红黑树中存储的是key还是kv结构是由第二个模板参数Value_type来决定的，因为map中的value_type是pair,set中的value_type是key.那么第一个参数key有什么用呢？为什么要多传这一个参数呢？因为在我们用find查找以及erase删除接口的时候，我们都是用的key值啊，举个例子，map中的find接口要查找不能用pair直接查找吧，我们是用的pair中的first来进行查找，但是由于set是key可以直接使用，pair要拿到first才能查找，所以干脆就多传一个参数，这个参数就是我们查找呀什么的那些接口所需要的类型，下面是红黑树的源码：

 我们可以看到红黑树的节点确实通过一个模板参数来控制，然后红黑树中两个模板参数，源码中实现了一个头结点和记录节点的多少，我们没有实现所以不用管这个，了解了以上知识我们就可以将之前的红黑树代码先修改一下：

template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{

	}
};

 首先将红黑树节点修改完毕，我们将原来的pair变成一个data类型，这个类型在set中是key，在map中是pair。

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);
		if (parent->_data < data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//开始红黑树
        //...........省略
}

上面是我们将红黑树进行了修改，因为我们将红黑树的节点模板参数设为T，所以我们在红黑树中需要修改一下将第二个参数设置为T，然后insert函数也需要改变，因为我们直接插入的是一个pair值，但是很明显这样是解决不了set的问题的，所以我们插入的是一个T类型的data，这个T类型的data就是红黑树节点中存储的值，将这些修改完毕后我们就可以实现map和set了，下面我们先实现set：

namespace sxy
{
	template <class K>
	class set
	{

	public:

		bool insert(const K& key)
		{
			return _t.insert(key);
		}
	private:
		RBTree<K, K> _t;
	};
	void test_set()
	{
		set<int> s;
		s.insert(1);
		s.insert(2);
		s.insert(3);
		/*set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}*/
	}
}

如我们之前所讲，set只需要一个参数key，但是在底层红黑树中是需要传两个K的，然后用红黑树的插入接口等即可，下面我们先演示一下:

 展开后2的左边是1右边是3，下面我们在简单实现一下map的：

namespace sxy
{
	template<class K, class V>
	class map
	{

	public:
		bool insert(const pair<const K, V>& kv)
		{
			return _t.insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>> _t;
	};
	void test_map()
	{
		map<int, int> mp;
		mp.insert(make_pair(1, 1));
		mp.insert(make_pair(2, 2));
		mp.insert(make_pair(3, 3));
	}
}

在map中我们需要的是KV结构，然后再调用底层红黑树的时候第一个参数为K，第二个参数为pair类型，pair的first加上const是因为map中的first不允许修改，但是second可以修改。同样我们跑起来演示一下：

 可以看到2的左边是1,1,右边是3,3.下面我们总结一下，map和set在用底层红黑树的时候set会多用一个模板参数，理由是：

1.第一个参数拿到单独K的类型，因为find，erase这些接口函数的参数是K。

2.第二个模板参数决定了树的节点里面存什么。。 K or KV

测试完毕后我们讲解源码中红黑树的第三个模板参数KeyOfT,这个参数实际上就是一个仿函数，通过一个仿函数将pair中的first拿到或者直接拿到set中的key。

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

可以看到set中的仿函数就是直接返回key。

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

map中的仿函数需要返回pair中的first，下面我们将红黑树的模板参数加入KeyOfT:

template <class K, class T, class KeyOfT>
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;
		KeyOfT kot;
		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);
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

可以看到我们在insert函数中加入了kot这个仿函数，这个仿函数重载了()符号，所以我们用kot(cur->data)就拿到了set中的key或者map中的pair.first,对了，前面我们没加仿函数但是程序可以运行的原因是：pair是有自己的比较方法的，也是通过仿函数实现的，当first不相等就用first比较，当first相等就用second比较，但是这不是我们想要的，我们想要的只是通过first比较，所以我们用仿函数来控制确定只拿出first。因为加入了一个模板参数所以map和set肯定是需要修改的：

 将这里的仿函数加入后我们就正式将红黑树部分搞定了，下面画张图让大家理解一下set和map如何调用红黑树的：

 下面就开始实现迭代器了。

二、红黑树迭代器的实现

迭代器的实现同样我们参考源码：

 我们可以看到源码中对于普通迭代器和const迭代器都用了const迭代器，这也就证明了为什么我们在使用map和set的时候不可以用迭代器修改其Key值，rep_type是红黑树的迭代器，也就是说map和set都用的红黑树内部的迭代器，当我们要使用模板类的使用要用typename否则编译器会报错以为没有实现迭代器，加了typename就会等模板实例化后。

 我们可以看到，红黑树的迭代器在源码中typedef了很多，下面我们就实现一下：

因为红黑树每一个都是节点，所以我们的迭代器实现和list的迭代器一样，底层用一个节点就解决了：

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)
	{

	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		//....
	}
};

这里的Ref就是T&，Ptr就是T*，这里的玩法我们在list的迭代器就玩过了，这样可以让模板生成普通迭代器和const迭代器，如果调用者传的const T&，const T*那么就是const迭代器。然后迭代器的构造就是通过一个节点来构造，*（解引用）就是返回节点的data值的引用，->如果是pair类型本来需要两次->才能访问到pair的first但是我们重载后一个->就能访问到节点中的data，并且我们返回的是T*，引用的本质也是指针所以直接返回引用。下面我们就实现迭代器中的++：

首先我们要知道，红黑树的迭代器的begin位置是在中序遍历的第一个位置（因为中序才能排序），所以我们直接看下图：

 对于下面这张图我们的it就是迭代器，在中序的第一个位置，++后我们要访问6这个位置，这个位置有什么要求呢？首先如果1这个节点有右子树并且6有左子树还需要依次往6这个节点的左子树走（因为中序遍历：左子树，根，右子树），如果1这个节点没有右子树那么++后的节点是8所以我们要判断的就是是否有右子树，如果有就访问右子树的最左节点，如果没有就要回溯，回溯也并不简单我们用代码来演示：

Self& operator++()
	{
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

我们直接说else语句中的代码，当发现右边为空时那就说明该向上回溯了，而我们通过图可以看到：当迭代器在6这个位置，正好6的右子树为空，++只能向上走，向上的时候1是parent是存在的并且1的右子树是cur，所以向上继续找parent变成8cur变成1，这个时候不满足8的右边是cur，所以这个时候parent的节点就是++后的节点，找到后返回*this(*this就是++后的迭代器).下面我们将迭代器放到红黑树中：

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;
public:
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}

begin我们已经说过是中序的第一个节点，拿到中序第一个节点后直接返回用这个节点构造的迭代器即可。end我们直接返回由空指针构造的迭代器即可，因为end必须是最后一个节点的后一个位置，而最后一个节点的后一个位置本来也是空。（这里源代码中是增加一个高于根节点的头结点，让end最后指向头结点，但是我们的nullptr也可以完成任务只不过不能从end--回到上一个节点（因为end为空）），而源代码是可以让end--在返回上一个节点的）接下来我们将迭代器放到set中看一下：

template <class K>
	class set
	{
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

这里我们先用的普通迭代器，因为const迭代器还有一个很难理解的问题需要我们详细讲解。因为这里用了红黑树的迭代器，所以红黑树中我们对于迭代器的typedef都放在public中，否则会有权限的问题：

 可以看到我们的迭代器没毛病，下面我们再用一下map:

template<class K, class V>
	class map
	{
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
	void test_map()
	{
		map<int, int> mp;
		mp.insert(make_pair(1, 1));
		mp.insert(make_pair(2, 2));
		mp.insert(make_pair(3, 3));
		for (auto& e : mp)
		{
			cout << e.first << ":" << e.second << endl;
		}
		cout << "-------------------------------- -" << endl;
		map<int, int>::iterator it = mp.begin();
		while (it != mp.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
	}

 可以看到我们的迭代器用于set和map都没问题，然后刚刚我们没有实现迭代器--现在实现一下：

--直接就是++的相反，比如++是左中右遍历，那么--就是右中左遍历：

Self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

 对于--大家让迭代器等于8或者等于6让其随着代码走一遍就知道正确与否。

有了迭代器后，我们就可以将map的[]运算符实现出来了，下面我们先修改insert函数：

pair<iterator,bool> insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点必须为黑色
			_root->_col = BLACK;
			//只有一个根节点，插入成功后返回根节点所在的迭代器
			return make_pair(iterator(_root), true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		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
			{
				//cur找到与要插入节点相等的节点，但由于相等没有插入，返回cur这个位置的迭代器
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//开始红黑树
	    //省略没有修改的地方......
		_root->_col = BLACK;
		//本来应该返回新插入节点的迭代器，但是由于cur在进入红黑树位置会发生调整，所以提前保存cur
		return make_pair(iterator(newnode), true);
	}

我们详细的介绍过map中的[]运算符，这个运算符可以实现：如果key不在就插入，如果在就返回second的引用（map中的second可以修改我们反复说过），唯一需要注意的地方是最后要返回新插入节点的迭代器，但是新节点在红黑树调整的过程中cur发生了变化，所以提前记录cur，最后返回之前记录的cur的这个节点即可。

 将map和set中insert的返回值修改完后我们实现[]：

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

首先[]要返回pair中second的引用，而second的模板参数是V所以返回值是V&,然后【】的插入是根据key来确定的，如果key存在bool为false，如果不存在就插入，但是不管怎么样我们都返回second，再插入的时候我们刚开始不知道K,V中的V具体是多少，所以我们给一个匿名对象去初始化即可，返回值这里就用到我们以前的知识了，首先ret是一个pair，先拿到pair中的迭代器，因为map迭代器里面存放的是pair，所以代码应该是：ret.first->_node->_data->second,但是由于我们重载了->符号所以可以直接访问到_data,然后返回_data->second即可下面我们测试一下是否成功：（如果对于->还有问题可以看一下下面第一张图：）

 it是一个迭代器，一旦通过->符号就拿到了红黑树节点中的_data，map中data存放的是KV模型，所以直接访问first，second。

void test_map2()
	{
		string arr[] = { "苹果","西瓜","西瓜","梨","葡萄" };
		map<string, int> mp;
		for (auto& e : arr)
		{
			mp[e]++;
		}
		for (auto& m : mp)
		{
			cout << m.first << ":" << m.second << endl;
		}
	}

 通过运行结果我们也发现是没问题的，接下来我们就要实现const迭代器了，首先先加入const迭代器：

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

 然后我们先用set做一下测试：

 运行起来报错了：

 错误原因在这里：

 我们已经将set的普通迭代器修改为红黑树中的const迭代器，但是红黑树中的begin()是一个普通迭代器，iterator经过typedef已经变成const迭代器，所以发生了报错，当然有人发现：

 将set的第二个参数加个const就可以，确实是这样，但是map该怎么办呢？map能在pair前面加上const吗？很明显是不能的，因为map中只有key也就是first不能修改，second是可以修改的，这该怎么办呢？下面我们参考一下源代码：

 首先set里面普通迭代器用const迭代器实现，const迭代器也用const迭代器来实现，并且begin和end()也没做任何修改，所以这里应该也面临着和我们一样的问题，那就是如何解决普通迭代器转化为const迭代器，我们继续看：

 我们可以看到源码中的迭代器比我们的迭代器多了一个构造函数，首先我们区分一下，iterator里面的参数都是不加const的所一iterator是普通迭代器，而self里面的参数是ref和ptr,当传参为const类型时self就变成了const迭代器，当传参为不带const就是普通迭代器，而最后的这个构造函数的参数是一个普通迭代器，那有什么作用呢？其实是这样：

1.当我本身的迭代器是普通迭代器时，参数也是一个普通迭代器这个时候就是一个拷贝构造函数。

2.当我本身是一个const迭代器时，参数是一个普通迭代器，这个时候就变成了用普通迭代器构造const迭代器，也就是说让普通迭代器和const迭代器之间进行转化了，再想想我们刚刚的报错，无法从普通迭代器转化为const迭代器，用上这个构造函数不就可以将红黑树中的普通迭代器转化为const迭代器了吗。 （现在搞懂这个构造函数为什么不用self来做参数了吧，因为self的参数如果是const那么self就变成const迭代器，那还如何转化呢）

 了解了以上知识我们直接加一个构造函数就可以了，一定要注意这个构造函数的参数是普通迭代器：

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)
	{

	}
	RBTreeIterator(const RBTreeIterator<T, T&, T*>& it)
		:_node(it._node)
	{

	}

有了这个构造函数运行起来就不会报错了，下面我们看看map的迭代器：

 我们可以看到map中普通迭代器还是普通迭代器，const迭代器是const迭代器。

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;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		const_iterator begin() const
		{
			return _t.begin();
		}
		const_iterator end() const
		{
			return _t.end();
		}

这样我们就搞定了set和map的底层，以上就是本文的所有内容了。

---

总结

对于这里的难点我认为迭代器确实是有难度的，并且有些方法也不是我们普通人可以想到的，所以要多看优秀的代码才能提升自己。