【C++】—— 从零开始封装 Map 与 Set：实现与优化

人生的态度是，抱最大的希望，尽最大的努力，做最坏的打算。

—— 柏拉图 《理想国》

目录

1、理论基石——深度剖析 BSTree、AVLTree 与 RBTree 的概念区别

2、迭代器机制——RBTree 迭代器的架构与工程实现

3、高级容器设计——Map 与 Set 的模块化封装

3.1 泛型支持增强——RBTree 模板参数设计优化

3.2 Set 容器构建——面向集合操作的优化设计

 3.3 Map 容器构建——高效键值存储的封装实现

Thanks谢谢阅读！！！

1、理论基石——深度剖析 BSTree、AVLTree 与 RBTree 的概念区别

为了实现 Map 和 Set 的封装，我们首先进行了充分的知识储备，确保理解底层数据结构的原理与实现。

二叉搜索树及其变种

为了深入理解 Map 和 Set 的底层原理，我们从二叉搜索树 (BST)入手。二叉搜索树在二叉树的基础上加入了以下重要特性：

• 若左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若右子树不为空，则右子树上所有节点的值都大于根节点的值；
• 左右子树也必须分别满足二叉搜索树的性质。

  这种结构在大多数情况下可以有效支持快速查找，但在某些极端情况下（例如单侧树形结构），搜索效率会退化为 O(n)。因此，我们引入了更为高效的平衡二叉搜索树，其中 AVL树 和 红黑树 (RBTree) 是两种经典的变种，它们通过不同的方式提高了性能与稳定性。

  平衡二叉搜索树：AVL 树与红黑树

  AVL 树 和 红黑树 都是在保持二叉搜索树基本性质的基础上，通过旋转与重新平衡操作，确保树的高度维持在一个相对平衡的状态，从而保证了操作的时间复杂度始终为 O(log n)。它们的出现大大提升了二叉搜索树在实际应用中的性能与可靠性。

  • AVL 树 增加了以下特性：

    • 它的左右子树必须都是 AVL 树；
    • 左右子树高度差（平衡因子）不能超过 1（即平衡因子为 -1、0 或 1）；
    • 如果平衡因子超出范围，树将进行旋转操作，包括右单旋、左单旋、左右双旋、右左双旋等。

  • 红黑树 则在其基础上引入了以下特点：

    • 每个节点必须是红色或黑色；
    • 根节点必须是黑色；
    • 红色节点的子节点必须是黑色；
    • 从任何节点到其所有后代叶子节点的路径上，必须有相同数量的黑色节点；
    • 叶子节点（空节点）必须是黑色。

    虽然红黑树在旋转操作的频率上低于 AVL 树，但它通过较少的旋转保持树的接近平衡状态，能够确保良好的性能。

    Map 与 Set 的底层实现

    由于 Map 和 Set 大多用于高效检索，我们选择使用 红黑树 来实现它们的底层结构。红黑树能够在保证相对平衡的同时，确保操作时间复杂度为 O(log n)，非常适合用于处理大量的键值对数据。

    封装前的迭代器实现

    在封装 Map 和 Set 之前，我们需要先实现一个关键的组件：迭代器。迭代器是遍历容器内元素的核心工具，它提供了访问和操作元素的方式，并为我们后续的封装工作奠定了基础。

    2、迭代器机制——RBTree 迭代器的架构与工程实现

    迭代器是容器中非常重要的组成部分，它使得我们可以方便地遍历数据。在 红黑树 的实现中，增加迭代器支持不仅仅是为了提供遍历的便利，更是为了使得红黑树能够符合现代 C++ 泛型编程的要求，遵循 STL 中对迭代器的严格规范。

    首先，考虑到迭代器的设计，我们需要解决几个关键问题：

    1. 泛型编程与迭代器框架

       迭代器的实现要支持泛型编程，因此需要考虑其接口设计，确保它能适应不同类型的容器结构。具体而言，我们需要实现一个适用于红黑树的迭代器模板，支持不同类型的键值对容器。

    2. begin() 与 end() 的设计
       STL 明确规定了 begin() 与 end() 方法分别代表容器的起始位置和结束位置，且是前闭后开的区间。在红黑树的情况下，由于其节点经过中序遍历是有序的，begin() 应该指向树的最小节点（即最左侧节点），end() 则应指向一个空节点，即最大节点的下一个位置（为了简化设计，可以设为 nullptr）。

    3. operator++() 和 operator--() 的实现

       在迭代器的操作符 ++ 和 -- 实现上，需要遵循红黑树的中序遍历顺序。与链表或数组不同，红黑树的节点并不是顺序排列的，因此简单的指针递增或递减操作无法满足需求。我们需要通过树的结构来确定“下一个”或“上一个”节点的位置，这通常通过旋转和父节点引用来实现。

    迭代器框架的搭建

    在确定了迭代器的需求后，接下来我们可以着手搭建迭代器框架。该框架需要支持以下功能：

    • 构造与销毁：支持红黑树迭代器的构造与析构。
    • 指针访问：提供对当前节点的访问能力，通常通过解引用操作符 * 和成员访问操作符 -> 来实现。
    • 前进与后退：通过 ++ 和 -- 操作符来支持迭代器的前进与后退，确保其符合树的中序遍历规则。
    • 比较操作：支持 == 和 != 比较操作，判断两个迭代器是否指向同一节点。

      // 迭代器
      // T 表示数据类型 Ref为引用 Ptr为指针
      template
      struct RBTreeIterator
      {
      	//为了方便调用，我们重命名一下
      	typedef RBTreeNode Node;
      	typedef _RBTreeIterator Self;
      	//内部是节点指针
      	Node* _node;
      	_RBTreeIterator(Node* node)
      		:_node(node)
      	{}
      	
      	//两种指向方式
      	Ref operator*()
      	{
      		return _node->_data;
      	}
      	Ptr operator&()
      	{
      		return &_node->_data;
      	}
      	bool operator!= (const Self& s)
      	{
      		return _node != s._node;
      	}
      	bool operator== (const Self& s)
      	{
      		return _node == s._node;
      	}
      };

      迭代器的访问 ++ 和 --

      ++ 中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。

      Self& operator++()
      {
      	//首先，能访问到当前节点说明左子树的都已经访问过啦 左 根 右  中序
      	//所以就要分类讨论
      	//如果右边有子树,就要去寻找右子树的最左节点
      	if (_node->_right)
      	{
      		Node* cur = _node->_right;
      		while (cur->_left)
      		{
      			cur = cur->_left;
      		}
      		_node = cur;
      	}
      	//如果右边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行++
      	//找到祖先节点(注意祖先节点右边可能还没遍历)
      	//此时也要进行分类讨论
      	else 
      	{
      		Node* cur = _node;
      		Node* parent = _node->_parent;
      		// 如果 _node == parent->_right
      		//说明parent的节点已经访问过了 需要向上遍历 找到没有访问的 可能一直向上 导致 parent 空 所以判断一下
      		while (parent && cur == parent->_right)
      		{
      			cur = parent;
      			parent = cur->_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* cur = _node->_left;
      		while (cur->_right)
      		{
      			cur = cur->_right;
      		}
      		_node = cur;
      	}
      	//如果左边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行--
      	//找到祖先节点(注意祖先节左边可能还没遍历)
      	//此时也要进行分类讨论
      	else
      	{
      		Node* cur = _node;
      		Node* parent = _node->_parent;
      		// 如果 _node == parent->_left 
      		//说明parent的节点已经访问过了 需要向上遍历 找到没有访问的 可能一直向上 导致 parent 空 所以判断一下
      		while (parent && cur == parent->_left)
      		{
      			cur = parent;
      			parent = cur->_parent;
      		}
      		_node = parent;
      	}
      	return *this;
      }
      

      这里特殊情况是因为 我们设置的容器迭代器 end（） 为空指针 （STTL库是加了个哨兵位节点）不可以再访问了所以特殊处理一下

      

      3、高级容器设计——Map 与 Set 的模块化封装

      3.1 泛型支持增强——RBTree 模板参数设计优化

      我们先来看之前写的红黑树的节点代码：

      // 节点结构体
      template
      struct RBTreeNode
      {
      	RBTreeNode* _left;
      	RBTreeNode* _right;
      	RBTreeNode* _parent;
      	pair _kv;
      	color _col;
      	RBTreeNode(pair kv)
      		:_left(nullptr),
      		_right(nullptr),
      		_parent(nullptr),
      		_kv(kv)
      	{}
      };
      

      在实现 Map 和 Set 的封装时，我们发现，当前的设计使得每个红黑树的节点都存储了一个固定的数据类型 pair。这种做法虽然对 Map 的实现来说非常直接，但当我们尝试为 Set 封装时，问题就显现出来了：Set 中的节点只需要存储键 K，而不是键值对 pair。这意味着如果我们照这种方式实现 Set，我们就不得不重复编写一份类似的红黑树代码来处理不同的数据结构。这样不仅增加了代码的冗余，也让代码的维护变得不够优雅。

      为了更好地封装 Map 和 Set，我们可以借鉴 STL 源码中的设计理念。STL 中通过 模板编程 和 类型特化 的方式，使得同一个数据结构能够支持不同类型的容器，而不需要重复编写代码。这种设计不仅提高了代码的复用性，还使得容器能够灵活地处理不同的数据类型。

      STL 的设计思路

      在 STL 中，Map 和 Set 都是通过底层红黑树（或其他平衡树）来实现的，但它们有不同的结构和需求：

      • Map 是一个键值对容器，节点存储 pair；
      • Set 是一个只存储键的容器，节点只需要存储 K。

        然而，尽管它们的数据存储结构不同，STL 并没有为 Map 和 Set 分别写两份完全不同的红黑树代码。相反，STL 通过巧妙的模板设计，使得同一个红黑树实现能够根据需求灵活存储键值对或者仅存储键。

        

        可以看出，STL 源码中的设计巧妙地利用了模板编程，成功地实现了 Map 和 Set 的统一封装，避免了代码冗余。

        STL设计思路解析

        首先，最底层的红黑树节点结构体只使用了一个模板参数 Value，该参数决定了节点中存储的数据类型。上层的红黑树根据提供的 Value 类型来选择具体的数据存储结构。这样，红黑树的底层实现不需要区分 Map 和 Set，而是通过模板参数 Value 来灵活适应不同需求。

        红黑树的关键模板参数

        在红黑树的实现中，存在三个关键的模板参数：

        1. Key：表示键的类型，主要用于查找操作（如 Find 函数）。通过 Key，红黑树可以高效地定位某个节点是否存在。
        2. Value：表示存储的数据类型。在 Map 中，Value 是 pair，而在 Set 中，Value 则只有键 K。
        3. KeyOfValue：这是一个仿函数，用于从 Value 中提取 Key。该仿函数在很多操作中都非常重要，特别是在查找操作中，它能帮助我们从 Value 中提取出 Key，用于比较和定位。

        统一封装：如何实现 Map 与 Set 的共享底层红黑树

        通过巧妙的模板设计，红黑树底层实现可以根据不同的需求使用不同的数据结构来存储：

        • 对于 Map，底层红黑树将 Key 和 pair 作为模板参数传入。Key 用于查找操作，而 Value 则是 pair，即包含键和值的结构。 
        • map:就传给红黑树
        • 对于 Set，红黑树只需要 Key 作为模板参数，因为 Set 只关心存储键 K，无需存储值，但是这里红黑树的前两个模板参数都需要传K。
        • set: 就传给红黑树

          通过这种方式，尽管 Map 和 Set 的模板参数不同（分别是 pair 和 K），它们却可以共用同一份底层红黑树代码。这种设计不仅避免了代码重复，也提高了代码的可维护性和灵活性。

          //-------------------------------------------
          //---------------- 红黑树实现 -----------------
          //-------------------------------------------
          //-------- 适配map 与 set 的进阶版本 -----------
          //-------------------------------------------
          enum color
          {
          	Black,
          	Red
          };
          // 节点结构体
          template
          struct RBTreeNode
          {	
          	RBTreeNode* _left;
          	RBTreeNode* _right;
          	RBTreeNode* _parent;
          	
          	T _data;
          	color _col;
          	RBTreeNode(T data)
          		:_left(nullptr),
          		_right(nullptr),
          		_parent(nullptr),
          		_data(data),
          		_col(Red)
          	{}
          };
          //适配map与set 的版本
          // 迭代器
          template
          struct _RBTreeIterator
          {
          	typedef RBTreeNode Node;
          	typedef _RBTreeIterator Self;
          	Node* _node;
          	_RBTreeIterator(Node* node)
          		:_node(node)
          	{}
          	Ref operator*()
          	{
          		return _node->_data;
          	}
          	Ptr operator&()
          	{
          		return &_node->_data;
          	}
          	bool operator!= (const Self& s)
          	{
          		return _node != s._node;
          	}
          	//迭代器的++ 中序遍历的顺序
          	Self& operator++()
          	{
          	}
          	Self& operator--()
          	{
          	}
          };
          //K 为键值 T 为储存的结构 map则为pair set则为key  KeyOfValue 是取出Key的方式
          template
          class RBTree
          {
          public:
          	typedef _RBTreeIterator Iterator;
          	typedef RBTreeNode Node;
          	Iterator begin()
          	{
          	
          	}
          	Iterator end()
          	{
          	
          	}
          	//右单旋
          	void RotateR(Node* parent)
          	{
          	}
          	//左右双旋
          	void RotateLR(Node* parent)
          	{
          	}
          	//右左双旋
          	void RotateRL(Node* parent)
          	{
          	}
          	
          	//插入函数	
          	pair insert(const T& data)
          {
          	if (_root == nullptr)
          	{
          		_root = new Node(data);
          		_root->_col = BLACK;
          		//return pair(Iterator(_root,_root),true);
          		return { Iterator(_root,_root), true };
          	}
          	Node* cur = _root;
          	Node* parent = nullptr;
          	//查找逻辑 cur 到对应的位置去
          	// KeyOfT 取第一个数据比较
          	KeyOfT kot;
          	while (cur)
          	{
          		if (kot(cur->_data) _right;
          		}
          		else if (kot(cur->_data) > kot(data))
          		{
          			parent = cur;
          			cur = cur->_left;
          		}
          		else
          		{
          			return { Iterator(cur,_root), false};
          		}
          	}
          	cur = new Node(data);
          	Node* newnode = cur;
          	cur->_col = RED; //新插入非空节点 为红色
          	// 连接 prev 与 cur
          	if (kot(parent->_data) > kot(data))
          		parent->_left = cur;
          	else
          		parent->_right = cur;
          	cur->_parent = parent;
          	// 父亲是红色 出现了连续红节点 需要处理 可能多次处理 while向上更新
          	while (parent && parent->_col == RED) //可能为空
          	{
          		Node* grandfather = parent->_parent;
          		if (grandfather->_left == parent)
          		{
          			//   g
          			// p   u
          			Node* uncle = grandfather->_right;
          			// 叔叔不为空 且红色 
          			if (uncle && uncle->_col == RED)
          			{
          				//父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变
          				parent->_col = uncle->_col = BLACK;
          				grandfather->_col = RED;
          				//往上更新
          				cur = grandfather;
          				parent = cur->_parent;
          			}
          			else
          			{
          				if (parent->_left == cur) //右单旋+变色
          				{	//     g
          					//   p   u
          					// c
          					RotateR(grandfather);
          					parent->_col = BLACK;
          					grandfather->_col = RED;
          				}
          				else //双旋处理
          				{
          					//     g
          					//   p   u
          					//    c
          					RotateLR(grandfather);
          					cur->_col = BLACK;
          					grandfather->_col = RED;
          				}
          				break;
          			}
          		}
          		else
          		{
          			//   g
          			// u   p
          			Node* uncle = grandfather->_left;
          			// 叔叔不为空 且红色 
          			if (uncle && uncle->_col == RED)
          			{
          				//父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变
          				parent->_col = uncle->_col = BLACK;
          				grandfather->_col = RED;
          				//往上更新
          				cur = grandfather;
          				parent = cur->_parent;
          			}
          			else
          			{
          				if (parent->_right == cur) //左单旋+变色
          				{	//     g
          					//   u   p
          					//		   c
          					RotateL(grandfather);
          					parent->_col = BLACK;
          					grandfather->_col = RED;
          				}
          				else //双旋处理
          				{
          					//     g
          					//   u   p
          					//		c
          					RotateRL(grandfather);
          					cur->_col = BLACK;
          					grandfather->_col = RED;
          				}
          				break;
          			}
          		}
          	}
          	_root->_col = BLACK;
          	return { Iterator(newnode,_root), true};
          }
          Iterator find(const K& key)
          {
          	Node* cur = _root;
          	KeyOfT kot;
          	while (cur)
          	{
          		if (kot(cur->_data) _right;
          		}
          		else if (kot(cur->_data) > key)
          		{
          			cur = cur->_left;
          		}
          		else
          		{
          			return Iterator(cur,_root);
          		}
          	}
          	return End();
          }
          private:
          	void _IsBalance(Node* root , int num)
          	{
          	}
          	bool Check(Node* root, int blackNum, const int refNum)
          	{
          	}
          	void _InOrder(Node* cur)
          	{
          	}
          	RBTreeNode* _root = nullptr;
          };
          

          注意比较方式统一改成类似kot(_data)

          3.2 Set 容器构建——面向集合操作的优化设计

          Set 封装的实现

          对于 Set 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

          1. 模板参数传递：

             Set 需要满足 K 和 V 的模板参数传递。K 表示键的类型，V 表示值的类型。

          2. 仿函数实现：

             我们需要实现一个仿函数，用于从存储的 模板参数 V 中提取出 Key。因为比较逻辑是比较键值，但是底层红黑树并不知道T模板参数是pair 还是key

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

          3. 底层红黑树的实例化：

             在 Set 类中，我们实例化一个底层红黑树，传入对应的模板参数 K、const K（注意，键是不可修改的，所以需要使用 const 来确保键是常量），以及 SetOfT 仿函数。这样，红黑树能够适应 Set中键值对的存储方式。

          4. 迭代器的实现：

             在 Set 类中，我们还需要实现一个迭代器。只需要提供基本的 begin() 和 end() 接口，直接调用底层红黑树的相关方法即可。迭代器的前进（++）和后退（--）操作交给底层红黑树的迭代器来处理。

          namespace xc
          {
          	template
          	class set
          	{
          		struct SetKeyOfT
          		{
          			const K& operator()(const K&key)
          			{
          				return key;
          			}
          		};
          	public:
          		typedef typename RBTree::Iterator iterator;
          		typedef typename RBTree::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 insert(const K&key)
          		{
          			return _t.insert(key);
          		}
          		
          		iterator find(const K& key)
          		{
          			return _t.find(key);
          		}
          	private:
          		RBTree _t;
          	};
          }

           3.3 Map 容器构建——高效键值存储的封装实现

          在完成了红黑树的改进后，接下来的步骤就相对简单了。我们只需要在上层实现 Map 和 Set 的具体封装，调用底层红黑树的接口并传入相应的模板参数即可。

          Map 封装的实现

          对于 Map 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

          1. 模板参数传递：

             Map 需要满足 K 和 V 的模板参数传递。K 表示键的类型，V 表示值的类型。

          2. 仿函数实现：

             我们需要实现一个仿函数，用于从存储的 pair 中提取出 Key。因为比较逻辑是比较键值，但是底层红黑树并不知道T模板参数是pair 还是key

             	struct MapKeyOfT
             	{
             		const K& operator()(const pair& kv)
             		{
             			return kv.first;
             		}
             	};

          3. 底层红黑树的实例化：

             在 Map 类中，我们实例化一个底层红黑树，传入对应的模板参数 K、pair（注意，键是不可修改的，所以需要使用 pair 来确保键是常量），以及 MapOfT 仿函数。这样，红黑树能够适应 Map 中键值对的存储方式。

          4. 迭代器的实现：

             在 Map 类中，我们还需要实现一个迭代器。只需要提供基本的 begin() 和 end() 接口，直接调用底层红黑树的相关方法即可。迭代器的前进（++）和后退（--）操作交给底层红黑树的迭代器来处理。

          namespace xc
          {
          	template
          	class map
          	{
          		struct MapKeyOfT
          		{
          			const K& operator()(const pair& kv)
          			{
          				return kv.first;
          			}
          		};
          	public:
          		typedef typename RBTree::Iterator iterator;
          		typedef typename RBTree::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 insert(const pair& kv)
          		{
          			return _t.insert(kv);
          		}
          		iterator find(const K& key)
          		{
          			return _t.find(key);
          		}
          		V& operator[](const K& key)
          		{
          			pair ret = insert({ key, V() });
          			return ret.first->second;
          		}
          	private:
          		RBTree _t;
          	};
          }

          这样map 封装好了，测试一下！！！

          void test_map()
          {
          	xc::map dict;
          	dict.insert({ "sort", "排序" });
          	dict.insert({ "left", "左边" });
          	dict.insert({ "right", "右边" });
          	dict["left"] = "左边，剩余";
          	dict["insert"] = "插入";
          	dict["string"];
          	xc::map::iterator it = dict.begin();
          	while (it != dict.end())
          	{
          		// 不能修改first，可以修改second
          		//it->first += 'x';
          		it->second += 'x';
          		cout first