• 实现map和set

      map和set的底层就是红黑树，所以只要实现了红黑树，就可以考虑封装出map和set。所以本文会重点介绍我是如何一步步封装map和set，就不会再介绍红黑树的实现，实现可看我上篇博客，个人觉得封装中最麻烦的就是模板参数和迭代器，所以本文从这两个方面入手。红黑树博客链接在下：

     红黑树的部分功能实现_小何只露尖尖角的博客-CSDN博客

    第一 模板参数

       map和set都是模板，使用时都要先显示实例化 , set只要传一个类型实例化K即可，因为set中只存一个关键码-key , 而map要给K , T实例化成具体的类型(K,T分别对应map K-V结构的关键码-key和存的数据-value) , 那为什么map的模板参数不命名为K,V呢?这其实牵扯到一个问题，那就是树中存的是什么?(红黑树模板参数会提及)

       map和set的底层就是红黑树，那是如何将红黑树的函数给map和set呢, 可以用继承，或者是组合。至于为什么此时用组合呢?我觉得在map和set内部定义了一个红黑树变量(这种方式称为组合)，比继承的耦合度更低，或许可以减少后期维护的工作量。而这个红黑树也是一个模板，所以定义该变量也要传模板参数。如下

    1 从map和set的传参来看

      红黑树接收的模板参数如下:

        T是节点存的数据类型，K就是关键码key的数据类型，第三个模板参数先不用理会。

        当我们大致解释了红黑树的模板参数的意义，也就知道了第一个模板参数是set和map的关键码key的数据类型, 第二个是map和set在节点存的数据类型。

    set给红黑树传的模板参数如下:

      set(set是把K传给红黑树的模板参数T实例化），set库里把K重命名为value然后传给T(T指的是红黑树模板参数)，而map是把一个pair重命名为value传给T，这种重命名为value个人觉得是为了统一记忆 , value是外部传给红黑树节点的数据类型 , 免得一会是K，一会是pair。

      为了避免混淆，不让大家以为map模板参数V是value_type的缩写，所以库里的map的模板参数是K和T，而不是K和V，我们为了与库里命名，函数实现保持一致，便于我们理解库里的实现，也用K ,T做map的模板参数。

       （set官网文档如下图）

    （map官网文档如下图）

    map给红黑树传的模板参数如下:

      那为什么map传给红黑树的T不是自己模板参数的T呢，而是一个pair呢，如果传的是自己的模板参数T，这样K,T不都传过去了吗?传pair不是浪费吗？

     可是你看看下面节点类RBTreeNode的设计，只有T一个模板参数，该类也只有_data一个变量。

      而map是k-v结构的，例如统计字符串出现次数, 那map实例化应该是map，如果map模板参数不是string,pair，而是string,int，这个时候int就被拿去实例化节点了，你让int类型的_data如何存储字符串类型的key呢? 什么?你说为什么不给节点类多加一个变量来存，那我反问一下，那insert如何实现呢，对于set的insert的参数那就一个key值，但是map却要插入两个值，难道写两个insert吗，模板的意义就是为了减少大量重复代码的书写，你现在难道要走回去吗。所以为了统一insert，map的k-v两个变量只能合并在一个结构体中了。其实合并也挺好的，返回也可以一起返回。

    2 红黑树接收模板参数来看

    我们先前勉强了解了红黑树模板参数T，map传一个pair类型给T接收 ,  而set传的是一个k类型。

      我们可以看到的是RBTree的模板参数还有两个。由于insert有可能是插入一个pair，也有可能是插入一个key值，由此却引发另外一个问题 , 那就是insert插入元素是要做大量的判断的，map插入的data是pair类型的，按二叉搜索树规则，要当前根节点cur比较key的值找插入位置，而cur是要用cur->_data.first才能取到key的值，而data则也要用.first访问到key，但是set插入的数据就是key的值，可以直接用cur->_data和插入的data比较，此时难道又要写两份代码吗?当然不是，所以我们就用一个仿函数将pair中的key返回来，而set为了保持一致，也得传个仿函数，只是这个仿函数几乎不做处理，这就是第三个模板参数的作用。

    Set仿函数如下:

    没有做什么处理就直接返回

    Map仿函数如下:

    取出key返回，此处是set为了配合map做出的让步，后续我们会在迭代器处看到map和set的其它冲突。在多种冲突下能维持一种特殊的平衡是一件很有成就感的事。

    使用场景如下:(在比较处就用这个仿函数)

      好好好，那为什么还要传个k呢，不是多余吗 , 那你想想find的参数那个const K& key中的K是哪来的，如果不传K，那find的参数类型如何确定，那个仿函数可取不出来，取得可不是类型，那是数据。

    第二 使key不可修改

       还有个难啃的骨头，set和map的key可修改的问题，但是只要我们把key可修改和模板参数的问题理清了，封装就过去了。

    1 解决set的key

       const迭代器是节点数据不能修改, 普通迭代器则可以修改节点数据，但是set中的节点数据只有key关键码，key是不能修改的, 所以set的普通迭代器也不能修改这个关键码，也就是说我们要让set的const迭代器和普通迭代器保持一致。

    迭代器iterator本质是my_set类和my_map类内部的一个类型，然后用这个类型来定义变量使用。

    	My_Structure::my_set<int>::iterator sit = s1.begin();

      所以要想取出来的iterator这个类型定义出来的变量，有const_iterator的作用，我们就得对const_iterator进行typedef重命名，将const_iterator命名为iterator，这样就有种偷梁换柱的效果，你以为取出来的iterator是普通迭代器，其实是const_iterator假扮的(如下)。

     所以set只提供加了const的begin和end函数，这样不管外部的set变量是不是const的，都只会调用这个被const修饰的begin和end函数，也就只会返回const迭代器了。注:此处的iterator是const_iterator重命名的。

      2  解决map的key

        map就不能用set的方法了，因为这样map的pair就是有const属性的了，那first是key不被修改可以，second是有被修改的需求的，一刀切是不行的。大佬的想法总是让人意想不到，那就是直接就把pair中的K传为const K, 这样普通迭代器就只会限制key，而不会限制value。

       还有值得一提的是，这种方法为什么不用在set上呢，可能会限制某些功能的开发，所以大佬就没用，但是就我们这点功能还是可以对set用传const key的方法。

      我们先记住这两个容器实现const迭代器的方法，由此产生的问题才刚刚开始，下面介绍map和set的成员函数会再说。

    第三 map和set的成员函数

      set的insert

       _t这个红黑树变量调用自己的insert函数返回的pair和set的insert函数返回的pair根本就不是同一个类型。因为红黑树内部的iterator就是普通迭代器，不是const_iterator重定义，而且insert函数必须是返回普通迭代器，因为map后面insert要配合[]修改节点数据。

      大佬们想了一种办法就是，我们先用匹配类型接收，然后调用构造函数来转换类型(这一步可以在后面完整代码介绍再好好体会)，这一步太妙了，我才意识到，构造函数的本质其实是一种类型的转换。

      还要解释一点就是typename这个关键字的意思，因为我们要取的红黑树类内的iterator，所以要指定类域，但是这个类没有被实例化，编译器不知道你取出来的是静态变量还是一种类型，因为我们取静态变量也是用类域::这种方式访问，犹豫不决编译器就选择报错了，所以有了typename，告诉编译器你先别报错，我这肯定是类型，等我实例化你再核实。

    map的insert

    类型匹配，不用做处理。

    map的[]重载

      []重载的妙用:map m1,统计字符串出现次数,m1["he"]++，如果"he"在map内，就对返回其节点的迭代器，如果不存在就要调用insert插入，并且返回pair，然后我们再取pair的first，也就是对应位置的迭代器，如下对it再取second就是存的次数了，虽然我们[]传的是一个字符串，和函数参数不匹配，但是pair内部的first只需要一个字符串来初始化,second是内置类型，默认为0，应该算是隐式类型转换支持的。

    封装set

    set的insert,begin,end函数都介绍完了，下面完整的发出封装代码，代码不多。

    1. namespace My_Structure
    2. {
    3. 	template<class K>
    4. 	class my_set
    5. 	{
    6. 		
    7. 		struct GainSetKey  为了map和set传模板参数保持一致,set也要传一个GainSetKey
    8. 		{
    9. 			const K& operator()(const K&data)
    10. 			{
    11. 				return data;
    12. 			}
    13. 		};
    14. 	public:
    15.  
    16. 		typedef typename RBTree::const_iterator iterator;
    17. 		typedef typename RBTree::const_iterator const_iterator;
    18.  
    19. 	public:
    20. 		pairbool> Insert(const K& data)//iterator:const_iterator
    21. 			                                      _t.Insert返回的是普通迭代器
    22. 		{
    23. 			pair<typename RBTree::iterator,bool> 
    24.                                     p1(_t.Insert(data));
    25.  
    26. 			return pairbool>(iterator(p1.first), p1.second);
    27. 		}
    28.  
    29. 		iterator begin()const//只提供const的begin和end函数
    30. 		{
    31. 			return _t.begin();
    32. 		}
    33. 		iterator end()const
    34. 		{
    35. 			return _t.end();
    36. 		}
    37. 	private:
    38. 		RBTree _t;   
    39.      
    40.     第一个模板参数k是给find使用的,第二个是给RBTree节点使用的
    41. 	};
    42. };

    封装map

      如下封装代码，map只剩下begin和end函数没提，其余的都讲过了，map的begin和end函数要提供const和非const的，如果只有const的，那返回就都是带const迭代器的pair了。

    1. namespace My_Structure
    2. {
    3. 	template<class K,class T>
    4. 	class my_map
    5. 	{
    6. 		
    7. 		struct GainMapKey//用来返回pair中的key
    8. 		{
    9. 			const K& operator()(const pair& data)
    10. 			{
    11. 				return data.first;
    12. 			}
    13. 		};
    14. 		typedef typename RBTreeconst K, T>, GainMapKey>::iterator iterator;
    15. 		typedef typename RBTreeconst K, T>, GainMapKey>::const_iterator const_iterator;
    16. 	public:
    17. 		pairbool> Insert(const pair&data)//不能返回const迭代器,这样[]无法修改val
    18. 		{
    19. 			return _t.Insert(data);
    20. 		}
    21. 		iterator begin()
    22. 		{
    23. 			return _t.begin();
    24. 		}
    25. 		iterator end()
    26. 		{
    27. 			return  _t.end();
    28. 		}
    29. 		const_iterator begin()const
    30. 		{
    31. 			return _t.begin();
    32. 		}
    33. 		const_iterator end()const
    34. 		{
    35. 			return _t.end();
    36. 		}
    37. 		T& operator[](const pair&data)
    38. 		{
    39. 			iterator it=_t.Insert(data).first;
    40. 			return (it)->second;
    41. 		}
    42. 	private:
    43. 		RBTreeconst K, T>, GainMapKey> _t;
    44. 	};
    45. };

    第三 其余完整代码

    节点类

    一个模板参数T，使得_data可以是任意类型的数据。

    1. enum Color
    2. {
    3. 	Red,
    4. 	Black
    5. };
    6. template<class T>
    7. struct RBTreeNode
    8. {
    9. 	RBTreeNode(const T& data)   默认构造
    10. 		:_data(data)
    11. 		,_left(nullptr)
    12. 		,_right(nullptr)
    13. 		,_parent(nullptr)
    14. 	{
    15. 		;
    16. 	}
    17. 	T _data;   节点数据类型根据模板参数而定,可能是一个pair,或者一个key
    18. 	RBTreeNode*_left;
    19. 	RBTreeNode* _right;
    20. 	RBTreeNode* _parent;
    21. 	Color _color=Red;  默认节点颜色为红
    22. };

    红黑树类

    1.  
    2.  
    3. template<class K, class T,class Gainkey>
    4. class RBTree
    5. {
    6. public:
    7. 	typedef RBTreeNode Node;
    8. 	typedef _Iterator iterator;
    9. 	typedef _Iteratorconst T*,const T&> const_iterator; const迭代器,
    10.   
    11.   第一个模板参数不传const T，这个T有大用。
    12.  而且const迭代器的不可修改特性是由后面const T*和const T&决定的，与第一个模板参数无关
    13.  
    14. public:
    15. 	iterator begin()  树的最左节点是中序遍历的起点
    16. 	{
    17. 		Node* cur = _root;
    18. 		while (cur->_left)
    19. 		{
    20. 			cur = cur->_left;
    21. 		}
    22. 		return iterator(cur);
    23. 	}
    24. 	iterator end()  迭代器++最后到根的parent,也就是空节点
    25. 	{
    26. 		return iterator(_root->_parent);
    27. 	}
    28. 	const_iterator begin()const
    29. 	{
    30. 		Node* cur = _root;
    31. 		while (cur->_left)
    32. 		{
    33. 			cur = cur->_left;
    34. 		}
    35. 		const_iterator cit(cur);
    36. 		return cit;
    37. 	}
    38. 	const_iterator end()const
    39. 	{
    40. 		return const_iterator(nullptr);
    41. 	}
    42. 	
    43. public:
    44. 	pairbool> Insert(const T& data)
    45. 	{
    46. 		Gainkey get;
    47. 		if (_root == nullptr)
    48. 		{
    49. 			_root = new Node(data);
    50. 			_root->_color = Black;
    51. 			return pairbool>(iterator(_root), true);
    52. 		}
    53. 		Node* cur = _root;
    54. 		Node* parent = _root;
    55. 		while (cur)   按照搜索二叉树规则插入节点
    56. 		{
    57. 			if (get(cur->_data) < get(data))
    58.        
    59.      若是map实例化,get可以将pair转为key来比较
    60. 		
    61.         	{
    62. 				parent = cur;
    63. 				cur = cur->_right;
    64. 			}
    65. 			else if (get(cur->_data) > get(data))
    66. 			{
    67. 				parent = cur;
    68. 				cur = cur->_left;
    69. 			}
    70. 			else
    71. 			{
    72. 				return pairbool>(iterator(cur), false);
    73.         
    74.             找到相同节点,返回该节点迭代器
    75. 		
    76.         	}
    77. 		}
    78. 		//当cur等于nullptr时,
    79. 		//插入节点
    80. 		cur = new Node(data);
    81. 		Node* newnode = cur;
    82.  
    83. 		if (get(parent->_data) > get(data))//小于parent的key,插入到左边
    84. 		{
    85. 			parent->_left = cur;
    86. 		}
    87. 		else //大于parent的key,插入到右边
    88. 		{
    89. 			parent->_right = cur;
    90. 		}
    91. 		cur->_parent = parent;
    92.  
    93. 		//变色
    94. 		while (parent && parent->_color == Red)//当cur的父节点为空和颜色为黑时，调整结束  
    95. 		{
    96. 			Node* gparent = parent->_parent;
    97. 			if (parent==gparent->_left)
    98. 			{
    99. 				Node* uncle = gparent->_right;
    100. 				if (uncle && uncle->_color==Red)//当uncle节点存在并且颜色为红时
    101. 				{
    102. 					uncle->_color = Black;
    103. 					parent->_color =Black;
    104. 					gparent->_color = Red;
    105. 					//继续向上调整
    106. 					cur = gparent;
    107. 					parent = cur->_parent;
    108. 				}
    109. 				else
    110. 				{
    111. 					if (cur == parent->_left)//右单旋
    112. 					{
    113. 						RotateR(gparent);
    114. 						parent->_color = Black;
    115. 						gparent->_color = Red;
    116. 					}
    117. 					if (cur == parent->_right)//双旋
    118. 					{
    119. 						RotateL(parent);
    120. 						RotateR(gparent);
    121. 						cur->_color = Black;
    122. 						gparent->_color = Red;
    123. 					}
    124. 					break;
    125. 				}
    126. 			}
    127. 			else//parent==gparent->_right
    128. 			{
    129. 				Node* uncle = gparent->_left;
    130. 				if (uncle && uncle->_color == Red)//当uncle节点存在并且颜色为红时
    131. 				{
    132. 					uncle->_color = Black;
    133. 					parent->_color = Black;
    134. 					gparent->_color = Red;
    135. 					//继续向上调整
    136. 					cur = gparent;
    137. 					parent = cur->_parent;
    138. 				}
    139. 				else
    140. 				{
    141. 					if (cur == parent->_right)//左单旋
    142. 					{
    143. 						RotateL(gparent);
    144. 						parent->_color = Black;
    145. 						gparent->_color = Red;
    146. 					}
    147. 					if (cur == parent->_left)
    148. 					{
    149. 						RotateR(parent);
    150. 						RotateL(gparent);
    151. 						cur->_color = Black;
    152. 						gparent->_color = Red;
    153. 					}
    154. 					break;
    155.  
    156. 				}
    157. 			}
    158.  
    159. 		}
    160. 		_root->_color = Black;
    161. 		return pairbool>(iterator(newnode),true);
    162. 	}
    163. void RotateR(Node* parent)
    164. 	{
    165. 		Node* cur = parent->_left;
    166. 		Node* Curright = cur->_right;
    167. 		//旋转
    168. 		Node* pparent = parent->_parent;//记录该树parent节点的父节点
    169. 		cur->_right = parent;
    170. 		parent->_left = Curright;
    171. 		parent->_parent = cur;
    172. 		cur->_parent = pparent;
    173.  
    174. 		if (Curright)//cur的右子树不为空时
    175. 		{
    176. 			Curright->_parent = parent;
    177. 		}
    178.  
    179.  
    180. 		if (parent == _root)//改变根
    181. 		{
    182. 			_root = cur;
    183. 		}
    184. 		else//和上一层链接
    185. 		{
    186. 			if (pparent->_left == parent)
    187. 				pparent->_left = cur;
    188. 			else
    189. 				pparent->_right = cur;
    190. 		}
    191. 	}
    192. 	void RotateL(Node* parent)//左旋转
    193. 	{
    194. 		Node* cur = parent->_right;
    195. 		Node* Curleft = cur->_left;
    196. 		//旋转
    197. 		Node* pparent = parent->_parent;
    198. 		cur->_left = parent;
    199. 		parent->_right = Curleft;
    200. 		parent->_parent = cur;
    201. 		cur->_parent = pparent;
    202.  
    203. 		if (Curleft)//cur的左子树不为空时
    204. 		{
    205. 			Curleft->_parent = parent;
    206. 		}
    207. 		if (parent == _root)//改变根
    208. 		{
    209. 			_root = cur;
    210. 		}
    211. 		else//和上一层链接
    212. 		{
    213. 			if (pparent->_left == parent)
    214. 				pparent->_left = cur;
    215. 			else
    216. 				pparent->_right = cur;
    217. 		}
    218. 	}
    219.  
    220. 	Node* _root=nullptr;
    221. };

    迭代器类

    我们先前只说了set和map容器如何使得key不可修改，还没看const迭代器的实现，

       下面有个构造函数先前提过，是特地为了给普通迭代器构造出const迭代器准备的，当然当迭代器类是实例化成普通迭代器时，此时就是一个拷贝构造，如果是构造const迭代器，那就是一个特殊的构造函数，不过此时构造函数的参数it所在的就是在const_iterator的类域内，就不能访问私有,所以说_node不要用private修饰，就是因为只有同一类域才能访问私有，切记切记，时至今日我才理解这句话的含义。

    1. template<class T,class Ptr,class Ref>  
    2. struct _Iterator   封装的是一个节点指针_node
    3. {
    4. 	typedef _Iterator Self;  命名成self是有原因的，
    5. 因为在实现的过程中并不是立刻考虑到要多少个模板参数，如果++,--时返回类型写成这个-Iterator，如果模板参数变了，所有写了Iterator都要改
    6. 重命名为self就方便多了
    7.  
    8.           
    9. 	typedef _Iterator iterator;
    10. 这个地方就是T的大用处，因为我们set那里要用普通迭代器来构造一个const迭代器，
    11. 所以我们在类内要有一个iterator类型能接收普通迭代器。
    12.  
    13. 	typedef RBTreeNode Node;
    14. 	_Iterator(Node*node)
    15. 		:_node(node)
    16. 	{
    17. 		;
    18. 	}
    19. 	_Iterator(const iterator& it)  _node不可用private修饰
    20. 		:_node(it._node)            
    21. 	{
    22. 		;
    23. 	}
    24.  
    25. 	Self& operator--()
    26. 	{
    27. 		if (_node->_left)//如果左不为空,就访问左树最右节点
    28. 		{
    29. 			Node* cur = _node->_left;
    30. 			while (cur->_right)
    31. 			{
    32. 				cur = cur->_right;
    33. 			}
    34. 			_node = cur;
    35. 		}
    36. 		else//左为空,向上找cur和parent节点,且parent->_right==cur
    37. 		{
    38. 			Node* parent = _node->_parent;
    39. 			Node* cur = _node;
    40. 			while (parent && cur == parent->_left)
    41. 			{
    42. 				cur = parent;
    43. 				parent = parent->_parent;
    44. 			}
    45. 			_node = parent;
    46. 		}
    47. 		return *this;
    48. 	}
    49.  
    50. 	Self& operator++()//后置++
    51. 	{
    52. 		if (_node->_right)//如果右不为空,就访问右树最左节点
    53. 		{
    54. 			Node* cur = _node->_right;
    55. 			while (cur->_left)
    56. 			{
    57. 				cur = cur->_left;
    58. 			}
    59. 			_node = cur;
    60. 		}
    61. 		else
    62. 		{
    63. 			Node* cur = _node;
    64. 			Node* parent = cur->_parent;
    65. 			while (parent&&cur == parent->_left)//可能只有一个root节点
    66. 			{
    67. 				cur = cur->_parent;
    68. 				parent = parent->_parent;
    69. 			}
    70. 			_node = parent;
    71. 		}
    72. 		return (*this);//返回迭代器,this是一个迭代器类型的指针
    73. 	}
    74.  
    75. 	Self operator++(int)//前置++
    76. 	{
    77. 		Self ret = (*this);
    78. 		if (_node->_right)//如果右不为空,就访问右树最左节点
    79. 		{
    80. 			Node* cur = _node->_right;
    81. 			while (cur->_left)
    82. 			{
    83. 				cur = cur->_left;
    84. 			}
    85. 			_node = cur;
    86. 		}
    87. 		else
    88. 		{
    89. 			Node* cur = _node;
    90. 			Node* parent = cur->_parent;
    91. 			while (parent && cur == parent->_right)//可能只有一个root节点,
    92. 				//当cur为parent的左节点或者parent为空,循环结束
    93. 			{
    94. 				cur = cur->_parent;
    95. 				parent = parent->_parent;
    96. 			}
    97. 			_node = parent;
    98. 		}
    99. 		return ret;
    100. 	}
    101.  
    102. 	bool operator!=(const Self&data)   比较迭代器是否不同,就看包含节点是否相等
    103. 	{
    104. 		return _node != data._node;   data是迭代器类型,访问成员用.操作符
    105. 	}
    106.  
    107. 	Ref operator*() 返回节点数据
    108. 	{
    109. 		return _node->_data;
    110. 	}
    111.  
    112.  
    113. 	Ptr operator->()  返回节点数据的地址
    114. 	{
    115. 		return &(_node->_data);  只能返回地址
    116. 	}
    117. 	Node* _node;
    118. };

    总算写完了，一开始觉得这篇难以下手，写了一两天解决了一个又一个小问题后发现困难越来越小，有时候一件事难度太大，分成一件件小事一件件完成或许成功概率更大。

  • 相关阅读:
    JavaScript 基础语法
    算法竞赛入门【码蹄集新手村600题】(MT1280-1300）C语言
    Vue3中的Ref与Reactive：深入理解响应式编程
    前端食堂技术周刊第 100 期：TS 5.3 Beta、ViteConf2023、Rspress 1.0、Fresh 1.5、Chrome 118
    人工智能自然语言处理：N-gram和TF-IDF模型详解
    Java+vue生成报纸排版新闻页面
    一起Talk Android吧（第四百一十一回：绘制文字）
    P2014 [CTSC1997] 选课（树形DP）
    Mysql 5.7开启binlog日志
    自适应前照灯系统控制器AFS
  • 原文地址：https://blog.csdn.net/m0_62792369/article/details/133384582