• C++ 关联式容器map+set

    目录

    一.关联式容器

    1.关联式容器 

     2.树形结构的关联式容器

    二.键值对 

    三.set

    1.介绍

    2.set的使用

    1.set的模板参数列表

    2.构造

    3.迭代器

    4.容量操作

    5.增删查操作

    四.map

    1.介绍

    2.map的使用

    1.map的模板参数说明

    2.构造

    3.迭代器

    4.容量操作与元素访问

    5.增删查改操作

    五.multiset和multimap

    1.multiset介绍

    2.multimap介绍

    六.红黑树改造

    1.节点内部

    2.增加仿函数

    3.增加迭代器

    七.set模拟实现（封装改造红黑树）

    八.map模拟实现（封装改造红黑树）

    九.模拟实现总代码

    1.RBTree.h

    2.Set.h

    3.Map.h

    前言：map和set容器是以平衡二叉搜索树（红黑树）为底层来实现的，与接下来要学习的unordered_map和unordered_set是C++使用最多的关联式容器。

            map和set的底层是红黑树，要想学map和set的模拟实现，就要先学红黑树，而学习红黑树前建议先学AVLTree。

    AVLTree-》深入理解AVLTree【旋转控制平衡（单旋、双旋）】_糖果雨滴a的博客-CSDN博客

    红黑树-》深入理解 红黑树【满足红黑树5条规则】_糖果雨滴a的博客-CSDN博客

    一.关联式容器

    1.关联式容器 

            之前学过的vector、list、deque等容器都叫做序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

            而今天所学习的关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

     2.树形结构的关联式容器

             根据应用场景的不同，STL实现了两种不同结构的关联式容器：树型结构和哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（红黑树）作为其底层结构，容器中的元素是一个有序的序列。

    二.键值对 

            键值对是用来表示具有一一对应关系的一种结构 ，该结构中一般只包括两个成员变量key和value，key代表键值， value表示与key对应的信息。

    三.set

    1.介绍

    ① set是按照一定次序存储元素的容器

    ② 在set中，元素的value也表示key（value就是key，类型为T），并且每个value（key）必须是唯一的

    ③ 在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格若排序准则进行排序

    ④ set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代

    ⑤ set的底层是用平衡搜索二叉树（红黑树）实现的

    注意：

    ① set/multiset与map/multimap不同，map中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对

    ② set中插入元素时，只需要插入value即可，不需要构造键值对

    ③ set中的元素不可以重复（因此可以使用set进行去重）

    ④ 使用set的迭代器遍历set中的元素，可以得到有序序列

    ⑤ set中的元素默认按照小于来比较（升序）

    ⑥ set中查找某个元素时，时间复杂度为：O(log2n)

    ⑦ set中的元素不允许修改

    2.set的使用

    1.set的模板参数列表

     T： set中存放元素的类型，实际在底层存储键值对

    Compare：set中元素默认按照小于来比较

    Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

    2.构造

    set()        构造空的set

    set(Inputlterator first, Inputlterator last)        用(first, last)区间中的元素构造set

    set(const set)        set的拷贝构造

    3.迭代器

            迭代器与之前相同，依旧是正向、反向、const修饰的迭代器 

    1. // 排序 + 去重 
    2. set<int>::iterator it = s.begin();
    3. while (it != s.end())
    4. {
    5. 	//*it = 10;
    6. 	cout << *it << " ";
    7. 	++it;
    8. }
    9. cout << endl;
    10.  
    11. for (auto e : s)
    12. {
    13. 	cout << e << " ";
    14. }
    15. cout << endl;

    4.容量操作

    empty()        检测set是否为空，空返回true，否则返回false

    size()        返回set中有效元素的个数

    5.增删查操作

    pair insert(const value_type& x)          插入（在set中插入元素x，实际插                                                                                             入的是构成的键值对，如果                                                                                             插入成功，返回<该元素在set中的                                                                                             位置, true>，如果插入失败，说明                                                                                              x在set中已经存在，返回）

    void erase(iterator position)                      删除set中position位置上的元素

    size_type erase(const key_type& x)        （multiset）删除set中值为x的元素，返回删除的                                                                         元素的个数

    void erase(iterator first, iterator last)        删除set中(first, last)区间中的元素

    void swap(set& st)       交换set中的元素

    void clear()                                          将set中的元素清空

    iterator find(const key_type& x)        返回set中值为x的元素的位置

    size_type count(const key_type& x)        返回set中值为x的元素的个数

    iterator lower_bound(const value_type& val)        返回>=val的位置的迭代器

    upper_bound(const value_type& val)        返回>val的位置的迭代器

    1. void test_set1()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(2);
    7. 	s.insert(1);
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(1);
    12.  
    13. 	cout << s.erase(3) << endl;
    14. 	cout << s.erase(30) << endl;
    15.  
    16. 	for (auto e : s)
    17. 	{
    18. 		cout << e << " ";
    19. 	}
    20. 	cout << endl;
    21.  
    22. 	set<int>::iterator pos = s.find(3);
    23. 	if (pos != s.end())
    24. 		s.erase(pos);
    25.  
    26. 	for (auto e : s)
    27. 	{
    28. 		cout << e << " ";
    29. 	}
    30. 	cout << endl;
    31.  
    32. 	if (s.count(5))
    33. 	{
    34. 		cout << "5在" << endl;
    35. 	}
    36. }
    37.  
    38. void test_set2()
    39. {
    40. 	set<int> s;
    41. 	s.insert(4);
    42. 	s.insert(5);
    43. 	s.insert(1);
    44. 	s.insert(3);
    45. 	s.insert(2);
    46. 	s.insert(7);
    47. 	s.insert(9);
    48.  
    49. 	for (auto e : s)
    50. 	{
    51. 		cout << e << " ";
    52. 	}
    53. 	cout << endl;
    54.  
    55. 	// 返回>x位置的迭代器  -》 都是返回 7位置的迭代器
    56. 	//set::iterator upIt = s.upper_bound(5);  // 存在
    57. 	//upIt = s.upper_bound(6); // 不存在
    58.  
    59. 	// 删除x <=  <= y的区间 删除 [x,y]
    60. 	int x, y;
    61. 	cin >> x >> y;
    62. 	auto leftIt = s.lower_bound(x);  // [
    63. 	auto rightIt = s.upper_bound(y); // )
    64. 	s.erase(leftIt, rightIt);
    65. 	for (auto e : s)
    66. 	{
    67. 		cout << e << " ";
    68. 	}
    69. 	cout << endl;
    70. }

    四.map

    1.介绍

    ① map是关联式容器，它按照特定的次序（按照key来比较）存储由键值key和值value组合而成的元素

    ② 在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容，键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，与其取别名为pair

    ③ 在内部，map中的元素总是按照键值key进行比较排序的

    ④ map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列）

    ⑤ map支持下标访问符，即在[]中放入key，就可以找到与key对应的value

    ⑥ map的底层是用平衡搜索二叉树（红黑树）实现的

    2.map的使用

    1.map的模板参数说明

    key：键值对中key的类型

    T：键值对

    Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）

    Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

    2.构造

    map()        构造一个空的map

    3.迭代器

            迭代器与之前相同，依旧是正向、反向、const修饰的迭代器 

    1. // 遍历
    2. //map::iterator it = dict.begin();
    3. auto it = dict.begin();
    4. while (it != dict.end())
    5. {
    6. 	//cout << *it << " "; // it->operator*()
    7. 	//cout << (*it).first << ":" << (*it).second << endl;
    8. 	cout << it->first << ":" << it->second << endl;
    9. 	++it;
    10. }
    11. cout << endl;
    12.  
    13. for (const auto& kv : dict)
    14. {
    15. 	cout << kv.first << ":" << kv.second << endl;
    16. }

    4.容量操作与元素访问

    empty()        检查map中的元素是否为空

    size()        返回map中有效元素的个数

    mapped_type& operator[](const key_type& k)        返回key对应的value

    5.增删查改操作

    pair insert(const value_type& x)          在map中插入键值对x，注意x是一                                                                                             个键值对，返回值也是键值对：                                                                                                iterator代表新插入元素的位置，                                                                                                bool代表释放插入成功

    void erase(iterator position)                删除position位置上的元素

    size_type erase(const key_type& x)        删除键值为x的元素

    void erase(iterator first)                        删除(first, last)区间中的元素

    void swap(map& mp)        交换两个map中的元素

    void clear()                                             将map中的元素清空

    iterator find(const key_type& x)        在map中插入key为x的元素，找到返回该元素的位置                                                                的迭代器，否则返回end

    const_iterator find(const key_type& x)       在map中插入key为x的元素，找到返回该元素                                                                           的位置的const迭代器，否则返回cend

    size_type count(const key_type& x)        返回key为x的键值在map中的个数，注意map中                                                                       key是唯一的，因此该函数的返回值要么为0，要                                                                       么为1，因此也可以用该函数来检测一个key是否                                                                       在map中

    1. void test_map1()
    2. {
    3. 	map dict;
    4.  
    5. 	// pair构造函数
    6. 	dict.insert(pair("sort", "排序"));
    7. 	pair kv("insert", "插入");
    8. 	dict.insert(kv);
    9.  
    10. 	// make_pair
    11. 	auto ret1 = dict.insert(make_pair("left", "左边"));
    12. 	auto ret2 = dict.insert(make_pair("left", "剩余"));
    13.  
    14. 	dict["operator"] = "重载"; // 插入+修改
    15. 	dict["left"] = "左边、剩余"; // 修改
    16. 	dict["erase"];  // 插入
    17. 	cout << dict["left"] << endl; // 查找
    18.  
    19.  
    20. 	// C++11方法
    21. 	//dict.insert({ "right", "右边" });
    22.  
    23. 	// 遍历
    24. 	//map::iterator it = dict.begin();
    25. 	auto it = dict.begin();
    26. 	while (it != dict.end())
    27. 	{
    28. 		//cout << *it << " "; // it->operator*()
    29. 		//cout << (*it).first << ":" << (*it).second << endl;
    30. 		cout << it->first << ":" << it->second << endl;
    31. 		++it;
    32. 	}
    33. 	cout << endl;
    34.  
    35. 	for (const auto& kv : dict)
    36. 	{
    37. 		cout << kv.first << ":" << kv.second << endl;
    38. 	}
    39. }
    40.  
    41. void test_map2()
    42. {
    43. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    44.  
    45.     // 方法1
    46. 	/*map countMap;
    47. 	for (auto& str : arr)
    48. 	{
    49. 		map::iterator it = countMap.find(str);
    50. 		if (it != countMap.end())
    51. 		{
    52. 			it->second++;
    53. 		}
    54. 		else
    55. 		{
    56. 			countMap.insert(make_pair(str, 1));
    57. 		}
    58. 	}*/
    59.  
    60.     // 方法2
    61. 	//map countMap;
    62. 	//for (auto& str : arr)
    63. 	//{
    64. 	//	//pair::iterator, bool> ret = countMap.insert(make_pair(str, 1));
    65. 	//	auto ret = countMap.insert(make_pair(str, 1));
    66. 	//	if (ret.second == false)
    67. 	//	{
    68. 	//		ret.first->second++;
    69. 	//	}
    70. 	//}
    71.  
    72.     // 方法3
    73. 	mapint> countMap;
    74. 	for (auto& str : arr)
    75. 	{
    76. 		countMap[str]++;
    77. 	}
    78.  
    79. 	for (const auto& kv : countMap)
    80. 	{
    81. 		cout << kv.first << ":" << kv.second << endl;
    82. 	}
    83. }

    五.multiset和multimap

    1.multiset介绍

    ① multiset是按照特定顺序存储元素的容器，其中元素是可以重复的

    ② 在multiset中，元素的value也会识别它（因为multiset中本身存储的就是组成的键值对，因此value本身就是key，key就是value，类型为T），multiset元素的值不能再容器中进行修改（因为元素总是const的），但可以从容器中插入或删除

    ③ 在内部，multiset中的元素总是按照其内部比较规则（类型比较）所指示的特定严格若排序准则进行排序

    ④ multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列

    ⑤ multiset底层结构为二叉搜索树（红黑树）

    注意：

    ① multiset中在底层中存储的是的键值对

    ② multiset的插入接口中只需要插入即可

    ③ 与set的区别是，multiset中的元素可以重复，set中的元素不能重复

    ④ 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

    ⑤ multiset中的元素不能修改

    ⑥ 在multiset中找某个元素，时间复杂度为O(log2n)

    ⑦ multiset的作用：可以对元素进行排序

    2.multimap介绍

    ① multimap是关联式容器，它按照特定的顺序，存储由key和value映射的键值对，其中多个键值对直接的key是可以重复的

    ② 在multimap中，通常按照key排序和唯一的标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对

    ③ 在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的

    ④ multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列

    ⑤ multimap的底层结构为二叉搜索树（红黑树）

    注意：

    ① multimap中的key是可以重复的

    ② multimap中的元素默认将key按照小于来比较

    ③ multimap中没有重载operator[]操作

    ④ 使用时与map包含的头文件相同

    multiset和set的使用几乎相同，multimap和map的使用几乎相同（multimap不能用operator[]）

    六.红黑树改造

            map和set的模拟实现实际上就是在红黑树的基础上进行封装，因此主要实现的红黑树，红黑树实现好了，map和set只要封装一下就可以了。

    1.节点内部

            因为我们不知道要用红黑树来实现set还是map，所以我们模板参数就用一个T，并且数据用_data（而不是kv或key）。

    1. template<class T>
    2. struct RBTreeNode
    3. {
    4. 	RBTreeNode* _left;
    5. 	RBTreeNode* _right;
    6. 	RBTreeNode* _parent;
    7. 	T _data;
    8.  
    9. 	Color _col;
    10.  
    11. 	RBTreeNode(const T& data)
    12. 		: _data(data)
    13. 		, _left(nullptr)
    14. 		, _right(nullptr)
    15. 		, _parent(nullptr)
    16. 		, _col(RED)
    17. 	{}
    18. };

    2.增加仿函数

    template

    增加KeyOfT的仿函数（支持取出T对象中key的仿函数）

    set  RBTree
    map  RBTree>

            如果是set则比较好取出key进行比较，而如果是map就需要先取出kv在找到first才能进行比较，因此我们需要实现一个仿函数来进行封装。

            

            这里的插入函数就要通过创建KeyOfT类型的对象，通过仿函数来完成对于不同的T对象实现相同的操作。

    1. pairbool> Insert(const T& data)
    2. {
    3. 	// 1.搜索树的规则插入
    4. 	// 2.看是否违反平衡规则，如果违反就需要处理：旋转
    5. 	if (_root == nullptr)
    6. 	{
    7. 		_root = new Node(data);
    8. 		_root->_col = BLACK;
    9. 		return make_pair(iterator(_root), true);
    10. 	}
    11.  
    12. 	KeyOfT kot;
    13.  
    14. 	Node* parent = nullptr;
    15. 	Node* cur = _root;
    16. 	while (cur)
    17. 	{
    18. 		if (kot(cur->_data) < kot(data))
    19. 		{
    20. 			parent = cur;
    21. 			cur = cur->_right;
    22. 		}
    23. 		else if (kot(cur->_data) > kot(data))
    24. 		{
    25. 			parent = cur;
    26. 			cur = cur->_left;
    27. 		}
    28. 		else
    29. 		{
    30. 			return make_pair(iterator(cur), true);
    31. 		}
    32. 	}
    33.  
    34. 	cur = new Node(data);
    35. 	Node* newnode = cur;
    36. 	cur->_col = RED;
    37. 	if (kot(parent->_data) < kot(data))
    38. 	{
    39. 		parent->_right = cur;
    40. 	}
    41. 	else
    42. 	{
    43. 		parent->_left = cur;
    44. 	}
    45.  
    46. 	cur->_parent = parent;
    47.  
    48. 	// 存在连续红色节点
    49. 	while (parent && parent->_col == RED)
    50. 	{
    51. 		Node* grandfather = parent->_parent;
    52. 		assert(grandfather);
    53.  
    54. 		if (grandfather->_left == parent)
    55. 		{
    56. 			Node* uncle = grandfather->_right;
    57. 			// 情况一：叔叔存在且为红
    58. 			if (uncle && uncle->_col == RED)
    59. 			{
    60. 				// 变色
    61. 				parent->_col = uncle->_col = BLACK;
    62. 				grandfather->_col = RED;
    63.  
    64. 				// 继续往上处理
    65. 				cur = grandfather;
    66. 				parent = cur->_parent;
    67. 			}
    68. 			// 叔叔不存在 or 叔叔存在且为黑
    69. 			else
    70. 			{
    71. 				// 情况二：单旋(右单旋)
    72. 				if (cur == parent->_left)
    73. 				{
    74. 					//     g
    75. 					//   p
    76. 					// c
    77. 					RotateR(grandfather);
    78. 					parent->_col = BLACK;
    79. 					grandfather->_col = RED;
    80. 				}
    81. 				// 情况三：双旋(左右双旋)
    82. 				else
    83. 				{
    84. 					//     g
    85. 					//   p
    86. 					//     c
    87. 					RotateL(parent);
    88. 					RotateR(grandfather);
    89. 					cur->_col = BLACK;
    90. 					grandfather->_col = RED;
    91. 				}
    92.  
    93. 				break;
    94.  
    95. 			}
    96. 		}
    97. 		// grandfather->_right == parent
    98. 		else
    99. 		{
    100. 			Node* uncle = grandfather->_left;
    101. 			// 情况一：叔叔存在且为红
    102. 			if (uncle && uncle->_col == RED)
    103. 			{
    104. 				// 变色
    105. 				parent->_col = uncle->_col = BLACK;
    106. 				grandfather->_col = RED;
    107.  
    108. 				// 继续往上处理
    109. 				cur = grandfather;
    110. 				parent = cur->_parent;
    111. 			}
    112. 			// 叔叔不存在 or 叔叔存在且为黑
    113. 			else
    114. 			{
    115. 				// 情况二：单旋(左单旋)
    116. 				if (cur == parent->_right)
    117. 				{
    118. 					// g
    119. 					//   p
    120. 					//     c 
    121. 					RotateL(grandfather);
    122. 					parent->_col = BLACK;
    123. 					grandfather->_col = RED;
    124. 				}
    125. 				// 情况三：双旋(右左双旋)
    126. 				else
    127. 				{
    128. 					// g
    129. 					//   p
    130. 					// c
    131. 					RotateR(parent);
    132. 					RotateL(grandfather);
    133. 					cur->_col = BLACK;
    134. 					grandfather->_col = RED;
    135. 				}
    136.  
    137. 				break;
    138. 			}
    139. 		}
    140. 	}
    141.  
    142. 	_root->_col = BLACK;
    143.  
    144. 	return make_pair(iterator(newnode), true);
    145. }

    3.增加迭代器

            

    1. template<class T, class Ref, class Ptr>
    2. struct __RBTreeIterator
    3. {
    4. 	typedef RBTreeNode Node;
    5. 	typedef __RBTreeIterator Self;
    6. 	Node* _node;
    7.  
    8. 	__RBTreeIterator(Node* node)
    9. 		: _node(node)
    10. 	{}
    11.  
    12. 	Ref operator*()
    13. 	{
    14. 		return _node->_data;
    15. 	}
    16.  
    17. 	Ptr operator->()
    18. 	{
    19. 		return &_node->_data;
    20. 	}
    21.  
    22. 	Self& operator++()
    23. 	{
    24. 		if (_node->_right == nullptr)
    25. 		{
    26. 			// 找祖先里面，孩子是父亲的那个
    27. 			Node* cur = _node;
    28. 			Node* parent = cur->_parent;
    29. 			while (parent && parent->_right == cur)
    30. 			{
    31. 				cur = cur->_parent;
    32. 				parent = parent->_parent;
    33. 			}
    34.  
    35. 			_node = parent;
    36. 		}
    37. 		else
    38. 		{
    39. 			// 右子树的最左节点
    40. 			Node* subLeft = _node->_right;
    41. 			while (subLeft->_left)
    42. 			{
    43. 				subLeft = subLeft->_left;
    44. 			}
    45.  
    46. 			_node = subLeft;
    47. 		}
    48.  
    49. 		return *this;
    50. 	}
    51.  
    52. 	Self operator++(int)
    53. 	{
    54. 		Self tmp(*this);
    55.  
    56. 		++(*this);
    57.  
    58. 		return tmp;
    59. 	}
    60.  
    61. 	Self& operator--()
    62. 	{
    63. 		if (_node->_left == nullptr)
    64. 		{
    65. 			// 找祖先里面，孩子是父亲
    66. 			Node* cur = _node;
    67. 			Node* parent = cur->_parent;
    68. 			while (parent && cur == parent->_left)
    69. 			{
    70. 				cur = cur->_parent;
    71. 				parent = parent->_parent;
    72. 			}
    73.  
    74. 			_node = parent;
    75. 		}
    76. 		else
    77. 		{
    78. 			// 左子树的最右节点
    79. 			Node* subRight = _node->_left;
    80. 			while (subRight->_right)
    81. 			{
    82. 				subRight = subRight->_right;
    83. 			}
    84.  
    85. 			_node = subRight;
    86. 		}
    87.  
    88. 		return *this;
    89. 	}
    90.  
    91. 	Self operator--(int)
    92. 	{
    93. 		Self tmp(*this);
    94.  
    95. 		--(*this);
    96.  
    97. 		return tmp;
    98. 	}
    99.  
    100. 	bool operator!=(const Self& s) const
    101. 	{
    102. 		return _node != s._node;
    103. 	}
    104.  
    105. 	bool operator==(const Self& s) const
    106. 	{
    107. 		return _node == s->_node;
    108. 	}
    109. };

            这个迭代器的增加类似于链表list类的实现C++ list类（包括反向迭代器适配器的实现）_糖果雨滴a的博客-CSDN博客_list 反向迭代器

            需要我们自己去封装一个迭代器，这里的模板参数中Ref是T&，Ptr是T*，然后将节点类typedef为Node，将自己typedef为Self。 

            接下来就是分别实现各种操作符重载，operator*，->，!=，==都比较简单，这里不过多赘述。而operator++要详细的说一下。

            我们根据这个图来说明：

             

            我们实现的++是中序遍历，左子树 根 右子树。这里因为是3叉链，因此我们可以有比之前更简单的代码实现。这里我们实现迭代版的。

             这里我们可以根据当前位置的右子树是否为空来进行分情况讨论：

    第一种情况：右子树为空-》找孩子是祖先的左的那个节点

    第二种情况：右孩子不为空-》找右子树最左的那个节点

            根据上面的图来说，第一个it是5所在的迭代器，它的右子树为空，因此找它的祖先里面，孩子是父亲的左的那个，这里6是5的祖先，5是6的左，因此下一个到6的迭代器。6的右子树不为空，找到它右子树的最左节点，7的迭代器。7的右子树为空，因此往上找，6是7的祖先，但是7不是6的左节点，继续往上，8是6和7的祖先，并且7是8的左节点，因此下一个是8的迭代器。右边同理。

            代码实现：

    1. Self& operator++()
    2. {
    3. 	if (_node->_right == nullptr)
    4. 	{
    5. 		// 找祖先里面，孩子是父亲的那个
    6. 		Node* cur = _node;
    7. 		Node* parent = cur->_parent;
    8. 		while (parent && parent->_right == cur)
    9. 		{
    10. 			cur = cur->_parent;
    11. 			parent = parent->_parent;
    12. 		}
    13.  
    14. 		_node = parent;
    15. 	}
    16. 	else
    17. 	{
    18. 		// 右子树的最左节点
    19. 		Node* subLeft = _node->_right;
    20. 		while (subLeft->_left)
    21. 		{
    22. 			subLeft = subLeft->_left;
    23. 		}
    24.  
    25. 		_node = subLeft;
    26. 	}
    27.  
    28. 	return *this;
    29. }

            operator--的实现正好与++相反：

            --相当于：右子树 根 左子树

    第一种情况：左子树为空-》找孩子是祖先的右的那个节点

    第二种情况：左孩子不为空-》找左子树最右的那个节点

            代码实现： 

    1. Self& operator--()
    2. {
    3. 	if (_node->_left == nullptr)
    4. 	{
    5. 		// 找祖先里面，孩子是父亲
    6. 		Node* cur = _node;
    7. 		Node* parent = cur->_parent;
    8. 		while (parent && cur == parent->_left)
    9. 		{
    10. 			cur = cur->_parent;
    11. 			parent = parent->_parent;
    12. 		}
    13.  
    14. 		_node = parent;
    15. 	}
    16. 	else
    17. 	{
    18. 		// 左子树的最右节点
    19. 		Node* subRight = _node->_left;
    20. 		while (subRight->_right)
    21. 		{
    22. 			subRight = subRight->_right;
    23. 		}
    24.  
    25. 		_node = subRight;
    26. 	}
    27.  
    28. 	return *this;
    29. }

            这里实现的++和--都是前置的，而后置只需要调用前置的并进行一定修改即可：

    1. Self operator++(int)
    2. {
    3. 	Self tmp(*this);
    4.  
    5. 	++(*this);
    6.  
    7. 	return tmp;
    8. }
    9.  
    10. Self operator--(int)
    11. {
    12. 	Self tmp(*this);
    13.  
    14. 	--(*this);
    15.  
    16. 	return tmp;
    17. }

    七.set模拟实现（封装改造红黑树）

            通过对改造后的红黑树进行封装即可。

            注意这里实现的仿函数，直接返回key。（这里因为map，所以才要实现仿函数）

    1. namespace hb
    2. {
    3. 	template<class K>
    4. 	class set
    5. 	{
    6. 		struct SetKeyOfT
    7. 		{
    8. 			const K& operator()(const K& key)
    9. 			{
    10. 				return key;
    11. 			}
    12. 		};
    13. 	public:
    14. 		typedef typename RBTree::const_iterator iterator;
    15. 		typedef typename RBTree::const_iterator const_iterator;
    16.  
    17. 		iterator begin() const
    18. 		{
    19. 			return _t.Begin();
    20. 		}
    21.  
    22. 		iterator end() const
    23. 		{
    24. 			return _t.End();
    25. 		}
    26.  
    27. 		pairbool> insert(const K& key)
    28. 		{
    29. 			// pair::iterator, bool> ret = _t.Insert(key);
    30. 			auto ret = _t.Insert(key);
    31. 			return pairbool>(iterator(ret.first._node), ret.second);
    32. 		}
    33.  
    34. 		iterator find(const K& key)
    35. 		{
    36. 			return _t.Find(key);
    37. 		}
    38. 	private:
    39. 		RBTree _t;
    40. 	};
    41. }

    八.map模拟实现（封装改造红黑树）

            这里面仿函数返回的是kv.first。

            map比set多的还有一个operator[]，因为这个operator[]，就导致红黑树内的insert函数需要返回pair，这样实现operator[]更简单。

    1. namespace hb
    2. {
    3. 	template<class K, class V>
    4. 	class map
    5. 	{
    6. 		struct MapKeyOfT
    7. 		{
    8. 			const K& operator()(const pair& kv)
    9. 			{
    10. 				return kv.first;
    11. 			}
    12. 		};
    13. 	public:
    14. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    15. 		typedef typename RBTree, MapKeyOfT>::const_iterator const_iterator;
    16.  
    17. 		iterator begin()
    18. 		{
    19. 			return _t.Begin();
    20. 		}
    21.  
    22. 		iterator end()
    23. 		{
    24. 			return _t.End();
    25. 		}
    26.  
    27. 		pairbool> insert(const pair& kv)
    28. 		{
    29. 			return _t.Insert(kv);
    30. 		}
    31.  
    32. 		iterator find(const K& key)
    33. 		{
    34. 			return _t.Find(key);
    35. 		}
    36.  
    37. 		V& operator[](const K& key)
    38. 		{
    39. 			pairbool> ret = insert(make_pair(key, V()));
    40. 			return ret.first->second;
    41. 		}
    42.  
    43. 	private:
    44. 		RBTree, MapKeyOfT> _t;
    45. 	};
    46. }

    九.模拟实现总代码

    1.RBTree.h

    1. #pragma once
    2.  
    3. #include 
    4.  
    5. enum Color
    6. {
    7. 	RED,
    8. 	BLACK,
    9. };
    10.  
    11. template<class T>
    12. struct RBTreeNode
    13. {
    14. 	RBTreeNode* _left;
    15. 	RBTreeNode* _right;
    16. 	RBTreeNode* _parent;
    17. 	T _data;
    18.  
    19. 	Color _col;
    20.  
    21. 	RBTreeNode(const T& data)
    22. 		: _data(data)
    23. 		, _left(nullptr)
    24. 		, _right(nullptr)
    25. 		, _parent(nullptr)
    26. 		, _col(RED)
    27. 	{}
    28. };
    29.  
    30. template<class T, class Ref, class Ptr>
    31. struct __RBTreeIterator
    32. {
    33. 	typedef RBTreeNode Node;
    34. 	typedef __RBTreeIterator Self;
    35. 	Node* _node;
    36.  
    37. 	__RBTreeIterator(Node* node)
    38. 		: _node(node)
    39. 	{}
    40.  
    41. 	Ref operator*()
    42. 	{
    43. 		return _node->_data;
    44. 	}
    45.  
    46. 	Ptr operator->()
    47. 	{
    48. 		return &_node->_data;
    49. 	}
    50.  
    51. 	Self& operator++()
    52. 	{
    53. 		if (_node->_right == nullptr)
    54. 		{
    55. 			// 找祖先里面，孩子是父亲的那个
    56. 			Node* cur = _node;
    57. 			Node* parent = cur->_parent;
    58. 			while (parent && parent->_right == cur)
    59. 			{
    60. 				cur = cur->_parent;
    61. 				parent = parent->_parent;
    62. 			}
    63.  
    64. 			_node = parent;
    65. 		}
    66. 		else
    67. 		{
    68. 			// 右子树的最左节点
    69. 			Node* subLeft = _node->_right;
    70. 			while (subLeft->_left)
    71. 			{
    72. 				subLeft = subLeft->_left;
    73. 			}
    74.  
    75. 			_node = subLeft;
    76. 		}
    77.  
    78. 		return *this;
    79. 	}
    80.  
    81. 	Self operator++(int)
    82. 	{
    83. 		Self tmp(*this);
    84.  
    85. 		++(*this);
    86.  
    87. 		return tmp;
    88. 	}
    89.  
    90. 	Self& operator--()
    91. 	{
    92. 		if (_node->_left == nullptr)
    93. 		{
    94. 			// 找祖先里面，孩子是父亲
    95. 			Node* cur = _node;
    96. 			Node* parent = cur->_parent;
    97. 			while (parent && cur == parent->_left)
    98. 			{
    99. 				cur = cur->_parent;
    100. 				parent = parent->_parent;
    101. 			}
    102.  
    103. 			_node = parent;
    104. 		}
    105. 		else
    106. 		{
    107. 			// 左子树的最右节点
    108. 			Node* subRight = _node->_left;
    109. 			while (subRight->_right)
    110. 			{
    111. 				subRight = subRight->_right;
    112. 			}
    113.  
    114. 			_node = subRight;
    115. 		}
    116.  
    117. 		return *this;
    118. 	}
    119.  
    120. 	Self operator--(int)
    121. 	{
    122. 		Self tmp(*this);
    123.  
    124. 		--(*this);
    125.  
    126. 		return tmp;
    127. 	}
    128.  
    129. 	bool operator!=(const Self& s) const
    130. 	{
    131. 		return _node != s._node;
    132. 	}
    133.  
    134. 	bool operator==(const Self& s) const
    135. 	{
    136. 		return _node == s->_node;
    137. 	}
    138. };
    139.  
    140. // T决定红黑树存什么数据
    141. // set  RBTree
    142. // map  RBTree>
    143. // KeyOfT -> 支持取出T对象中key的仿函数
    144. template<class K, class T, class KeyOfT>
    145. class RBTree
    146. {
    147. 	typedef RBTreeNode Node;
    148. public:
    149. 	typedef __RBTreeIterator iterator;
    150. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    151.  
    152. 	iterator Begin()
    153. 	{
    154. 		Node* subLeft = _root;
    155. 		while (subLeft && subLeft->_left)
    156. 		{
    157. 			subLeft = subLeft->_left;
    158. 		}
    159.  
    160. 		return iterator(subLeft);
    161. 	}
    162.  
    163. 	iterator End()
    164. 	{
    165. 		return iterator(nullptr);
    166. 	}
    167.  
    168. 	const_iterator Begin() const
    169. 	{
    170. 		Node* subLeft = _root;
    171. 		while (subLeft && subLeft->_left)
    172. 		{
    173. 			subLeft = subLeft->_left;
    174. 		}
    175.  
    176. 		return const_iterator(subLeft);
    177. 	}
    178.  
    179. 	const_iterator End() const
    180. 	{
    181. 		return const_iterator(nullptr);
    182. 	}
    183.  
    184. 	pairbool> Insert(const T& data)
    185. 	{
    186. 		// 1.搜索树的规则插入
    187. 		// 2.看是否违反平衡规则，如果违反就需要处理：旋转
    188. 		if (_root == nullptr)
    189. 		{
    190. 			_root = new Node(data);
    191. 			_root->_col = BLACK;
    192. 			return make_pair(iterator(_root), true);
    193. 		}
    194.  
    195. 		KeyOfT kot;
    196.  
    197. 		Node* parent = nullptr;
    198. 		Node* cur = _root;
    199. 		while (cur)
    200. 		{
    201. 			if (kot(cur->_data) < kot(data))
    202. 			{
    203. 				parent = cur;
    204. 				cur = cur->_right;
    205. 			}
    206. 			else if (kot(cur->_data) > kot(data))
    207. 			{
    208. 				parent = cur;
    209. 				cur = cur->_left;
    210. 			}
    211. 			else
    212. 			{
    213. 				return make_pair(iterator(cur), true);
    214. 			}
    215. 		}
    216.  
    217. 		cur = new Node(data);
    218. 		Node* newnode = cur;
    219. 		cur->_col = RED;
    220. 		if (kot(parent->_data) < kot(data))
    221. 		{
    222. 			parent->_right = cur;
    223. 		}
    224. 		else
    225. 		{
    226. 			parent->_left = cur;
    227. 		}
    228.  
    229. 		cur->_parent = parent;
    230.  
    231. 		// 存在连续红色节点
    232. 		while (parent && parent->_col == RED)
    233. 		{
    234. 			Node* grandfather = parent->_parent;
    235. 			assert(grandfather);
    236.  
    237. 			if (grandfather->_left == parent)
    238. 			{
    239. 				Node* uncle = grandfather->_right;
    240. 				// 情况一：叔叔存在且为红
    241. 				if (uncle && uncle->_col == RED)
    242. 				{
    243. 					// 变色
    244. 					parent->_col = uncle->_col = BLACK;
    245. 					grandfather->_col = RED;
    246.  
    247. 					// 继续往上处理
    248. 					cur = grandfather;
    249. 					parent = cur->_parent;
    250. 				}
    251. 				// 叔叔不存在 or 叔叔存在且为黑
    252. 				else
    253. 				{
    254. 					// 情况二：单旋(右单旋)
    255. 					if (cur == parent->_left)
    256. 					{
    257. 						//     g
    258. 						//   p
    259. 						// c
    260. 						RotateR(grandfather);
    261. 						parent->_col = BLACK;
    262. 						grandfather->_col = RED;
    263. 					}
    264. 					// 情况三：双旋(左右双旋)
    265. 					else
    266. 					{
    267. 						//     g
    268. 						//   p
    269. 						//     c
    270. 						RotateL(parent);
    271. 						RotateR(grandfather);
    272. 						cur->_col = BLACK;
    273. 						grandfather->_col = RED;
    274. 					}
    275.  
    276. 					break;
    277.  
    278. 				}
    279. 			}
    280. 			// grandfather->_right == parent
    281. 			else
    282. 			{
    283. 				Node* uncle = grandfather->_left;
    284. 				// 情况一：叔叔存在且为红
    285. 				if (uncle && uncle->_col == RED)
    286. 				{
    287. 					// 变色
    288. 					parent->_col = uncle->_col = BLACK;
    289. 					grandfather->_col = RED;
    290.  
    291. 					// 继续往上处理
    292. 					cur = grandfather;
    293. 					parent = cur->_parent;
    294. 				}
    295. 				// 叔叔不存在 or 叔叔存在且为黑
    296. 				else
    297. 				{
    298. 					// 情况二：单旋(左单旋)
    299. 					if (cur == parent->_right)
    300. 					{
    301. 						// g
    302. 						//   p
    303. 						//     c 
    304. 						RotateL(grandfather);
    305. 						parent->_col = BLACK;
    306. 						grandfather->_col = RED;
    307. 					}
    308. 					// 情况三：双旋(右左双旋)
    309. 					else
    310. 					{
    311. 						// g
    312. 						//   p
    313. 						// c
    314. 						RotateR(parent);
    315. 						RotateL(grandfather);
    316. 						cur->_col = BLACK;
    317. 						grandfather->_col = RED;
    318. 					}
    319.  
    320. 					break;
    321. 				}
    322. 			}
    323. 		}
    324.  
    325. 		_root->_col = BLACK;
    326.  
    327. 		return make_pair(iterator(newnode), true);
    328. 	}
    329.  
    330. private:
    331. 	void RotateL(Node* parent)
    332. 	{
    333. 		Node* subR = parent->_right;
    334. 		Node* subRL = subR->_left;
    335.  
    336. 		parent->_right = subRL;
    337. 		if (subRL)
    338. 			subRL->_parent = parent;
    339.  
    340. 		Node* ppNode = parent->_parent;
    341.  
    342. 		subR->_left = parent;
    343. 		parent->_parent = subR;
    344.  
    345. 		if (parent == _root)
    346. 		{
    347. 			_root = subR;
    348. 			_root->_parent = nullptr;
    349. 		}
    350. 		else
    351. 		{
    352. 			if (parent == ppNode->_left)
    353. 			{
    354. 				ppNode->_left = subR;
    355. 			}
    356. 			else
    357. 			{
    358. 				ppNode->_right = subR;
    359. 			}
    360.  
    361. 			subR->_parent = ppNode;
    362. 		}
    363. 	}
    364.  
    365. 	void RotateR(Node* parent)
    366. 	{
    367. 		Node* subL = parent->_left;
    368. 		Node* subLR = subL->_right;
    369.  
    370. 		parent->_left = subLR;
    371. 		if (subLR)
    372. 			subLR->_parent = parent;
    373.  
    374. 		Node* ppNode = parent->_parent;
    375.  
    376. 		subL->_right = parent;
    377. 		parent->_parent = subL;
    378.  
    379. 		if (parent == _root)
    380. 		{
    381. 			_root = subL;
    382. 			_root->_parent = nullptr;
    383. 		}
    384. 		else
    385. 		{
    386. 			if (ppNode->_left == parent)
    387. 			{
    388. 				ppNode->_left = subL;
    389. 			}
    390. 			else
    391. 			{
    392. 				ppNode->_right = subL;
    393. 			}
    394. 			subL->_parent = ppNode;
    395. 		}
    396.  
    397. 	}
    398.  
    399. 	iterator Find(const K& key)
    400. 	{
    401. 		Node* cur = _root;
    402. 		KeyOfT kot;
    403. 		while (cur)
    404. 		{
    405. 			if (kot(cur->_data) < key)
    406. 			{
    407. 				cur = cur->_right;
    408. 			}
    409. 			else if (kot(cur->_data) > key)
    410. 			{
    411. 				cur = cur->_left;
    412. 			}
    413. 			else
    414. 			{
    415. 				return iterator(cur);
    416. 			}
    417. 		}
    418.  
    419. 		return End();
    420. 	}
    421. private:
    422. 	Node* _root = nullptr;
    423. };

    2.Set.h

    1. #pragma once
    2.  
    3. #include "RBTree.h"
    4.  
    5. namespace hb
    6. {
    7. 	template<class K>
    8. 	class set
    9. 	{
    10. 		struct SetKeyOfT
    11. 		{
    12. 			const K& operator()(const K& key)
    13. 			{
    14. 				return key;
    15. 			}
    16. 		};
    17. 	public:
    18. 		typedef typename RBTree::const_iterator iterator;
    19. 		typedef typename RBTree::const_iterator const_iterator;
    20.  
    21. 		iterator begin() const
    22. 		{
    23. 			return _t.Begin();
    24. 		}
    25.  
    26. 		iterator end() const
    27. 		{
    28. 			return _t.End();
    29. 		}
    30.  
    31. 		pairbool> insert(const K& key)
    32. 		{
    33. 			// pair::iterator, bool> ret = _t.Insert(key);
    34. 			auto ret = _t.Insert(key);
    35. 			return pairbool>(iterator(ret.first._node), ret.second);
    36. 		}
    37.  
    38. 		iterator find(const K& key)
    39. 		{
    40. 			return _t.Find(key);
    41. 		}
    42. 	private:
    43. 		RBTree _t;
    44. 	};
    45. }

    3.Map.h

    1. #pragma once
    2.  
    3. #include "RBTree.h"
    4.  
    5. namespace hb
    6. {
    7. 	template<class K, class V>
    8. 	class map
    9. 	{
    10. 		struct MapKeyOfT
    11. 		{
    12. 			const K& operator()(const pair& kv)
    13. 			{
    14. 				return kv.first;
    15. 			}
    16. 		};
    17. 	public:
    18. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    19. 		typedef typename RBTree, MapKeyOfT>::const_iterator const_iterator;
    20.  
    21. 		iterator begin()
    22. 		{
    23. 			return _t.Begin();
    24. 		}
    25.  
    26. 		iterator end()
    27. 		{
    28. 			return _t.End();
    29. 		}
    30.  
    31. 		pairbool> insert(const pair& kv)
    32. 		{
    33. 			return _t.Insert(kv);
    34. 		}
    35.  
    36. 		iterator find(const K& key)
    37. 		{
    38. 			return _t.Find(key);
    39. 		}
    40.  
    41. 		V& operator[](const K& key)
    42. 		{
    43. 			pairbool> ret = insert(make_pair(key, V()));
    44. 			return ret.first->second;
    45. 		}
    46.  
    47. 	private:
    48. 		RBTree, MapKeyOfT> _t;
    49. 	};
    50.  
    51. 	void test_map1()
    52. 	{
    53. 		mapint> m;
    54. 		m.insert(make_pair("111", 1));
    55. 		m.insert(make_pair("555", 5));
    56. 		m.insert(make_pair("333", 3));
    57. 		m.insert(make_pair("222", 2));
    58.  
    59. 		mapint>::iterator it = m.begin();
    60. 		while (it != m.end())
    61. 		{
    62. 			cout << it->first << ":" << it->second << endl;
    63. 			++it;
    64. 		}
    65. 		cout << endl;
    66.  
    67. 		for (auto& kv : m)
    68. 		{
    69. 			cout << kv.first << ":" << kv.second << endl;
    70. 		}
    71. 		cout << endl;
    72. 	}
    73. }
  • 相关阅读:
    两利好因素携手而至 美元指数或逼近年内高点？
    「Spring Boot 系列」02. Spring Boot的目录结构和启动方式
    Python 基础（一）：初识 Python
    vue 前端 问题整理
    Jvm之内存泄漏
    Wireshark过滤DNS协议包语法实战
    Centos7 安装部署Kubernetes(k8s)集群
    vue3 源码解析（1）— reactive 响应式实现
    React工具
    学习笔记4--导航与定位技术
  • 原文地址：https://blog.csdn.net/qq_60750110/article/details/126088494