【C++：封装红黑树】C++ 红黑树封装实战：从零手把手实现MyMap与MySet

前言

用过 STL 的朋友都知道，map 和 set 是非常高频使用的关联式容器，而其底层都依赖红黑树实现 —— 通过前面的 set 和 map 学习我们已经知道了 set 容器只需要传一个类型参数K，而 map 需要传两个类型参数K/V。
那你们知道红黑树如何通过泛型设计同时支撑 “key-only”（set）和 “key-value”（map）两种场景吗？为什么 set 的迭代器不可修改，而 map 只能修改 value 不能修改 key？又是怎么让它们的迭代器实现不可修改的操作的？set 和 map 的迭代器走的是中序遍历，那又如何通过operator++找到中序遍历的下一个结点呢？
本文结合 set 和 map 的源码框架与实现细节，从红黑树的泛型改造入手，一步步拆解 myMap 和 mySet 的封装逻辑，包括关键的仿函数设计、迭代器实现、key 不可修改约束及 map 的 [] 运算符重载，帮你吃透 STL 容器的底层封装思想。

一. 架构与实现：总览设计框架，深入源码细节

在封装红黑树实现MyMap与MySet之前，我们需要先浅浅看一下 map 和 set 的源代码，虽然源代码非常乱而且难理解，但是两者的源代码是辅助我们实现MyMap与MySet的关键：

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。

1、 map 和 set 的框架核心源代码

stl_tree.h：

// stl_tree.h
struct __rb_tree_node_base
{
	typedef __rb_tree_color_type color_type;
	typedef __rb_tree_node_base* base_ptr;
	color_type color;
	base_ptr parent;
	base_ptr left;
	base_ptr right;
};

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
	= alloc>
class rb_tree {
protected:
	typedef void* void_pointer;
	typedef __rb_tree_node_base* base_ptr;
	typedef __rb_tree_node<Value> rb_tree_node;
	typedef rb_tree_node* link_type;
	typedef Key key_type;
	typedef Value value_type;
public:
	// insert⽤的是第⼆个模板参数左形参
	pair<iterator, bool> insert_unique(const value_type& x);
	// erase和find⽤第⼀个模板参数做形参
	size_type erase(const key_type& x);
	iterator find(const key_type& x);
protected:
	size_type node_count; // keeps track of size of tree
	link_type header;
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
	typedef __rb_tree_node<Value>* link_type;
	Value value_field;
};

stl_set.h：

// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_set.h>
#include <stl_multiset.h>

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
	// typedefs:
	typedef Key key_type;
	typedef Key value_type;
private:
	typedef rb_tree<key_type, value_type,
		identity<value_type>, key_compare, Alloc> rep_type;
	rep_type t; // red-black tree representing set
};

stl_map.h：

// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_map.h>
#include <stl_multimap.h>

// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
	// typedefs:
	typedef Key key_type;
	typedef T mapped_type;
	typedef pair<const Key, T> value_type;
private:
	typedef rb_tree<key_type, value_type,
		select1st<value_type>, key_compare, Alloc> rep_type;
	rep_type t; // red-black tree representing map
};

2、对比set和map的源码：泛型编程的应用

虽然两者的底层都是用红黑树实现的，但是看了上面的源代码我们发现：set 和 map 第一个模板参数都是 Key，区别就在于第二个模板参数，value 对于 set 是 key，对 map 而是 pair<const key, value>

通过下图对框架的分析，我们可以看到源码中 rb_tree 用了一个巧妙的泛型思想实现，rb_tree 不管是实现 key 的搜索场景，还是 key/value 的搜索场景不是直接写死的，而是由第二个模板参数 Value 决定 _rb_tree_node 中存储的数据类型。
set 实例化 rb_tree 时第二个模板参数给的是 Key，map 实例化 rb_tree 时第二个模板参数给的是 pair<const key,T>，这样一颗红黑树既可以实现 key 搜索场景，也可以实现 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 对象，如果不传第一个模板参数 Key，的确对于 set 没有任何影响，但是 map 就无法实现 find 和 erase 接口了

二. 核心设计思路：红黑树的泛型复用

STL 中 map 和 set 复用同一颗红黑树的核心是泛型编程 + 仿函数提取 key，解决了 “一颗树适配两种数据场景” 的问题，具体设计思路如下：

1、红黑树的模板参数设计

红黑树需要支持存储两种数据类型：

set 场景：存储单个 key（如int、string）（key 不可修改）；
map 场景：存储 pair<const Key, Value>（key 不可修改）

因此红黑树的模板参数需抽象为 3 个：

template<class K, class T, class KeyofT>
class RBTree {
    // K：find/erase时的key类型（统一接口参数）
    // T：红黑树节点存储的实际数据类型（set为 K，map为 pair<const K, V>）
    // KeyofT：仿函数，从T中提取K（解决T类型不统一的比较问题）
};

2、仿函数 KeyofT：统一 key 的提取逻辑

由于 T 的类型不固定（K 或 pair<K, V>），红黑树插入 / 查找在比较大小时无法直接获取 key，虽然 pair<K, V> 自带比较大小的接口，但是比较逻辑不是我们想要的，所以我们需通过手动实现仿函数KeyofT统一提取，由 map 和 set 分别实现适配：

set 的仿函数：直接返回 key（T = K）；
map 的仿函数：返回 pair 的 first 成员（T = pair<const K, V>）。

3、核心约束：key 不可修改

set 的 key 是唯一标识，需禁止修改：红黑树存储const K；
map 的 key 是索引，需禁止修改：pair 的 first 设为 const K，value 可正常修改。

三. 基础组件实现：红黑树、仿函数、迭代器iterator、map支持[]

1、红黑树节点结构

节点存储模板类型 T，包含左右子指针、父指针和颜色标记：

// 枚举结点颜色
enum Color
{
	BLACK, // 黑色结点
	RED    // 红色结点
};

// 红黑树结点结构
template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _father; // 父节点指针（回溯平衡需用到）
	RBTreeNode<T>* _left;    // 左子节点指针
	RBTreeNode<T>* _right;   // 右子节点指针
	Color _col;				// 节点颜色

	RBTreeNode(const T& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _father(nullptr)
		, _col(RED) //将初始化的结点颜色为红色，满足插入要求(不能插入黑色结点)
	{ }
};

2、仿函数实现（map/set 层）

2.1 set 的仿函数：直接返回 key

#include"RBTree.h"

namespace xiaoye
{
	template<class K>
	class Myset
	{
		// 仿函数：从T（const K）中提取key
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	private:
		RBTree<K, const K, SetKeyofT> _tree;
		//因为set的iterator迭代器是不支持修改的，不管是普通迭代器还是const迭代器
		//const本来就不支持修改，那普通迭代器怎么实现呢？
		//我们可以把RBTree的第二个参数用const修饰
		//这样RBTree的模板参数T就会变成const K，
		//而T就是来影响迭代器interator的实例化的(typedef RBTreeInterator<T, T&, T*> Iterator;)
	};
}

2.2 map 的仿函数：提取 pair 的 first

#include"RBTree.h"

namespace xiaoye
{
	template<class K, class V>
	class Mymap
	{
		//仿函数：从T（pair<const K, V>）中提取key
		struct MapKeyofT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		//因为RBTree中的insert需要比较大小，虽然pair自带比较大小的接口，但是比较逻辑不是我们想要的
		//pair自带的比较大小逻辑是先比较first的大小，如果相等还会比较

	private:
		RBTree<K, pair<const K, V>, MapKeyofT> _tree;
		//虽然map的迭代器支持Value的修改，但是不支持Key的修改，不管是普通迭代器还是const迭代器
		//所以我们只需要将RBTree的第二个参数修改为pair<const K, V>即可
	};
}

3、迭代器iterator

3.1 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。
end()如何表示呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有父亲，没有找到孩子是父亲左的那个祖先，这时父亲为空了，那么我们就把it 中的结点指针置为nullptr，我们用去充当end。需要注意的是stl源空，红黑树增加了一个哨兵位头结点做为end()，这哨兵位头结点和根互为父亲，左指向最左结点，右指向最右结点。相比我们用nullptr作为end()，差别不大，他能实现的，我们也能实现。只是–end()判断到结点是空，特殊处理一下，让迭代器结点指向最右结点。具体参考迭代器一个个实现。
迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右子树->根结点->左子树。但是需要一个_root。
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;

支持完整的迭代器还有很多细节需要考虑，具体参考下面的代码：

3.2 迭代器iterator的实现

template<class T, class Ref, class Ptr>
struct RBTreeInterator
{
	typedef RBTreeInterator<T, Ref, Ptr> Self;
	typedef RBTreeNode<T> Node;

	Node* _node;
	Node* _root;//_root的作用就是为了辅助实现operator--的功能
	//因为当特殊情况迭代器it为end()也就是_node为nullptr时，
	//我们原本想法是获取这棵树的最右结点，但是此时_node为nullptr我们访问不了
	//所以我们利用_root来获取这棵树的根节点

	RBTreeInterator(Node* node, Node* root)
		:_node(node)
		,_root(root)
	{ }

	Self& operator++()
	{
		if (_node->_right)
		{
			//结点右子树不为空，则中序下一个访问结点就是右子树的最左(最小)结点
			Node* minright = _node->_right;
			while (minright->_left)
			{
				minright = minright->_left;
			}
			_node = minright;
			return *this;
		}
		else
		{
			//结点右子树为空，则我们需要一直往上查找，直到孩子在父亲的左边停止，此时的父亲就是中序下一个访问结点
			Node* cur = _node;
			Node* father = cur->_father;
			while (father && father->_right == cur)
			{
				cur = father;
				father = cur->_father;
			}
			_node = father;
			return *this;
		}
	}

	Self& operator--()
	{
		if(_node == nullptr) // end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点 
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
			return *this;
		}
		else if (_node->_left)
		{
			//结点左子树不为空，则中序上一个访问结点就是左子树的最右(最大)结点
			Node* minleft = _node->_left;
			while (minleft->_right)
			{
				minleft = minleft->_right;
			}
			_node = minleft;
			return *this;
		}
		else
		{
			//结点左子树为空，则我们需要一直往上查找，直到孩子在父亲的右边停止，此时的父亲就是中序上一个访问结点
			Node* cur = _node;
			Node* father = cur->_father;
			while (father && father->_left == cur)
			{
				cur = father;
				father = cur->_father;
			}
			_node = father;
			return *this;
		}
	}

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

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

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

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

// RBTree<K, pair<K, V>> _tree; -> // map
// RBTree<K, K> _tree; ->		   // set

4、map支持[]

之前我们实现 insert 函数的返回类型为 bool，即只考虑了是否插入成功，但是无法获取插入失败的存在结点/插入成功的插入结点的位置。
而如果map要支持[ ]，就需要修改 insert 返回值支持，修改 RBtree 中的 insert 返回值为：

pair<Iterator,bool> Insert(const T& data)

这样我们就可以通过insert函数来辅助实现map的operator[]：

//利用Insert接口实现operator[]
V& operator[](const K& Key)
{
	pair<iterator, bool> ret = _tree.Insert({ Key, V() });
	return ret.first->second;
	//ret.first为迭代器iterator
	//通过迭代器来获取value值
}

四. 封装红黑树、mySet 与 myMap 完整实现

RBTree.h：

#include <iostream>
using namespace std;

// 枚举结点颜色
enum Color
{
	BLACK, // 黑色结点
	RED    // 红色结点
};

// 红黑树结点结构
template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _father; // 父节点指针（回溯平衡需用到）
	RBTreeNode<T>* _left;    // 左子节点指针
	RBTreeNode<T>* _right;   // 右子节点指针
	Color _col;				// 节点颜色

	RBTreeNode(const T& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _father(nullptr)
		, _col(RED) //将初始化的结点颜色为红色，满足插入要求(不能插入黑色结点)
	{ }
};

template<class T, class Ref, class Ptr>
struct RBTreeInterator
{
	typedef RBTreeInterator<T, Ref, Ptr> Self;
	typedef RBTreeNode<T> Node;

	Node* _node;
	Node* _root;//_root的作用就是为了辅助实现operator--的功能
	//因为当特殊情况迭代器it为end()也就是_node为nullptr时，
	//我们原本想法是获取这棵树的最右结点，但是此时_node为nullptr我们访问不了
	//所以我们利用_root来获取这棵树的根节点

	RBTreeInterator(Node* node, Node* root)
		:_node(node)
		,_root(root)
	{ }

	Self& operator++()
	{
		if (_node->_right)
		{
			//结点右子树不为空，则中序下一个访问结点就是右子树的最左(最小)结点
			Node* minright = _node->_right;
			while (minright->_left)
			{
				minright = minright->_left;
			}
			_node = minright;
			return *this;
		}
		else
		{
			//结点右子树为空，则我们需要一直往上查找，直到孩子在父亲的左边停止，此时的父亲就是中序下一个访问结点
			Node* cur = _node;
			Node* father = cur->_father;
			while (father && father->_right == cur)
			{
				cur = father;
				father = cur->_father;
			}
			_node = father;
			return *this;
		}
	}

	Self& operator--()
	{
		if(_node == nullptr) // end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点 
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
			return *this;
		}
		else if (_node->_left)
		{
			//结点左子树不为空，则中序上一个访问结点就是左子树的最右(最大)结点
			Node* minleft = _node->_left;
			while (minleft->_right)
			{
				minleft = minleft->_right;
			}
			_node = minleft;
			return *this;
		}
		else
		{
			//结点左子树为空，则我们需要一直往上查找，直到孩子在父亲的右边停止，此时的父亲就是中序上一个访问结点
			Node* cur = _node;
			Node* father = cur->_father;
			while (father && father->_left == cur)
			{
				cur = father;
				father = cur->_father;
			}
			_node = father;
			return *this;
		}
	}

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

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

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

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

// RBTree<K, pair<K, V>> _tree; -> // map
// RBTree<K, K> _tree; ->		   // set

// 封装红黑树
template<class K, class T, class KeyofT>
// K：find/erase时的key类型（统一接口参数）
// T：红黑树节点存储的实际数据类型（set为 K，map为 pair<const K, V>）
// KeyofT：仿函数，从T中提取K（解决T类型不统一的比较问题）
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeInterator<T, T&, T*> Iterator;
	typedef RBTreeInterator<T, const T&, const T*> ConstIterator;
	
	Iterator Begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur, _root);
	}

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

	ConstIterator Begin() const
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return ConstIterator(cur, _root);
	}

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

	//bool Insert(const T& data)
	pair<Iterator, bool> Insert(const T& data)//为了实现map的[]我们需要修改Insert的返回类型
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			//return true;

			//return pair<Iterator, bool>(Iterator(_root, _root), true);
			return { Iterator(_root, _root), true };//隐式类型转换
		}

		KeyofT kof;
		//创建一个比较对象，将对象像函数一样使用( 重载operator() )
		Node* cur = _root;
		Node* father = nullptr;
		while (cur)
		{
			//根据是map还是set来调用对应的仿函数获取比较大小的值
			//map就是获取kv.first；set就是获取key
			if(kof(cur->_data) < kof(data))
			{
				father = cur;
				cur = cur->_right;
			}
			else if(kof(cur->_data) > kof(data))
			{
				father = cur;
				cur = cur->_left;
			}
			else
			{
				//return false;
				return { Iterator(cur, _root), false };
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		//提前记录cur(插入数据)的位置，后续旋转等操作cur会发生变化，为了返回的时候能找到插入数据的位置

		if (kof(father->_data) < kof(data))
		{
			father->_right = cur;
		}
		else
		{
			father->_left = cur;
		}
		cur->_father = father;

		while (father && father->_col == RED)
		{
			Node* grandfather = father->_father;
			if (grandfather->_left == father)
			{
				//     g
				//   p    u
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					// 情况一：uncle存在且为红色
					// 变色+继续向上处理
					father->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					father = cur->_father;
					//若此时grandfather为根节点则father为空需要结束判断，则可以在循环条件中加上father判空
				}
				else
				{
					if (father->_left == cur) // 单旋+变色
					{
						//     g
						//   p    u
						// c
						//cur在father左边则进行右单旋
						RotateR(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 双旋+变色
					{
						//     g
						//   p    u
						//    c
						//cur在father右边则进行左右双旋
						RotateL(father);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				//uncle结点在father左侧的核心操作和上面基本一致
				//     g
				//   u    p
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = father->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					father = cur->_father;
				}
				else
				{
					if (father->_right == cur) // 单旋+变色
					{
						//     g
						//   u    p
						//         c
						//cur在father右边则进行左单旋
						RotateL(grandfather);
						father->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 双旋+变色
					{
						//     g
						//   u    p
						//       c
						//cur在father左边则进行右左单旋
						RotateR(father);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		//return true;
		return { Iterator(newnode, _root), true };
	}

	//红黑树的查找Find
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;  // 找到，返回节点指针
			}
		}
		return nullptr;  // 未找到
	}

	//红黑树的结点总数size()
	int size()
	{
		return _size(_root);
	}

	//红黑树的高度height()
	int height()
	{
		return _height(_root);
	}

private:
	//右单旋
	void RotateR(Node* father)
	{
		Node* subL = father->_left;
		Node* subLR = subL->_right;
		Node* prev_father = father->_father;

		subL->_right = father;
		father->_father = subL;
		father->_left = subLR;
		if (subLR)
		{
			subLR->_father = father;
		}

		if (prev_father == nullptr)
		{
			_root = subL;
			_root->_father = nullptr;
		}
		else
		{
			if (prev_father->_left == father)
			{
				prev_father->_left = subL;
				subL->_father = prev_father;
			}
			else
			{
				prev_father->_right = subL;
				subL->_father = prev_father;
			}
		}
	}

	//左单旋
	void RotateL(Node* father)
	{
		Node* subR = father->_right;
		Node* subRL = subR->_left;
		Node* prev_father = father->_father;

		subR->_left = father;
		father->_father = subR;
		father->_right = subRL;
		if (subRL)
		{
			subRL->_father = father;
		}

		if (prev_father == nullptr)
		{
			_root = subR;
			_root->_father = nullptr;
		}
		else
		{
			if (prev_father->_left == father)
			{
				prev_father->_left = subR;
				subR->_father = prev_father;
			}
			else
			{
				prev_father->_right = subR;
				subR->_father = prev_father;
			}
		}
	}

	int _size(const Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return _size(root->_left) + _size(root->_right) + 1;
	}

	int _height(const Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int left_h = _height(root->_left);
		int right_h = _height(root->_right);
		return left_h > right_h ? left_h + 1 : right_h + 1;
	}

private:
	Node* _root = nullptr;
};

Mymap.h:

#include"RBTree.h"

namespace xiaoye
{
	template<class K, class V>
	class Mymap
	{
		//仿函数：从T（pair<const K, V>）中提取key
		struct MapKeyofT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		//因为RBTree中的insert需要比较大小，虽然pair自带比较大小的接口，但是比较逻辑不是我们想要的
		//pair自带的比较大小逻辑是先比较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;
		//一定要注意：下面的成员变量类型为了使迭代器不支持修改Key加上const修饰
		//则这里也需要同步修改，否则下面begin/end函数的返回类型会不匹配。
		//如果这里不修改则会导致 return _tree.Begin()返回类型是 RBTree<K, pair<const K, V>, MapKeyofT>
		//而函数返回类型iterator为 RBTree<K, pair<const K, V>, MapKeyofT>

		iterator begin()
		{
			return _tree.Begin();
		}

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

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

		const_iterator end() const
		{
			return _tree.Begin();
		}

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

		//利用Insert接口实现operator[]
		V& operator[](const K& Key)
		{
			pair<iterator, bool> ret = _tree.Insert({ Key, V() });
			return ret.first->second;
			//ret.first为迭代器iterator
			//通过迭代器来获取value值
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyofT> _tree;
		//虽然map的迭代器支持Value的修改，但是不支持Key的修改，不管是普通迭代器还是const迭代器
		//所以我们只需要将RBTree的第二个参数修改为pair<const K, V>即可
	};
}

Myset.h:

#include"RBTree.h"

namespace xiaoye
{
	template<class K>
	class Myset
	{
		// 仿函数：从T（const K）中提取key
		struct SetKeyofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetKeyofT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyofT>::ConstIterator const_iterator;
		//一定要注意：下面的成员变量类型为了使迭代器不支持修改加上const修饰
		//则这里也需要同步修改，否则下面begin/end函数的返回类型会不匹配。
		//如果这里不修改则会导致 return _tree.Begin()返回类型是 RBTree<K, const K, SetKeyofT>
		//而函数返回类型iterator为 RBTree<K, const K, SetKeyofT>

		iterator begin()
		{
			return _tree.Begin();
		}

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

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

		const_iterator end() const
		{
			return _tree.Begin();
		}

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


	private:
		RBTree<K, const K, SetKeyofT> _tree;
		//因为set的iterator迭代器是不支持修改的，不管是普通迭代器还是const迭代器
		//const本来就不支持修改，那普通迭代器怎么实现呢？
		//我们可以把RBTree的第二个参数用const修饰
		//这样RBTree的模板参数T就会变成const K，
		//而T就是来影响迭代器interator的实例化的(typedef RBTreeInterator<T, T&, T*> Iterator;)
	};
}

Test.cpp:

#include"Mymap.h"
#include"Myset.h"

void test_set()
{
	xiaoye::Myset<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(3);
	s.insert(4);
	s.insert(2);

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

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

	//利用正向迭代器实现反向迭代器的逻辑(operator--)
	xiaoye::Myset<int>::iterator rit = s.end();
	while (rit != s.begin())
	{
		//这里非常巧妙，因为一开始rit为 s.end() 也就是空，空是不能解引用的
		//所以我们可以先--rit获取到set中序的最后一个位置，避免访问空
		//当rit为 s.begin() 的前一个位置时，先--rit就可以获取到set中序的第一个位置的数据了
		--rit;
		cout << *rit << " ";
	}
}

void test_map()
{
	xiaoye::Mymap<string, string> dict;
	dict.insert({ "sort", "排序" });
	dict.insert({ "left", "左边" });
	dict.insert({ "right", "右边" });

	xiaoye::Mymap<string, string>::iterator mit = dict.begin();
	while (mit != dict.end())
	{
		cout << mit->first << ":" << mit->second << endl;
		++mit;
	}
	cout << endl;

	dict["left"] = "左边、剩余";
	dict["insert"] = "插入";
	for (auto e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
}
int main()
{
	cout << "测试set:" << endl;
	test_set();
	cout << endl;
	cout << "------------------" << endl;
	cout << "测试map:" << endl;
	test_map();
	return 0;
}

结束语

到此，通过封装红黑树来模拟实现 myMap 和 mySet 就讲解完了。myMap 和 mySet 的封装核心是红黑树的泛型复用：通过模板参数 T 适配不同数据类型，用仿函数 KeyofT 统一 key 提取逻辑，再通过迭代器封装实现双向遍历。其中，key 不可修改的约束、map 的 [] 运算符重载、迭代器的 ++/-- 实现，都是 STL 容器设计的经典细节。掌握这套封装逻辑，不仅能理解 STL 容器的底层实现，更能学会 “泛型编程 + 接口抽象” 的设计思想。希望对大家学习C++能有所收获！

C++参考文档：
https://legacy.cplusplus.com/reference/
https://zh.cppreference.com/w/cpp
https://en.cppreference.com/w/

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

基于深度确定性策略梯度算法（DDPG）强化学习的滑模控制（SMC）自适应调参优化算法Simulink仿真

在复杂非线性系统控制领域，单一控制算法往往难以兼顾控制精度、鲁棒性与自适应能力，因此算法融合成为提升控制性能的重要方向。深度确定性策略梯度算法（DDPG）作为强化学习领域中经典的基于策略的算法，其核心优势在于能够适配连续动作空间的决策问题，无需依赖系统精确模型，具备自主探索与学习优化的能力，可通过与环境的实时交互不断调整策略，实现目标优化。

AtomGit开源社区

Agent Harness，硅谷爆火的全新AI技术框架

Harness将与领域本体深度结合，将行业本体的规则、约束直接内置到Harness的校验层，实现业务规则的机器可执行化，进一步提升Agent在垂直行业的确定性与合规性，这也是金融、政务等强监管场景的核心发展方向。，子Agent的工作内容不会污染主Agent的核心上下文，大幅提升token效率；违规行为的自动拦截与告警；：未来将出现专门的HaaS厂商，提供开箱即用的、针对不同垂直场景的Harness