【C++详解】用红黑树封装模拟实现mymap、myset

前言

我们要用红黑树封装自己的map和set需要完成以下六个步骤：
1、实现红⿊树
2、封装map和set框架，解决KeyOfT
3、iterator
4、const_iterator
5、key不⽀持修改的问题
6、operator[]

实现红黑树小编在上一篇博文已经介绍了：红黑树实现
所以本文聚焦剩下的5个步骤。

一、源码及框架分析

这篇文章实现mymap、myset参考SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件中。
stl_map.h、stl_set.h中map和set底层就是采用的stl_tree.h中的rb_tree作为底层存储结构，并通过模板参数配置rb_tree以符合map和set的功能需求。具体细节看下面截取的一部分源码。

首先明确，三个类的模板参数Key都是同一个东西，stl_map.h里的模板参数T是我们在二叉搜索树章节介绍的key/value结构中value的类型，stl_tree.h里的模板参数Value是红黑树为了适配set和map做的泛型类型，若红黑树是为了实现set则Value实例化为key，若是为了实现map则Value实例化为pair<Ley,T>，总而言之Value就是红黑树存储的数据类型。
我们可以看到在底层红黑树内部不仅仅内部数据类型是泛型，就连传给红黑树模板参数的类型也是map和set传来的泛型。(红黑树代表存储数据类型的第二个模板参数set传递的是Key，map传递的是pair<const Key,T>)这里可以简单理解成两重泛型。

• 通过上图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，但是key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。(图中箭头方框标记的就是红黑树中实际存放的数据类型)
• set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是pair<const key, T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
• 要注意⼀下，源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。
• rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板参数Key呢？尤其是set，两个模板参数是⼀样的，这是很多读者这时的⼀个疑问。要注意的是对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和erase的是Key对象。

二、封装框架，解决KeyOfT

• 参考源码框架，map和set复⽤之前我们实现的红⿊树。
• 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的数据类型，我们使⽤T。
• 其次因为底层RBTree实现了泛型导致不知道T参数是K，还是pair<K, V>，在insert内部进⾏插⼊逻辑⽐较时，是cur->_data和data进行比较，而在find和erase中是cur->_data和Key进行比较，所以这里我们无法像priority_queue那样实现出一个传递同类型参数用来比较单一类型(这里指data)的仿函数，这里的比较逻辑是我们需要在任何时候只⽐较key，实现思路是虽然底层RBTree不知道T参数是K，还是pair<K, V>，但是上层map和set层清楚的知道要传递什么类型给底层的RBTree中的T模板参数，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的第三个模板参数KeyOfT(仿函数传递思路)，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较，具体细节参考如下代码实现。

//map
struct MapkeyofT
		{
			//v在map中是pair对象
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
//set
struct SetkeyofT
		{
			//k在set中是K类型对象
			const K& operator()(const K& k)
			{
				return k;
			}
		};

三、⽀持iterator的实现

iterator实现思路分析

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。
• 这⾥的难点是operator++和operator–的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10所在结点的迭代器。
• 迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。
• 迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点和当前结点的左子树已经访问完了，要访问下⼀个结点是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。
• 迭代器++时，如果it指向的结点的右⼦树为空，代表当前结点已经访问完了且当前结点所在的⼦树也访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上找。
• 如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结点的⽗亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
• 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找到孩⼦是⽗亲左的那个祖先就是中序要遍历的下⼀个结点。如下图：it指向15，15右为空，15是10的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个访问的结点就是18。
• begin()返回整棵二叉树的最右结点。
• end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这时⽗亲为空了，所以我们⽤nullptr去充当end。需要注意的是stl源码中，红⿊树增加了⼀个哨兵位头结点作为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是–end()判断到结点时空，特殊处理⼀下，让迭代器结点指向最右结点。具体参考迭代器–实现。
• 迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树，具体参考下⾯代码实现。
• set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree<K,const K, SetKeyOfT> _t;
• map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;
• ⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码，小编会逐步讲解。

示意图：

iterator代码实现

这里的迭代器实现和链表很相似，因为底层结构都是不连续的结点。
1、迭代器的析构、拷贝构造都不需要自己写，因为结点并不属于迭代器，而是属于红黑树，由红黑树来维护结点的生死。
2、在map和set里使用迭代器需要加typename和域作用限定符。加typename因为迭代器是在类模板RBTree中取内嵌类型Iterator。加域作用限定符是因为__TreeIterator虽然是在全局定义的，但是我们要复用的是在RBTree内部重定义的Iterator，所以需要加域作用限定符。

//map
typedef typename RBTree<K, pair<K, V>, MapkeyofT>::Iterator iterator;
//set
typedef typename RBTree<K, K, SetkeyofT>::Iterator iterator; 

3、迭代器的接口基本上都不用显示写参数，都是操作this指针，除了比较大小和初始化。
4、迭代器operator++后要改变迭代器的成员变量_node，然后返回*this。

//__Tree_Iterator
self& operator++()  //这里返回值不用加const吧？ //对
{
	if (_node->_right) //当前结点存在右子树，找右子树的最左结点
	{
		_node = _node->_right;
		while (_node->_left)
		{
			_node = _node->_left;
		}
	}
	else  //当前结点不存在右子树
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent != nullptr && cur == parent->_right) //若cur不为根节点或者cur在parent右边需要继续往上找
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

5、迭代器的初始化传递的node参数最好不用const修饰，这样既可以初始化非const迭代器也可以初始化const迭代器。

//__Tree_Iterator
__Tree_Iterator(Node* node)
	:_node(node)
{}

5、RBTree里begin和end的返回值类型是Iterator，最好返回Iterator的匿名对象Iterator()，如Iterator(nullptr)，所以由此可知begin和end不能传引用返回，因为匿名对象具有常性，而begin和end的返回值因为返回的迭代器会被修改不能加const，传引用返回就会造成权限的放大。

//RBTree
	Iterator Begin() //找整棵树最左结点
	{
		Node* minleft = _root;
		while (minleft && minleft->_left)
		{
			minleft = minleft->_left;
		}
		return Iterator(minleft);
	}

	Iterator End() 
	{
		return Iterator(nullptr);
	}

6、迭代器比较就是单纯的比迭代器成员变量_node的大小，不要以为是去比迭代器内部的_data，并且迭代器比较时参数传的是迭代器对象，还需要取迭代器对象里的成员变量_node出来比较。

//__Tree_Iterator
bool operator!=(const self& s)
{
	//迭代器比较就是单纯的比迭代器本身也就是迭代器成员变量的大小
	return _node != s._node;
}

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

7、不管在哪个类里迭代器都最好typedef在类的共有，因为迭代器的定位是作为 “容器对外遍历的接口”。

普通迭代器实现代码：

template<class T>
class __Tree_Iterator
{
	typedef RBTNode<T> Node;
	typedef __Tree_Iterator<T> self;
	Node* _node;  //Iterator的成员变量
public:
	__Tree_Iterator(Node* node)
		:_node(node)
	{}

	T& operator*() //支持返回值可以修改，不加const
	{
		return _node->_data;  //返回值可能是key也可能是pair
	}

	T* operator->() //返回值是T*,只不过使用时编译器会自动优化
	{
		return &(_node->_data);
	}

	self& operator++()  //这里返回值不用加const吧？ //对
	{
		if (_node->_right) //当前结点存在右子树，找右子树的最左结点
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else  //当前结点不存在右子树
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_right) //若cur不为根节点或者cur在parent右边需要继续往上找
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const self& s)
	{
		//迭代器比较就是单纯的比迭代器本身也就是迭代器成员变量的大小
		return _node != s._node;
	}

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

四、const迭代器

const迭代器也和list一样，通过模板参数控制operator*()和operator->()返回值来实现，有了const迭代器后需要在RBTree set map里都需要重载一份const begin 和 const begin，只不过set map是复用RBTree里的罢了。

template<class T, class Ref, class Ptr>
class __Tree_Iterator
{
	typedef RBTNode<T> Node;
	typedef __Tree_Iterator<T, Ref, Ptr> self;
	Node* _node;  //Iterator的成员变量
public:
	__Tree_Iterator(Node* node)
		:_node(node)
	{}

	Ref operator*() //支持返回值可以修改，不加const
	{
		return _node->_data;  //返回值可能是key也可能是pair
	}

	Ptr operator->() //返回值是T*,只不过使用时编译器会自动优化
	{
		return &(_node->_data);
	}

	self& operator++()  //这里返回值不用加const吧？ //对
	{
		if (_node->_right) //当前结点存在右子树，找右子树的最左结点
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else  //当前结点不存在右子树
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_right) //若cur不为根节点或者cur在parent右边需要继续往上找
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const self& s)
	{
		//迭代器比较就是单纯的比迭代器本身也就是迭代器成员变量的大小
		return _node != s._node;
	}

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

五、operator–

迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树，但是这里有一点需要注意，当当前结点为nullptr也就是end(）的返回值时，operator–需要通过红黑树根节点找到当前红黑树最右结点，也就是我们实现的迭代器还需要一个参数来传递红黑树的根结点，那么迭代器的构造函数需要跟着变，RBTree内部的begin()和end()返回值也需要返回由当前结点_node和根节点_root合并一起返回。

//__Tree_Iterator
	Node* _node;  //Iterator的成员变量
	Node* _root;
public:
	__Tree_Iterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}
	
//RBTree
Iterator Begin() //找整棵树最左结点
{
	Node* minleft = _root;
	while (minleft && minleft->_left)
	{
		minleft = minleft->_left;
	}
	return Iterator(minleft, _root);
}

Iterator End() 
{
	return Iterator(nullptr, _root);
}

operator–实现代码如下：

	self& operator--()
	{
		if (_node == nullptr) // end()
		{
			// --end()，特殊处理，⾛到中序最后⼀个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左⼦树不为空，找左⼦树最右结点
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 找孩⼦是⽗亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

六、实现key不支持修改

我们知道在库里set和map的key是不支持修改的，我们想要实现也很简单，通过上层set和map里配置底层红黑树的第二个模板参数就行了，set是_data整体不能被修改，map的_data是pair，要求pair的first不能被修改，而second可以被修改。

//set
typedef typename RBTree<K, const K, SetkeyofT>::Iterator iterator;  //RBTree后面加不加模板参数？//要加
typedef typename RBTree<K, const K, SetkeyofT>::ConstIterator const_iterator;

private:
	RBTree<K, const K, SetkeyofT> _t;

//map
typedef typename RBTree<K, pair<const K, V>, MapkeyofT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapkeyofT>::ConstIterator const_iterator;
private:
RBTree<K, pair<const K, V>, MapkeyofT> _t;

七、operator[ ]

我们在map和set使用章节介绍过map独有的operator[ ]实现要依托于insert的返回值，我们目前insert的返回值的bool类型，所以我们首先需要调整insert的接口。
第一步修改insert的返回值为pair<Iterator,bool>，修改完返回值后insert里每一个返回bool值的地方也需要跟着调整，前两个返回点恒简单，主要是第三给返回点，前面两个返回点都是用cur代表新插入结点然后返回，但是如果叔叔存在且为红cur要往上走，所以需要用一个newnode提前保存cur的值，最后返回newnode。

//RBTree
pair<Iterator, bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK; 
		return { Iterator(_root, _root),true }; //返回点1
	}
	Node* parent = nullptr;
	Node* cur = _root;
	KeyofT kot;
	while (cur)
	{
		if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return { Iterator(cur, _root),false }; //返回点2
		}
	}
	cur = new Node(data);
	Node* newnode = cur; 
	cur->_col = RED;  
	if (kot(data) < kot(parent->_data))
		parent->_left = cur;
	else
		parent->_right = cur;
	cur->_parent = parent;

	while (parent && parent->_col == RED) 
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left) 
		{
			Node* uncle = grandparent->_right;
			if (uncle && uncle->_col == RED)    
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				//继续向上调整
				cur = grandparent;
				parent = cur->_parent;
			}
			else                               
			{
				if (cur == parent->_left) 
				{
					//      g
					//    p   u
					//  c
					RotateR(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else                    
				{
					//      g
					//    p   u
					//     c
					RotateL(parent);
					RotateR(grandparent);
					grandparent->_col = RED;
					cur->_col = BLACK; //cur被推上来做根
				}
				break; //情况2、3执行完后便更新完毕
			}
		}
		else  //p在右，u在左
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)     //u存在且为红
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				//继续向上调整
				cur = grandparent;
				parent = cur->_parent;
			}
			else                                //u存在且为黑或不存在
			{
				if (cur == parent->_right) //都右边小，左单旋
				{
					//      g
					//    u   p
					//         c
					RotateL(grandparent);
					grandparent->_col = RED;
					parent->_col = BLACK;
				}
				else                      //右边大的左边小，右左双旋
				{
					//      g
					//    u   p
					//       c
					RotateR(parent);
					RotateL(grandparent);
					grandparent->_col = RED;
					cur->_col = BLACK; //cur被推上来做根
				}
				break;
			}
		}
	}
	_root->_col = BLACK;  //情况1cur更新到根节点需要把根结点变黑
	return { Iterator(newnode, _root),true }; //返回点3
}

然后在上层map里修改insert，补充operator[]复用insert。

//map
pair<iterator, bool> insert(const pair<K, V>& kv) //pair<K, V>就是RBTree里的T
{
	return _t.Insert(kv);
}

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

八、源码

mymap.h

#pragma once

#include "RBTree.h"

namespace wusaqi
{
	template<class K, class V>
	class map
	{
		struct MapkeyofT
		{
			//v在map中是pair对象
			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;
		iterator begin()
		{
			return _t.Begin();
		}

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

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

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

		pair<iterator, bool> insert(const pair<K, V>& kv) //插入红黑树中存储的数据类型
		{
			return _t.Insert(kv);
		}

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

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

myset.h

#pragma once

#include "RBTree.h"

namespace wusaqi
{
	template<class K>
	class set
	{
		struct SetkeyofT
		{
			//k在set中是K类型对象
			const K& operator()(const K& k)
			{
				return k;
			}
		};


	public:
		typedef typename RBTree<K, const K, SetkeyofT>::Iterator iterator;  //RBTree后面加不加模板参数？//要加
		typedef typename RBTree<K, const K, SetkeyofT>::ConstIterator 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();
		}

		pair<iterator, bool> insert(const K& key)  // 插入红黑树中存储的数据类型
		{
			return _t.Insert(key);
		}


	private:
		RBTree<K, const K, SetkeyofT> _t;
	};
}

RBTree.h

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

enum colour
{
	BLACK,
	RED
};

template<class T>
struct RBTNode
{
	T _data;
	RBTNode<T>* _left;
	RBTNode<T>* _right;
	RBTNode<T>* _parent;
	colour _col;

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

template<class T, class Ref, class Ptr>
class __Tree_Iterator
{
	typedef RBTNode<T> Node;
	typedef __Tree_Iterator<T, Ref, Ptr> self;
	Node* _node;  //Iterator的成员变量
	Node* _root;
public:
	__Tree_Iterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}

	Ref operator*() //支持返回值可以修改，不加const
	{
		return _node->_data;  //返回值可能是key也可能是pair
	}

	Ptr operator->() //返回值是T*,只不过使用时编译器会自动优化
	{
		return &(_node->_data);
	}

	self& operator++()  //这里返回值不用加const吧？ //对
	{
		if (_node->_right) //当前结点存在右子树，找右子树的最左结点
		{
			_node = _node->_right;
			while (_node->_left)
			{
				_node = _node->_left;
			}
		}
		else  //当前结点不存在右子树
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_right) //若cur不为根节点或者cur在parent右边需要继续往上找
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	self& operator--()
	{
		if (_node == nullptr) // end()
		{
			// --end()，特殊处理，⾛到中序最后⼀个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左⼦树不为空，找左⼦树最右结点
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 找孩⼦是⽗亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	bool operator!=(const self& s)
	{
		//迭代器比较就是单纯的比迭代器本身也就是迭代器成员变量的大小
		return _node != s._node;
	}

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

//K是传给find/erase等函数做形参的类型的，T是真正的datatype
template<class K, class T, class KeyofT>
class RBTree
{
	typedef RBTNode<T> Node;
public:
	typedef __Tree_Iterator<T, T&, T*> Iterator;
	typedef __Tree_Iterator<T, const T&, const T*> ConstIterator;

	Iterator Begin() //找整棵树最左结点
	{
		Node* minleft = _root;
		while (minleft && minleft->_left)
		{
			minleft = minleft->_left;
		}
		return Iterator(minleft, _root);
	}

	Iterator End() 
	{
		return Iterator(nullptr, _root);
	}

	ConstIterator Begin() const//找整棵树最左结点
	{
		Node* minleft = _root;
		while (minleft && minleft->_left)
		{
			minleft = minleft->_left;
		}
		return ConstIterator(minleft, _root);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr, _root);
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; //根结点为黑
			return { Iterator(_root, _root),true }; //返回点1
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyofT kot;
		while (cur)
		{
			//cur->_data类型是T
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return { Iterator(cur, _root),false }; //返回点2
			}
		}
		cur = new Node(data);
		Node* newnode = cur; //提前保存，以便最后返回
		cur->_col = RED;   //插入结点默认为红
		if (kot(data) < kot(parent->_data))
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		while (parent && parent->_col == RED) //更新到根结点和parent为黑出循环停止更新
		{
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)  //p在左，u在右
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)     //u存在且为红
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else                                //u存在且为黑或不存在
				{
					if (cur == parent->_left) //都左边小，右单旋
					{
						//      g
						//    p   u
						//  c
						RotateR(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
					else                     //左边小的右边大，左右双旋
					{
						//      g
						//    p   u
						//     c
						RotateL(parent);
						RotateR(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK; //cur被推上来做根
					}
					break; //情况2、3执行完后便更新完毕
				}
			}
			else  //p在右，u在左
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)     //u存在且为红
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
					//继续向上调整
					cur = grandparent;
					parent = cur->_parent;
				}
				else                                //u存在且为黑或不存在
				{
					if (cur == parent->_right) //都右边小，左单旋
					{
						//      g
						//    u   p
						//         c
						RotateL(grandparent);
						grandparent->_col = RED;
						parent->_col = BLACK;
					}
					else                      //右边大的左边小，右左双旋
					{
						//      g
						//    u   p
						//       c
						RotateR(parent);
						RotateL(grandparent);
						grandparent->_col = RED;
						cur->_col = BLACK; //cur被推上来做根
					}
					break;
				}
			}
		}
		_root->_col = BLACK;  //情况1cur更新到根节点需要把根结点变黑
		return { Iterator(newnode, _root),true }; //返回点3
	}

	Iterator Find(const K& key)
	{
		KeyofT kot;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur, _root);
			}
		}
		return End(); //find没找到返回end
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//前序递归遍历
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			// 前序遍历⾛到空时，意味着⼀条路径⾛完了
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色结点的数量不相等的路径" << endl;
				return false;
			}
			return true;
		}
		// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "存在连续的红⾊结点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			blackNum++;
		}
		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
			return true;
		if (_root->_col == RED)
			return false;
		// 参考值
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}
			cur = cur->_left;
		}
		return Check(_root, 0, refNum);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right; //?
		//分配孩子
		subL->_right = parent;
		parent->_left = subLR;
		//调整subLR的父亲
		if (subLR)
			subLR->_parent = parent;
		Node* parentParent = parent->_parent; //提前保存
		//调整parent的父亲
		parent->_parent = subL;
		//调整subL的父亲和parentParent的孩子
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = parentParent;
			if (parent == parentParent->_left)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		//分配孩子
		subR->_left = parent;
		parent->_right = subRL;
		//调整subLR的父亲
		if (subRL)
			subRL->_parent = parent;
		Node* parentParent = parent->_parent; //提前保存
		//调整parent的父亲
		parent->_parent = subR;
		//调整subL的父亲和parentParent的孩子
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = parentParent;
			if (parent == parentParent->_left)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
		}
	}

private:
	Node* _root = nullptr;
};

test.cpp

#include "myset.h"
#include "mymap.h"

namespace wusaqi
{
	void Printset(const set<int> s)
	{

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_set()
	{
		set<int> s;
		s.insert(4);
		s.insert(1);
		s.insert(6);
		s.insert(-1);
		s.insert(3);
		s.insert(9);
		s.insert(9);
		s.insert(-5);
		s.insert(5);
		s.insert(7);

		Printset(s);

		set<int>::iterator it = s.end();
		while (it != s.begin())
		{
			--it;
			cout << *it << " ";
		}
		cout << endl;
	}

	void Printmap(const map<string, string> m)
	{
		for (auto e : m)
		{
			cout << e.first << ":" << e.second << " ";
			cout << endl;
		}
		cout << endl;
	}

	void test_map()
	{
		map<string, string> dict;
		dict.insert({ "left", "左边" });
		dict.insert({ "right", "右边" });
		dict.insert({ "string", "字符串" });
		dict.insert({ "array", "数组" });
		Printmap(dict);

		dict["insert"];
		dict["left"] = "左边、剩余";
		Printmap(dict);
	}
}


int main()
{
	//wusaqi::test_set();
	wusaqi::test_map();
	return 0;
}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~