模拟实现map和set超详解（C++）

 hello！我是bug。今天我们来讲讲map和set的相关内容：
（代码可能会有一点问题，请各位老铁指正   ）

• 前言
• 一、map
• 二、set
• 三、红黑树
• 四、map的模拟实现
• 五、set的模拟实现
• 六、测试代码

 Map 和 Set 是一种专门用来进行搜索的容器或者数据结构，因为其底层是红黑树，所以其增删查改的时间复杂度都是O（logN），其效率是很高的。而且由于红黑树遵循搜索二叉树的规则，map和set遍历时可以间接进行排序。

 Map：是STL 的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。
其底层一般是红黑树，当然AVL树也可以。通过对红黑树包装来实现map。

 map的相关接口：

  map常用功能：可以实现字典、统计数量 。

 Set ：集合，和map类似。区别在于：map存储的是键对值（KV模型），而set存储的是key值（K模型）。
set和map的底层都是红黑树，它们都是对同一棵红黑树进行包装。

 set的相关接口：

 红黑树实现代码⬇️ ⬇️：

#pragma once
#include
#include
#include

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::make_pair;
using std::pair;

enum Colour { RED, BLACK, };

namespace lz
{
	template
	struct PairSelect1st
	{
		const K& operator()(const pair& kv) { return kv.first; }
	};

	template
	struct KSelect1st
	{
		const K& operator()(const K& key) { return key; }
	};

	template
	struct RBTreeNode
	{
		typedef RBTreeNode* pNode;
		typedef RBTreeNode Node;

		//三叉链
		pNode _left;
		pNode _right;
		pNode _parent;

		//颜色,红黑树不需要平衡因子
		Colour _col;
		T _data;

		RBTreeNode(const T& data, Colour col = RED)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _col(col)
			, _data(data)
		{}
	};

	template
	struct Iterator
	{
		typedef RBTreeNode* pNode;
		typedef RBTreeNode Node;
		typedef Iterator Self;
		typedef Ref Reference;
		typedef const Ref const_Reference;
		typedef Ptr Pointer;
		typedef const Ptr const_Pointer;

	public:
		Iterator(pNode pnode = nullptr)
			:_pnode(pnode)
		{}

		pNode _pnode;

		Reference operator*() { return _pnode->_data; }
		const_Reference operator*()const { return _pnode->_data; }
		Pointer operator->() { return &(operator*()); }
		const_Pointer operator->()const { return &(operator*()); }
		bool operator!=(const Self& s)const { return s._pnode != _pnode; }
		bool operator==(const Self& s)const { return s._pnode == _pnode; }

		void increasement()
		{
			//如果右子树存在，那么我们去访问右子树的最左结点
			//也就是中序的第一个结点。
			if (_pnode->_right)
			{
				pNode left = _pnode->_right;
				while (left->_left)
				{
					left = left->_left;
				}

				_pnode = left;
			}
			else //cur的右子树为NIL,上溯查找
			{
				//如果父亲为空，则_pnode为根结点父亲不为空，
				//那么就向上去找不是父亲右孩子的结点，它的父亲就是我们要访问的结点
				pNode cur = _pnode;
				pNode parent = cur->_parent;
				while (parent && cur == parent->_right)
				{
					cur = parent;
					parent = parent->_parent;
				}

				_pnode = parent;
			}
		}

		void decreasement()
		{
			if (_pnode->_left)
			{
				//左子树不为空，去找左子树的最右结点
				pNode right = _pnode->_left;
				while (right->_right)
				{
					right = right->_right;
				}

				_pnode = right;
			}
			else//cur的左子树不存在,上溯查找父亲
			{
				//如果去找不是父亲左孩子的结点，它的父亲就是我们要访问的结点
				pNode cur = _pnode;
				pNode parent = cur->_parent;
				while (parent && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}

				_pnode = parent;
			}
		}

		Self& operator++() { increasement(); return *this; }
		Self& operator--() { decreasement(); return *this; }
		Self operator++(int)
		{
			pNode tmp = _pnode; increasement(); return tmp;
		}
		Self operator--(int)
		{
			pNode tmp = _pnode; decreasement(); return tmp;
		}

	};

	//反向迭代器(迭代器适配器：里面封装了正向迭代器)
	template
	struct reverse_iterator
	{
		typedef typename Iterator::Reference Reference;
		typedef typename Iterator::const_Reference const_Reference;
		typedef typename Iterator::Pointer Pointer;
		typedef typename Iterator::const_Pointer const_Pointer;
		typedef reverse_iterator Self;

		reverse_iterator(Iterator it)
			:_it(it)
		{}

		Reference operator*() { return *_it; }
		const_Reference operator*()const { return *_it; }
		Pointer operator->() { return &operator* (); }
		const_Pointer operator->()const { return *operator* (); }

		Self& operator++() { --_it; return *this; }
		Self operator++(int) { Iterator tmp = _it--; return tmp; }
		Self& operator--() { ++_it; return *this; }
		Self operator--(int) { Iterator tmp = _it++; return tmp; }
		bool operator!=(const Self& s)const { return _it != s._it; }
		bool operator==(const Self& s)const { return _it == s._it; }

		Iterator _it;
	};

	template
	struct RBTree
	{
		typedef RBTree Self;
		typedef RBTreeNode* pNode;
		typedef RBTreeNode Node;
		typedef Iterator tree_iterator;
		typedef
			Iterator tree_const_iterator;
		typedef reverse_iterator tree_reverse_iterator;
		typedef reverse_iterator tree_const_reverse_iterator;

	private:
		pNode _root;

	public:
		RBTree()
			:_root(nullptr)
		{}

		//正向迭代器
		tree_iterator begin()
		{
			if (_root == nullptr)
				return tree_iterator(nullptr);

			pNode cur = _root;
			while (cur->_left)
				cur = cur->_left;
			return tree_iterator(cur);
		}
		tree_iterator end() { return tree_iterator(nullptr); }

		tree_const_iterator cbegin()const
		{
			if (_root == nullptr)
				return tree_const_iterator(nullptr);

			pNode cur = _root;
			while (cur->_left)
				cur = cur->_left;
			return tree_const_iterator(cur);
		}
		tree_const_iterator cend()const { return tree_const_iterator(nullptr); }

		//反向迭代器
		tree_reverse_iterator rend()
		{
			return tree_reverse_iterator(tree_iterator(nullptr));
		}
		tree_reverse_iterator rbegin()
		{
			if (_root == nullptr)
				return tree_reverse_iterator(nullptr);

			pNode cur = _root;
			while (cur->_right)
				cur = cur->_right;
			return tree_reverse_iterator(tree_iterator(cur));
		}

		tree_const_reverse_iterator crend()const
		{
			return tree_const_reverse_iterator(tree_const_iterator(nullptr));
		}
		tree_const_reverse_iterator crbegin()const
		{
			if (_root == nullptr)
				return tree_const_reverse_iterator(nullptr);

			pNode cur = _root;
			while (cur->_right)
				cur = cur->_right;
			return tree_const_reverse_iterator(tree_const_iterator(cur));
		}

		//内部拷贝
		void _CopyTree(const pNode& root)
		{
			if (root == nullptr)
				return;

			insert(root->_data);

			_CopyTree(root->_left);
			_CopyTree(root->_right);
		}

		//拷贝构造函数
		RBTree(const Self& t)
		{
			_root = nullptr;
			_CopyTree(t._root);
		}

		void clear() { _clear(_root); _root = nullptr; }//删除之后置空

		void _clear(pNode& root)
		{
			if (root == nullptr)
				return;

			_clear(root->_left);
			_clear(root->_right);
			delete root;
		}

		~RBTree()
		{
			_clear(_root);
		}

		//对=进行重载
		Self& operator=(const Self& t)
		{
			Self tmp(t);
			std::swap(tmp._root, _root);
			return *this;
		}

		//查找
		tree_iterator find(const T& data)const
		{
			Select1st slt;
			if (_root == nullptr)
				return tree_iterator(nullptr);

			pNode cur = _root;
			while (cur)
			{
				if (slt(cur->_data) > slt(data))
					cur = cur->_left;
				else if (slt(cur->_data) < slt(data))
					cur = cur->_right;
				else
					return tree_iterator(cur);
			}

			return tree_iterator(nullptr);
		}

		//插入数据
		pair insert(const T& data)
		{
			Select1st slt;
			//如果根节点为空
			if (_root == nullptr)
			{
				_root = new Node(data, BLACK);
				return make_pair(tree_iterator(_root), true);
			}

			//如果根节点不为空,去找插入位置
			pNode cur = _root;
			pNode parent = _root;
			while (cur)
			{
				//如果cur中的key大于kv中的key，去左边找
				if (slt(cur->_data) > slt(data))
				{
					parent = cur;
					cur = cur->_left;
				}
				//如果cur中的key小于kv中的key，去右边找
				else if (slt(cur->_data) < slt(data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else//找到了和插入数据的key相同的数据，插入失败
					//同时返回原有数据的的指针
					return make_pair(tree_iterator(cur), false);
			}

			pNode newNode = new Node(data);
			cur = newNode;
			//找到了插入的位置，判断位置是在parent左边还是右边
			if (slt(parent->_data) > slt(data))
			{
				newNode->_parent = parent;
				parent->_left = newNode;
			}
			else if (slt(parent->_data) < slt(data))
			{
				newNode->_parent = parent;
				parent->_right = newNode;
			}

			//插入完成
			//开始进行平衡操作（变色+旋转）

			//如果parent存在：《1》parent为BLACK，不操作
			//《2》parent为RED，如果uncle为RED，直接把uncle和parent变红
			//如果uncle为BLACK或者不存在，进行旋转和变色
			while (parent && parent->_col == RED)
			{
				pNode grandFather = parent->_parent;

				//注意！！这里grandFather一定存在，因为parent为红色结点，如果
				//grandFather不存在，parent就是根节点，违反了规则。

				//如果parent是grandFather的左孩子
				if (grandFather->_left == parent)
				{
					//如果uncle不为空而且为红色，uncle和parent直接变黑
					pNode uncle = grandFather->_right;
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;

						cur = grandFather;
						parent = grandFather->_parent;
					}
					//如果uncle为空或者uncle不为空且为而且为黑色
					else
					{
						//如果cur是parent的左孩子,进行右单旋+变色
						//如果这里grandFather是根节点，
						//则parent最后要变成黑色，最后调整
						if (parent->_left == cur)
						{
							RotateR(parent->_parent);
							parent->_col = BLACK;
							grandFather->_col = RED;
							break;
						}
						//如果cur是parent的右孩子,进行左右双旋+变色
						//如果这里grandFather是根节点，
						//则cur最后要变成黑色，最后调整
						else if (parent->_right == cur)
						{
							RotateL(parent);
							RotateR(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
							break;
						}
					}
				}
				//如果parent是grandFather的右孩子,和上面情况类似
				else if (grandFather->_right == parent)
				{
					pNode uncle = grandFather->_left;
					//如果uncle存在，而且为红色
					if (uncle && uncle->_col == RED)
					{
						parent->_col = BLACK;
						uncle->_col = BLACK;
						grandFather->_col = RED;
						//继续往上处理
						cur = grandFather;
						parent = grandFather->_parent;
					}
					//uncle不存在，或者存在为黑色
					else
					{
						//如果cur是parent的右孩子
						if (parent->_right == cur)
						{
							RotateL(parent->_parent);
							parent->_col = BLACK;
							grandFather->_col = RED;
							break;
						}
						//cur是parent的左孩子
						else if (parent->_left == cur)
						{
							RotateR(parent);
							RotateL(grandFather);
							cur->_col = BLACK;
							grandFather->_col = RED;
							break;
						}
					}
				}
			}

			_root->_col = BLACK;
			return make_pair(tree_iterator(newNode), true);
		}

		//右单旋
		void RotateR(pNode parent)
		{
			pNode grandFather = parent->_parent;
			pNode subL = parent->_left;
			pNode subLR = subL->_right;

			if (subLR)
				subLR->_parent = parent;

			subL->_right = parent;
			subL->_parent = grandFather;
			parent->_parent = subL;
			parent->_left = subLR;

			//如果parent是根节点
			if (parent == _root)
				_root = subL;
			else//如果parent不是根节点	
			{
				//如果parent是grandFather左孩子
				if (grandFather->_left == parent)
					grandFather->_left = subL;
				else if (grandFather->_right == parent)
					grandFather->_right = subL;
			}
		}

		//左单旋
		void RotateL(pNode parent)
		{
			pNode grandFather = parent->_parent;
			pNode subR = parent->_right;
			pNode subRL = subR->_left;

			if (subRL)
				subRL->_parent = parent;

			subR->_left = parent;
			subR->_parent = grandFather;
			parent->_parent = subR;
			parent->_right = subRL;

			if (parent == _root)
				_root = subR;
			else
			{
				if (grandFather->_left == parent)
					grandFather->_left = subR;
				else if (grandFather->_right == parent)
					grandFather->_right = subR;
			}
		}

		//进行删除结点
		void deleteNode(pNode node)
		{
			if (node == nullptr)
				return;

			pNode replace = nullptr;
			pNode parent = nullptr;
			// 存在两个孩子结点
			if (node->_left != nullptr && node->_right != nullptr)
			{
				pNode left = node->_right;
				while (left && left->_left)
					left = left->_left;

				node->_data = left->_data;//覆盖值
				deleteNode(left);//递归删除，只可能递归一次
				return;
			}
			else
			{
				//有一个孩子结点或者没有孩子结点
				// 判断删除的结点是否是根结点
				if (node->_parent == nullptr)
				{
					this->_root =
						(node->_left != nullptr ? node->_left : node->_right);
					replace = this->_root;
					if (this->_root != nullptr)
						this->_root->_parent = nullptr;
				}
				else
				{
					// 不是根结点	
					pNode child =
						(node->_left != nullptr ? node->_left : node->_right);
					if (node->_parent->_left == node)
						node->_parent->_left = child;
					else
						node->_parent->_right = child;

					if (child != nullptr)
						child->_parent = node->_parent;
					replace = child;
					parent = node->_parent;
				}
			}
			//红色结点直接删除，不用处理
			if (node->_col == BLACK)
				_deleteFixUp(replace, parent);
		}

		//修复颜色
		void _deleteFixUp(pNode replace, pNode parent)
		{
			pNode brother = nullptr;
			//parent不是空结点，代替结点是黑色结点时
			while ((replace == nullptr || replace->_col == BLACK)
				&& replace != this->_root)
			{
				if (parent->_left == replace)
				{
					brother = parent->_right;
					// 兄弟结点是红色结点，兄弟结点变黑，父亲结点变红
					//parent左旋，replace的兄弟变成了黑色
					if (brother->_col == RED)
					{
						brother->_col = BLACK;
						parent->_col = RED;
						RotateL(parent);
						brother = parent->_right;
					}
					// 经过上面，不管进没进if，兄弟都成了黑色
					// 兄弟结点是黑色结点，兄弟的两个孩子结点也是黑色
					if ((brother->_left == nullptr
						|| brother->_left->_col == BLACK)
						&& (brother->_right == nullptr
							|| brother->_right->_col == BLACK))
					{
						// 如果parent此时为红，把兄弟结点和父亲结点交换颜色
						if (parent->_col == RED)
						{
							parent->_col = BLACK;
							brother->_col = RED;
							break;
						}
						else
						{
							//parent为黑，先把兄弟结点变红保持子树平衡，
							//然后向上调整
							brother->_col = RED;
							replace = parent;
							parent = replace->_parent;
						}
					}
					else
					{
						//兄弟结点是黑色结点，左孩子存在且为红色结点
						if (brother->_left != nullptr && brother->_left->_col == RED)
						{
							brother->_left->_col = parent->_col;
							parent->_col = BLACK;
							RotateR(brother);
							RotateL(parent);
						}
						//兄弟结点是黑色结点，右孩子存在且为红色结点
						else if (brother->_right != nullptr
							&& brother->_right->_col == RED)
						{
							brother->_col = parent->_col;
							parent->_col = BLACK;
							brother->_right->_col = BLACK;
							RotateL(parent);
						}
						break;
					}
				}
				else
				{
					//对称情况
					brother = parent->_left;
					//兄弟结点是红色结点,兄弟结点变黑，父亲结点变红
					//parent右旋，replace的兄弟结点变成了黑色
					if (brother->_col == RED)
					{
						brother->_col = BLACK;
						parent->_col = RED;
						RotateR(parent);
						brother = parent->_left;
					}
					// 经过上面，不管进没进if，兄弟结点都成了黑色
					// 兄弟结点是黑色结点，兄弟的两个孩子结点也是黑色
					if ((brother->_left == nullptr
						|| brother->_left->_col == BLACK)
						&& (brother->_right == nullptr
							|| brother->_right->_col == BLACK))
					{
						// 如果parent此时为红，把兄弟结点和父亲结点交换颜色
						if (parent->_col == RED)
						{
							parent->_col = BLACK;
							brother->_col = RED;
							break;
						}
						else
						{
							//parent为黑，先把兄弟结点变红保持子树平衡，
							//然后向上调整
							brother->_col = RED;
							replace = parent;
							parent = replace->_parent;
						}
					}
					else
					{
						//兄弟结点是黑色结点，左孩子存在且为红色结点
						if (brother->_right != nullptr
							&& brother->_right->_col == RED)
						{
							brother->_right->_col = parent->_col;
							parent->_col = BLACK;
							RotateL(brother);
							RotateR(parent);
						}
						//兄弟结点是黑色结点，右孩子存在且为红色结点
						else if (brother->_left != nullptr
							&& brother->_left->_col == RED)
						{
							brother->_col = parent->_col;
							parent->_col = BLACK;
							brother->_left->_col = BLACK;
							RotateR(parent);
						}
						break;
					}
				}
			}
			//删除结点只有一个孩子结点，如果是根，将其涂黑。
			if (replace != nullptr)
				replace->_col = BLACK;
		}

		//中序遍历,map
		void _InOder(const pNode& root)
		{
			if (root == nullptr)
				return;

			_InOder(root->_left);
			cout << root->_data.first << " : " << root->_data.second << endl;
			_InOder(root->_right);
		}

		void InOder()
		{
			if (_root == nullptr)
				return;

			_InOder(_root);
		}

		//测试RBTee是否错误
		bool _IsRBTree(const Node* root, int blackCount, int count)
		{
			if (root == nullptr)
			{
				if (count != blackCount)
				{
					cout << "黑色节点的个数不一致" << endl;
					return false;
				}
				return true;
			}

			//判断红色节点的parent是否是红色节点
			if (root->_col == RED && root->_parent->_col == RED)
			{
				cout << "有连续的红色结点" << endl;
				return false;
			}

			//黑色节点时，++
			if (root->_col == BLACK)
				count++;

			return _IsRBTree(root->_left, blackCount, count)
				&& _IsRBTree(root->_right, blackCount, count);
		}

		bool IsRBTree()
		{
			if (_root == nullptr)
				return true;

			pNode cur = _root;
			//参考值
			int blackCount = 0;
			while (cur)
			{
				//统计黑色结点个数作为参考
				if (cur->_col == BLACK)
					blackCount++;
				cur = cur->_left;
			}
			return _IsRBTree(_root, blackCount, 0);
		}

		size_t size() { return _size(_root); }

		size_t _size(pNode root)
		{
			if (root == nullptr)
				return 0;

			return _size(root->_left) + _size(root->_right) + 1;
		}

		bool empty() { return _root == nullptr; }
	};
}

  红黑树之前我们实现过，这里就不进行详细介绍了。

 map模拟实现代码⬇️ ⬇️：

#pragma once
#include"RBTree.h"

namespace lz
{
	template
	class Map
	{
		typedef Map self;
		typedef lz::RBTree, PairSelect1st> RBTree;
		typedef typename lz::Iterator, pair< K, V>&, pair< K, V>*>::Reference Ref ;
		typedef typename lz::Iterator, pair< K, V>&,pair< K, V>*>::Pointer Ptr ;
	public:
		typedef typename RBTree::tree_iterator iterator;
		typedef typename RBTree::tree_const_iterator const_iterator;
		typedef typename RBTree::tree_reverse_iterator reverse_iterator;
		typedef typename RBTree::tree_const_reverse_iterator const_reverse_iterator;
		Map() :_rt() {}
		Map(const self& m) { _rt = m._rt; }

		//迭代器
		iterator begin() { return _rt.begin(); }
		iterator end() { return _rt.end(); }
		const_iterator cbegin()const { return _rt.cbegin(); }
		const_iterator cend()const { return _rt.cend(); }
		reverse_iterator rbegin() { return _rt.rbegin(); }
		reverse_iterator rend() { return _rt.rend(); }
		const_reverse_iterator crbegin()const { return _rt.crbegin(); }
		const_reverse_iterator crend()const { return _rt.crend(); }

		Ref operator*() { return _rt._root->_data; }
		Ptr operator->() { return &_rt._root->_data; }
		bool operator!=(const self& s)const { return _rt._root != s._rt._root; }
		bool operator==(const self& s)const { return _rt._root == s._rt._root; }

		//插入
		pair insert(const pair& kv) { return _rt.insert(kv); }
		//=重载
		self& operator=(const self& s) { _rt = s._rt; return *this; }
		//删除
		void erase(const iterator& it) { _rt.deleteNode(it._pnode); }
		//查找
		iterator find(const pair& kv)const { return _rt.find(kv); }
		//[]重载
		V& operator[](const K& key) { return insert(make_pair(key, V())).first._pnode->_data.second; }
		//判空
		bool empty()const { return _rt.empty(); }
		//打印
		void print() { _rt.InOder(); }
		//元素个数
		size_t size() { return _rt.size(); }
		//清除
		void clear() { _rt.clear(_rt._root); }

	private:
		RBTree _rt;
	};
}

对红黑树进行封装，其实就是通过红黑树来实现map的功能。

这里因为红黑树中实现了自减的重载，所以这里我们可以封装正向迭代器来实现反向迭代器。
关于插入，因为map要存储键对值，所以这里我们的仿函数选择PairSelect1st来选出key。同时注意其返回值是一个键对值，第一个参数是迭代器，第二个参数是布尔类型。
“=”的重载，直接通过红黑树中的等号重载完成。
”[]“的重载十分重要，根据[]中的key值来构造键对值，进行插入，同时根据插入的返回键对值中的迭代器，将插入键对值中的V引用返回，即可以直接通过=修改。

 set模拟实现代码⬇️ ⬇️：

#pragma once
#include"RBTree.h"
namespace lz
{
	template
	class Set
	{
		typedef Set self;
		typedef lz::RBTree< K, KSelect1st> RBTree;
		typedef typename lz::Iterator::Reference Ref;
		typedef typename lz::Iterator::Pointer Ptr;
	public:
		typedef typename RBTree::tree_iterator iterator;
		typedef typename RBTree::tree_const_iterator const_iterator;
		typedef typename RBTree::tree_reverse_iterator reverse_iterator;
		typedef typename RBTree::tree_const_reverse_iterator const_reverse_iterator;
		Set() :_rt() {}
		Set(const self& s) { _rt = s._rt; }

		//迭代器
		iterator begin() { return _rt.begin(); }
		iterator end() { return _rt.end(); }
		const_iterator cbegin()const { return _rt.cbegin(); }
		const_iterator cend()const { return _rt.cend(); }
		reverse_iterator rbegin() { return _rt.rbegin(); }
		reverse_iterator rend() { return _rt.rend(); }
		const_reverse_iterator crbegin()const { return _rt.crbegin(); }
		const_reverse_iterator crend()const { return _rt.crend(); }

		Ref operator*() { return _rt._root->_data; }
		Ptr operator->() { return &_rt._root->_data; }
		bool operator==(const self& s)const { return _rt._root == s._rt._root; }
		bool operator!=(const self& s)const { return _rt._root != s._rt._root; }

		//插入
		pair insert(const K& key) { return _rt.insert(key); }
		//=重载
		self& operator=(const self& s) { _rt = s._rt; return *this; }
		//删除
		void erase(const iterator& it) { _rt.deleteNode(it._pnode); }
		//查找
		iterator find(const K& key)const { return _rt.find(key); }
		//判空
		bool empty() { return _rt.empty(); }
		//元素个数
		size_t size() { return _rt.size(); }
		//清除
		void clear() { _rt.clear(); }

	private:
		RBTree _rt;
	};
}

  set这边就不做详细的介绍了，其功能和map类似。就存储方面不同。

 测试代码⬇️ ⬇️：

#include"RBTree.h"
#include"Map.h"
#include"Set.h"

void Test_Map1()//字典
{
	lz::Map map;
	pair arr[] = {
	make_pair("left", "左边") ,make_pair("right", "右边"),make_pair("up", "向上")
	,make_pair("down", "向下"),make_pair("left","左边"),make_pair("eat","吃")
	,make_pair("sleep","睡觉"),make_pair("run","跑"),make_pair("jump","跳") };

	//插入,const修饰+引用可以避免深拷贝
	for (const auto& str : arr)
		map.insert(str);
	
	//测试[]
	map["abc"] = "xx";
	map["abc"] = "xx";

	//正向迭代器
	auto it = map.begin();
	while (it != map.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;

	//反向迭代器
	auto rit = map.rbegin();
	while (rit != map.rend())
	{
		cout << rit->first << ":" << rit->second << endl;
		rit++;
	}
	cout << endl;

	//范围for
	for(const auto& str : map)
		cout << str.first << ":" << str.second << endl;
}

void Test_Map2()//统计次数
{
	lz::Map map1;
	string arr[] = { "苹果","梨","苹果","梨","梨","梨","苹果","香蕉","香蕉", "香蕉" ,"西瓜" };

	for (const auto& str : arr)
	{
		//如果不存在，那么插入数据
		if (map1.find(make_pair(str,1))._pnode == nullptr)
		{
			map1.insert(make_pair(str, 1));
			continue;
		}

		//存在，将次数++;
		map1[str]++;
	}

	auto it = map1.begin();
	while (it != map1.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;
}

void Test_Map3()
{
	lz::Map map;
	pair arr[] = {
	 make_pair(1, 1) ,make_pair(2, 2),make_pair(3, 3)
	,make_pair(4, 4),make_pair(5, 5),make_pair(6, 6)
	,make_pair(7, 7),make_pair(8, 8),make_pair(9, 9) };

	//插入
	for (auto e : arr)
		map.insert(e);

	//=测试和拷贝构造
	lz::Map map2;
	map2 = map;
	lz::Map map3(map2);

	//正向迭代器
	auto it = map.begin();
	while (it != map.end())
	{
		//可修改
		//it->second = 1;
		cout << it->first << ":" << it->second << endl;
		it++;
	}
	cout << endl;

	auto cit = map.cbegin();
	while (cit != map.cend())
	{
		//不可修改
		
		cout << cit->first << ":" << cit->second << endl;
		cit++;
	}
	cout << endl;

	//反向迭代器
	auto rit = map.rbegin();
	while (rit != map.rend())
	{
		// 可修改
		//rit->second = 1;
		cout << rit->first << ":" << rit->second << endl;
		rit++;
	}
	cout << endl;

	auto crit = map.crbegin();
	while (crit != map.crend())
	{
		//不可修改
		
		cout << crit->first << ":" << crit->second << endl;
		crit++;
	}
	cout << endl;

	//删除测试
	for (int i = 0; i < 20; i++)
	{
		it = map.begin();
		map.erase(it);
	}

	//范围for
	for (const auto& str : map)
		cout << str.first << ":" << str.second << endl;
}

void Test_Set()
{
	lz::Set s1;
	string arr[] = {
	"left", "左边" ,"right", "右边","up", "向上"
	,"down", "向下","left","左边","eat","吃"
	,"sleep","睡觉","run","跑","jump","跳" };

	if (s1.empty())
		cout << "空" << endl;
	else
		cout << "非空" << endl;

	//插入
	for (const auto& e : arr)
		s1.insert(e);

	//测试size
	cout << s1.size() << endl;

	//测试查找
	if (s1.find("睡觉")._pnode != nullptr)
		cout << "找到了" << endl;
	else
		cout << "没找到" << endl;

	//测试判空
	if (s1.empty())
		cout << "空" << endl;
	else
		cout << "非空" << endl;

	//=重载
	lz::Set s2;
	s2 = s1;

	//拷贝构造
	lz::Set s3(s2);

	for (const auto& e : s1)
		cout << e << endl;
	cout << endl;

	auto it = s1.begin();
	for (const auto& e : s1)
	{
		it = s1.begin();
		s1.erase(it);
	}

	for (const auto& e : s2)
	{
		it = s2.begin();
		s2.erase(it);
	}

	for (const auto& e : s3)
		cout << e << endl;
}

int main()
{
	//Test_Set();
	//Test_Map1();
	//Test_Map2();
	//Test_Map3();
	return 0;
}

  测试中包括了map的功能测试，map字典和计数的实现，以及set的功能测试。

 今天的内容到这里就结束了，希望各位小伙伴们能够有所收获，我们下期再见！