C++模拟实现——红黑树封装set和map

一、红黑树迭代器的实现

基本的框架和实现链表的迭代器思路是一样的，都是对指针进行封装处理，然后实现一些基本的运算符重载，最重要的是operator++，需要不递归的实现走中序的规则，这里只实现那最核心的几个基本功能，用遍历和插入值去测试，其余的一些零零散散的功能就不进行实现了

基本框架

operator++的实现

按照中序遍历的规则，首先是走左子树，然后是根，然后是右子树，从begin位置开始，可以认为此时是最左边的那一个，此时的++，是要往该节点的右边去遍历，而且是右边的最左边，因此要先确定，此时是否有右边，然后走到右边的最左边，就是下一个要遍历的节点，如果右边为空，则我们说明该节点已经遍历结束了，此时往上走找到parent，需要判断parent是否已经遍历过，则需要再判断parent是否是其上一个节点的右边，如果是右边，则说明此时parent位置已经被遍历过且右子树遍历结束，需要继续向上走

ps：operator--的思路和++是一样的，不过啥反过来走，右子树根左子树，这里不过多分析

参考代码

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

	// 1、typedef __RBTreeIterator<T, T&, T*> itertaor;  拷贝构造
	// 2、 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++()
	{
		if (_node->_right)
		{
			// 1、右不为空，下一个就是右子树的最左节点
			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)
		{
			// 1、左不为空，找左子树最右节点
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}
		else
		{
			// 2、左为空，孩子是父亲的右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};

二、封装set和map

由于之前模拟实现的红黑树，是为了模拟实现和学习其中的核心功能，也就是如何完成插入，以及明白其算法原理，所以在其他的细节上，与库里的对比，做了很多的省略，本次将用自己实现的红黑树，通过封装红黑树，模拟实现出set和map，加深对set和map的理解和底层实现

我们对红黑树的改造，目的是为了兼容set和map的复用，因此，得先了解，set和map具体的使用区别

1.对红黑树的基本改造

虽然底层都是搜索二叉树，但是节点内存的值类型是不同的，从使用的角度来看，可以认为k模型每个节点存的就是一个key，搜索树的顺序和规则也是根据key的大小比较规则去执行的，而kv模型则是每个节点内存着key和value，搜索树以key的大小比较规则其执行，而每个key都有一个关联性很强的value，所以，在节点的数据类型上看，kv模型的节点数据类型pair类型的

此时，红黑树需要兼容任意类型的模板参数都能实现相同的比较规则，都是找到key去比较，则需要像以下类模板定义：

template<class K,class T,class KeyOfT>

接下来就是，将所有关于比较的部分，需要换上仿函数，通过仿函数去取得key，第一个参数K代表key，当一些需要使用到key类型的地方（返回参数等等）时使用，修改过后，对set和map的基本封装就没有问题了，至少可以实现插入功能了，各自将框架搭起来，然后复用Insert进行测试

2.对迭代器的封装

（1）set迭代器的封装

set的迭代器要求，无论是iterator还是const_iterator，都不能对值进行修改，因为在set里面存着的值就是key，key不允许被修改，所以我们封装时，直接将两种迭代器都用红黑树的const_iterator去复用，注意：typedef一个类型名的时候，需要在前面加上typename

但是，如果红黑树的迭代器实现部分，没有将普通迭代器转换成常量迭代器的函数，则直接复用会报错

说的是在使用迭代器的时候，返回的迭代器类型是普通迭代器类型，但是返回参数类型的声明却是常量迭代器类型，无法转换，这是由于我们使用的是非const对象调用红黑树的迭代器，则红黑树会则会穿一个普通迭代器，但是我们iterator的类型实际是const_iterator，因此无法转化报错，解决这个问题的办法，是在红黑树的迭代器实现部分，提供一个能够将普通迭代器转化成const迭代器的函数

当传参为const类型的迭代器时，该函数为拷贝构造，当参数是普通迭代器时，则那够构造一个const类型的迭代器返回

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

（2）map的迭代器封装

map的值是pair类型，first是key，不允许修改，second是value，允许修改，所以map的普通迭代器是允许修改值的，但要保证key不能被修改，在传参时传pair<const K,V>

3.map的operator[ ]的实现

实现[ ]的重载，需要先对红黑树中插入函数的返回值进行改造，之前为了简化，因此用bool值作为返回值，现在需要完整的实现它，返回值为pair类型，first为插入成功位置的迭代器，若是插入失败，则说明书中已经有了一个值，此时first返回已有的值的迭代器，second则是bool值，表示返回插入是否成功

改造结束后，根据[ ]功能实现，这个部分在之前有做过分析，不详细分析，提供参考代码

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

三、测试

以上就是模拟封装set和map时，需要注意的部分，接下来就是通过一些最基本的测试去测试set和map是否能实现一些基本用法，下面提供几个用于测试的代码

set测试迭代器和插入

	void test_set1()//测试迭代器和插入
	{
		srand(time(0));
		const size_t N = 1000;
		set<int> s;
		for (int i = 0; i < N; i++)
		{
			size_t x = rand() % 100;
			s.Insert(x);
		}
		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
	}

map测试迭代器和插入

	void test_map1()//测试插入和迭代器
	{
		srand(time(0));
		const size_t N = 1000;
		map<int, int> m;
		for (int i = 0; i < N; i++)
		{
			size_t x = rand() % 100;
			m.Insert(make_pair(x, x));
		}
		for (auto e : m)
		{
			cout << e.first << ":" << e.second << endl;
		}
		cout << endl;
	}

map测试[ ]的重载

	void test_map2()//测试[]的重载
	{
		map<string, string> m;
		m["字符串"] = "string";
		m["清理"] = "clear";
		m["想念"] = "miss";
		m["错过"] = "miss";
		m["错过"] = "miss";

		for (auto e : m)
		{
			cout << e.first << ":" << e.second << endl;
		}
		cout << endl;
	}