🔥个人主页：胡萝卜3.0

📖个人专栏：  《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题

《Linux系统编程》

⭐️人生格言：不试试怎么知道自己行不行

---

🎥胡萝卜3.0🌸的简介：

​

---

目录

一、源码及框架结构

二、set与map的设计解析：基于同一红黑树的封装策略

2.1 设计基石：理解底层红黑树架构

2.1.1 节点的关键设计：如何同时存储 set 的 Key 与 map 的 pair

2.1.2 模板的艺术：通过模板参数决定容器类型 (T = K 或 T = pair)及insert代码实现

2.2 迭代器的实现：容器访问的桥梁

2.2.1 迭代器实现核心思想

2.2.2 运算符重载：++,*, -> 的实现要点

2.3 key不支持修改的问题

2.3 核心操作的实现

2.3.1 map 的特殊操作：operator[] 的实现

2.3.2 查找操作 (find)：基于键的高效搜索

三、完整代码

结尾

---

一、源码及框架结构

注意：红黑树封装实现set和map这一块的难度还是挺大的，代码逻辑没有什么难度，主要的难度在于它的结构，ok，话不多说，直接开始~

我们先来看一点源码中内容，看看源码中是怎么用红黑树封装实现set和map的~

通过上图，我们总结出一个框架图——

通过对框架的分析，我们可以看到源码中的rb_tree用了一个巧妙的泛型思想实现，rb_tree是实现：

• key的搜索场景；
• key/value的搜索场景

其实不是直接写死的，而是由rb_tree中的第二个模板参数Value决定_rb_tree_node中存储的数据类型

• 如果Value是key的类型，那_rb_tree_node中存的就是一个key
• 如果Value是key_value的类型，那_rb_tree_node中存的就是一个pair<k,v>

set实例化rb_tree时第二个模板参数给的是key，map实例化rb_tree时第二个模板参数给的是pair<const key,T>，这样一棵红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map

ok，那这里还有一个问题：既然rb_tree第二个模板参数Value已经控制了红黑树节点中存储的数据类型，为什么还要传第一个模板参数Key呢？尤其是set，两个模板参数是一样的。

ok，其实这个传第一个模板参数Key是为了find和erase，对于map和set，调用find/erase时的函数参数都是key，所以第一个模板参数是传给find/erase等函数做参数的类型。

• 对于set来说两个参数是一样的
• 但是对于map来说就不一样了，map在调用insert时，传的是key_value的pair对象，但是在调用find/erase时传的是key对象

注意：在平时博主自己写的时候，对于key_value，使用的都是value，但是在源码里面的模板参数是用T代表value，而内部写的value_type不是我们日常key/value场景中说的value，源码中的value_type反而是红黑树节点中存储的真实的数据的类型（吐槽一下，这里有点子混乱）

二、set与map的设计解析：基于同一红黑树的封装策略

2.1 设计基石：理解底层红黑树架构

2.1.1 节点的关键设计：如何同时存储 set 的 Key 与 map 的 pair<Key, Value>

通过对框架的分析，我们可以看到源码中的rb_tree用了一个巧妙的泛型思想实现，rb_tree是实现：

• key的搜索场景；
• key/value的搜索场景

其实不是直接写死的，而是由rb_tree中的第二个模板参数Value决定_rb_tree_node中存储的数据类型

• 如果Value是key的类型，那_rb_tree_node中存的就是一个key
• 如果Value是key_value的类型，那_rb_tree_node中存的就是一个pair<k,v>

set实例化rb_tree时第二个模板参数给的是key，map实例化rb_tree时第二个模板参数给的是pair<const key,T>，这样一棵红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map

2.1.2 模板的艺术：通过模板参数决定容器类型 (T = K 或 T = pair<const K, V>)及insert代码实现

ok，既然我们已经知道源码中是使用第二模板参数来决定我红黑树中存的是什么数据，那我们也可以按照此方法对我们的红黑树进行改造：

• 使用模板，让红黑树中的节点存一个T类型的数据（T是什么类型，底层不知道）

传入第一个模板参数k的原因是——

• 因为find和erase传参传的是key，对于set而言调用insert/find/erase传的k和T的两个参数是一样的，但是对于map而言是不一样的，insert传的是pair，但是find/erase是key

所以我们需要传第一个模板参数！！！

我们现在来看看set和map——

由于 std::map 和 std::set 的底层通常使用红黑树实现，因此在我们自定义的 map 和 set 类中，需要在私有成员区域定义一个红黑树对象作为底层容器。

• map

• set

这时候就很清晰了——

但是这就完了吗？很明显没有，当我们继续往下调整时，就出现了下面的问题：

这里用data比较大小，data是什么，不知道；如果data是key，没有问题；如果data是pair，可能有问题——pair可以进行比较大小，比较的逻辑是：key小就小，key相等，value小就小，这很明显不符合我们的要求。

我们的比较大小仅仅是想比较Key，不是说像pair中的比较大小，这可咋办？

ok，我们可以使用一个仿函数，这个仿函数用来取我们这里的key，set中取得就是Key，map中取的就是pair<k,v>中的first，取出相应的key，我们就可以比较了

ok，那我们就可以在map和set中分别写这么个仿函数，然后传给第三个模板参数——

• map

• set

ok，现在我们来看一下这是怎么调用的——

ok，这样我们插入的相关代码就改好了（后面有需要再做改动）

我们插入一些值运行一下：

2.2 迭代器的实现：容器访问的桥梁

2.2.1 迭代器实现核心思想

这里的iterator实现的大框架跟list的iterator的思路是一致的，用一个类型封装节点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为

但是这里的难点是operator++的实现。在之前的使用部分，我们分析了，map和set的迭代器走的是中序遍历（左子树->根节点->右子树）（可以达到有序的目的），那么begin()就会返回中序中第一个节点的迭代器

所谓中序中的第一个节点：这棵树的最左节点

begin()就会返回这棵树的最左节点所在位置的迭代器

迭代器++的核心逻辑就是——不看全局，只看局部，只考虑当前中序局部要访问的下一个节点

这块我们通过图来看——

• 情况一：访问的根节点（it）的右子树不为空（左子树->根节点->右子树）

（++it）it走的下一个是谁？右子树不为空，就是右子树中的最左节点

总结（重要）：

• 迭代器++时，如果it指向的节点的右子树不为空，代表当前节点已经访问完了，要访问下一个节点是右子树的中序第一个，也就是右子树中的最左节点，所以直接找右子树的最左节点

• 情况二：访问的根节点（it）的右子树为空（左子树->根节点->右子树）

对于访问节点的右子树为空的情景，无论我访问的节点（cur）是cur的父节点的左还是右，我都是去找那个孩子节点是父亲节点的左的那个父亲节点（这个父亲节点就是中序遍历的下一个节点）！！！就停止查找

或者找到我父亲节点是空也停止查找（因为当我的父亲节点是空时，说明我已经是整棵树的根节点了，遍历结束了）

ok，这就是迭代器++的整体思路！！！

2.2.2 运算符重载：++,*, -> 的实现要点

ok，这样我们就可以来封装这个迭代器了~

• RBTree.h

//封装迭代器
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;
	}
	//++
	self& operator++()
	{
		if (_node->_right)
		{
			node* minleft = _node->_right;
			while (minleft->_left)
			{
				minleft = minleft->_left;
			}
			//跳出循环，说明找到右子树中的最左节点，这个节点就是下一个要访问的节点
			_node = minleft;
		}
		else
		{
			node* cur = _node;
			node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const self& s) const
	{
		return _node != s._node;
	}
	bool operator==(const self& s) const
	{
		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;
	Iterator Begin()
	{
		//中序遍历第一个节点是最左节点
		node* minleft = _root;
		while (minleft&&minleft->_left)
		{
			minleft = minleft->_left;
		}
		return Iterator(minleft);
	}
	Iterator End()
	{
		return Iterator(nullptr);
	}
	const_Iterator Begin() const
	{
		//中序遍历第一个节点是最左节点
		node* minleft = _root;
		while (minleft && minleft->_left)
		{
			minleft = minleft->_left;
		}
		return const_Iterator(minleft);
	}
	const_Iterator End() const
	{
		return const_Iterator(nullptr);
	}
};

ok，接下来，我们来使用已经封装好的迭代器分别实现map和set里面的迭代器——

• 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;
	typedef typename RBTree<k, k, SetKeyOft>::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();
	}
	bool insert(const k& key)
	{
		return _t.Insert(key);
	}
private:
	//set的底层是一棵红黑树，所以我们需要这么一棵红黑树
	RBTree<k, k,SetKeyOft> _t;
};

• map.h

template<class k,class v>
class map
{
	struct MapKeyOfT
	{
		const k& operator()(const pair<k, v>& kv)
		{
			return kv.first;
		}
	};
public:
	typedef typename RBTree<k, pair<k, v>, MapKeyOfT>::Iterator iterator;
	typedef typename RBTree<k, pair<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();
	}
	bool insert(const pair<k, v>& kv)
	{
		return _t.Insert(kv);
	}
private:
	//map的底层是一棵红黑树，所以我们需要这么一棵红黑树
	RBTree<k, pair<k,v>, MapKeyOfT> _t;
};

ok，解决完迭代器的问题，接下来，我们要解决就是key不支持修改的问题——

在上面的操作中，无论是set中的key还是map中的key都是可以修改的，但是库中的key是不能修改的，接下来我们来看看如何实现这个——

2.3 key不支持修改的问题

ok，这个问题还是比较容易解决的——

• set

• map

注意：改完上面之后，相应的部分也应该进行改动！！！

2.3 核心操作的实现

2.3.1 map 的特殊操作：operator[] 的实现

operator[]是map的一个重要的接口，通过前面的学习，我们这里就可以很容易实现这个 [ ] 的运算符重载：

• 修改insert的返回值为pair<iterator,bool>

插入成功（说明是第一次出现），返回新插入Key所在的迭代器，true；插入失败（说明不是第一次出现），也返回key所在的迭代器，false

然后再拿出pair<iterator,bool>中的节点iterator（这个指向的是一个pair<key,value>），然后再拿出其中的value

测试一下：

2.3.2 查找操作 (find)：基于键的高效搜索

查找的代码实现还是比较简单的，这里只需要将返回值改为迭代器即可~

• RBTree.h

Iterator Find(const k& key)
{
	node* cur = _root;
	while (cur)
	{
		if (kot(cur->_data) >key)
		{
			cur = cur->_left;
		}
		else if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else
		{
			return Iterator(cur);
		}
	}
	return End();
}

• set.h

iterator find(const k& key)
{
	return _t.Find(key);
}

• map.h

iterator find(const k& key)
{
	return _t.Find(key);
}

三、完整代码

• RBTree.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace carrot
{
	enum colour
	{
		BLACK,
		RED
	};
	template<class T>
	//节点结构，节点中存一个类型是T的数据，T是什么，底层不知道
	struct RBTreeNode
	{
		T _data;//存储数据(底层不知道存的是什么类型的数据)
		RBTreeNode<T>* _left;//指向左孩子的指针
		RBTreeNode<T>* _right;//指向右孩子的指针
		RBTreeNode<T>* _parent;//指向父节点的指针
		colour _col;//记录颜色
		RBTreeNode(const T& data)
			:_data(data)
			, _left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(RED)//默认新插入节点是红色
		{}
	};
	//RBTree<k, k> _t;          -> set
	//RBTree<k, pair<k,v>> _t;  -> map
	//封装迭代器
	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;
		}
		//++
		self& operator++()
		{
			if (_node->_right)
			{
				node* minleft = _node->_right;
				while (minleft->_left)
				{
					minleft = minleft->_left;
				}
				//跳出循环，说明找到右子树中的最左节点，这个节点就是下一个要访问的节点
				_node = minleft;
			}
			else
			{
				node* cur = _node;
				node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		bool operator!=(const self& s) const
		{
			return _node != s._node;
		}
		bool operator==(const self& s) const
		{
			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;
		Iterator Begin()
		{
			//中序遍历第一个节点是最左节点
			node* minleft = _root;
			while (minleft&&minleft->_left)
			{
				minleft = minleft->_left;
			}
			return Iterator(minleft);
		}
		Iterator End()
		{
			return Iterator(nullptr);
		}
		const_Iterator Begin() const
		{
			//中序遍历第一个节点是最左节点
			node* minleft = _root;
			while (minleft && minleft->_left)
			{
				minleft = minleft->_left;
			}
			return const_Iterator(minleft);
		}
		const_Iterator End() const
		{
			return const_Iterator(nullptr);
		}

		KeyOfT kot;//用来把相应的key取出来，然后进行比较
		pair<Iterator,bool> Insert(const T& data)
		{
			if (_root == nullptr)
			{
				_root = new node(data);
				_root->_col = BLACK;//根节点为黑色
				return { Iterator(_root),true };
			}
			node* cur = _root;
			node* parent = nullptr;
			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),false };
				}
			}
			cur = new node(data);
			cur->_col = RED;
			node* newnode = cur;
			if (kot(parent->_data) >kot( data))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;
			//调整颜色
			//如果新插入节点的父节点的颜色是黑色，则插入结束
			//如果新插入节点的父节点的颜色是红色，我们需要调整颜色
			//此时c（红色），p（红色），g（黑色）的颜色已经确定，关键看uncle
			while (parent && parent->_col == RED)//parent为空也要跳出循环
			{
				node* grandfather = parent->_parent;
				//（1）
				//          g（黑色）
				//  p（红色）          u
				//c（红色）
				if (grandfather->_left == parent)
				{
					node* uncle = grandfather->_right;
					//           g（黑色）
					//  p（红色）       u（存在且为红）
					//c（红色）
					//只需变色
					if (uncle && uncle->_col == RED)
					{
						//p和u节点变成黑色，解决连续红色节点问题
						parent->_col = uncle->_col = BLACK;
						//g节点变成红色，解决g的左右子树多了一个黑色节点的问题，使每条路径上的黑色节点数量相等
						grandfather->_col = RED;

						//继续往上更新颜色
						//为什么需要继续往上更新颜色？因为经过上面的更新之后，g的父节点有可能是红色的
						//这样就导致了连续红色节点的问题，需要继续往上更新颜色,直到父节点的颜色是黑色的
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						//uncle节点不存在或者存在且为黑
						//情况1：单旋+变色
						//           g（黑色）
						//  p（红色）       u（不存在或者存在且为黑）
						//c（红色）
						if (parent->_left == cur)
						{
							//右单旋+变色
							//以g为旋转点进行右单旋
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						//情况2：双旋+变色
						//           g（黑色）
						//  p（红色）       u（不存在或者存在且为黑）
						//        c（红色）
						else
						{
							//左右双旋+变色
							//以p为旋转点先进行左单旋，然后再以g为旋转点进行右单旋
							RotateL(parent);
							RotateR(grandfather);
							//变色
							grandfather->_col = RED;
							cur->_col = BLACK;
						}
					}
				}
				//（2）
				//        g（黑色）
				//  u             p（红色）
				//                    c（红色）
				else
				{
					node* uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)
					{
						//           g（黑色）
						// u（存在且为红）      p（红色）
						//                           c（红色）
						//只需变色
						//p和u节点变成黑色，解决连续红色节点问题
						parent->_col = uncle->_col = BLACK;
						//g节点变成红色，解决g的左右子树多了一个黑色节点的问题，使每条路径上的黑色节点数量相等
						grandfather->_col = RED;

						//继续往上更新颜色
						//为什么需要继续往上更新颜色？因为经过上面的更新之后，g的父节点有可能是红色的
						//这样就导致了连续红色节点的问题，需要继续往上更新颜色,直到父节点的颜色是黑色的
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						//           g（黑色）
						// u（不存在或者存在且为黑）      p（红色）
						//                                     c（红色）
						//c是p的右
						if (parent->_right == cur)
						{
							//左单旋+变色
							RotateL(grandfather);
							grandfather->_col = RED;
							parent->_col = BLACK;
						}
						else
						{
							//           g（黑色）
							// u（不存在或者存在且为黑）      p（红色）
							//                           c（红色）
							//c是p的左
							//右左双旋+变色
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
					}
				}
			}
			//无论根是黑色还是红色，我们都直接让根变成黑色
			//uncle存在且为红的情况中，根节点可能变成红色，可以进行判断（但是有点麻烦）
			_root->_col = BLACK;
			return { Iterator(newnode),true };
		}
		//右单旋
		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 = subL;
			//若parent是根节点
			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				//parent不是根节点
				if (parentParent->_left == parent)
				{
					parentParent->_left = subL;
				}
				else
				{
					parentParent->_right = subL;
				}
				subL->_parent = parentParent;
			}
		}
		//左单旋
		void RotateL(node* parent)
		{
			node* subR = parent->_right;
			node* subRL = subR->_left;
			subR->_left = parent;
			node* parentParent = parent->_parent;
			parent->_right = subRL;
			parent->_parent = subR;
			if (subRL)
				subRL->_parent = parent;
			//让subR成为新的整棵树的根节点/子树的根节点
			if (parent == _root)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parentParent->_left == parent)
				{
					parentParent->_left = subR;
				}
				else {
					parentParent->_right = subR;
				}
				subR->_parent = parentParent;
			}
		}
		Iterator Find(const k& key)
		{
			node* cur = _root;
			while (cur)
			{
				if (kot(cur->_data) >key)
				{
					cur = cur->_left;
				}
				else if (kot(cur->_data) < key)
				{
					cur = cur->_right;
				}
				else
				{
					return Iterator(cur);
				}
			}
			return End();
		}
		int Size()
		{
			return _Size(_root);
		}
		int TreeHigh()
		{
			return _TreeHigh(_root);
		}
	private:
		int _TreeHigh(node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			int lefthigh = _TreeHigh(root->_left);
			int righthigh = _TreeHigh(root->_right);
			return 1 + (lefthigh > righthigh ? lefthigh : righthigh);
		}
		int _Size(node* root)
		{
			if (root == nullptr)
			{
				return 0;
			}
			return _Size(root->_left) + _Size(root->_right) + 1;
		}
		node* _root = nullptr;
	};
}

• map.h

#pragma once
#include"RBTree.h"
namespace carrot
{
	template<class k,class v>
	class map
	{
		struct MapKeyOfT
		{
			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>::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();
		}
		iterator find(const k& key)
		{
			return _t.Find(key);
		}
		pair<iterator, bool> insert(const pair<k, v>& kv)
		{
			return _t.Insert(kv);
		}
		v& operator[](const k& key)
		{
			pair<iterator, bool> ret = insert({ key, v() });
			return ret.first->second;
		}
	private:
		//map的底层是一棵红黑树，所以我们需要这么一棵红黑树
		RBTree<k, pair<const k,v>, MapKeyOfT> _t;
	};
}

• set.h

#pragma once
#include"RBTree.h"
namespace carrot
{
	template<class k>
	class set
	{
		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>::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();
		}
		iterator find(const k& key)
		{
			return _t.Find(key);
		}
		pair<iterator,bool> insert(const k& key)
		{
			return _t.Insert(key);
		}
	private:
		//set的底层是一棵红黑树，所以我们需要这么一棵红黑树
		RBTree<k, const k,SetKeyOft> _t;
	};
}

• test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include"set.h"
#include"map.h"
namespace carrot
{
	void func(const set<int>& s)
	{
		set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			//*it = 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void test_set()
	{
		set<int> s;
		s.insert(1);
		s.insert(3);
		s.insert(5);
		s.insert(20);
		set<int>::iterator it = s.begin();
		//*it = 1;//key不能修改
		while (it != s.end())
		{
			
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto& e : s)
		{
			cout << e << " ";
		}
		func(s);
	}
	void func2(const map<string, string>& dict)
	{
		map<string, string>::const_iterator it = dict.begin();
		while (it != dict.end())
		{
			//it->first += 'x';
			//it->second += 'x';
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
	void test_map()
	{
		//map<string, string> dict;
		//dict.insert({ "string","字符串" });
		//dict.insert({ "left","左边" });
		//dict.insert({ "right","右边" });
		//map<string, string>::iterator it = dict.begin();
		//while (it != dict.end())
		//{
		//	//it->first += 'x';//key不能修改
		//	it->second += 'x';
		//	cout << it->first << ":" << it->second << endl;
		//	++it;
		//}
		//cout << endl;
		//for (auto& [k, v] : dict)
		//{
		//	cout << k << ":" << v << endl;
		//}
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		map<string, int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}
		for (auto& [k, v] : countMap)
		{
			cout << k << ":" << v << endl;
		}
		cout << endl;
		/*for (auto& e : arr)
		{
			auto it = countMap.find(e);
			if (it != countMap.end())
			{
				it->second++;
			}
			else
			{
				countMap.insert({ e, 1 });
			}
		}*/
	}
}
int main()
{
	//carrot::test_set();
	carrot::test_map();
	return 0;
}

结尾

ok，写到这，我们就知道如何用一棵红黑树同时实现set与map了，对于这一块的内容还是比较难的，各位uu在学的时候，可以半写半看，面试的时候也不会让你手搓这部分代码的，知道其中的细节部分即可~~~

那请大佬不要忘记给博主来个赞哦！ 

૮₍ ˶ ˊ ᴥ ˋ˶₎ა

​