devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】set和map_c++ set map

作者：繁依Fanyi0 | 2024-05-15 01:21:58

赞

踩

c++ set map

目录

一、set、map的介绍

1、set的介绍

2、map的介绍

二、红黑树的实现

1、具体框架

2、迭代器

三、set、map的实现

1、具体结构

2、仿函数

3、insert

4、迭代器

5、operator[ ]

四、完整代码

一、set、map的介绍

1、set的介绍

1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对
子集进行直接迭代。
5. set在底层是用红黑树实现的。

set主要是用来查看元素是否在某一集合中，并且它默认在set中是升序的，且不含有重复元素

set是一个关联式容器，是K的模型，它不允许有键值冗余的情况发生

set模板具有三个参数，第一个是元素类型，第二个参数是一个仿函数，默认的缺省值是less，排的是升序

并且它的拷贝和赋值都是深拷贝，代价极大，拷贝的是整棵树

 

find是set常用的接口，插入元素之后需要查找是否存在，如果能够找到返回对应位置的迭代器，如果没有找到，返回的是end

set的遍历特征是有序+去重

  1. #include <iostream>
  2. #include <set>
  3.  
  4. using namespace std;
  5.  
  6. void test_set1()
  7. {
  8.     int a[] = {1, 2, 1, 6, 3, 8, 5};
  9.     set<int> s(a, a + sizeof(a) / sizeof(int));
  10.     for(const auto& e : s)
  11.     {
  12.         cout << e << endl;
  13.     }
  14. }
  15.  
  16. int main()
  17. {
  18.     test_set1();
  19.     return 0;
  20. }

 

 

接下来就是set的删除了

  1. void test_set1()
  2. {
  3.     int a[] = {1, 2, 1, 6, 3, 8, 5};
  4.     set<int> s(a, a + sizeof(a) / sizeof(int));
  5.     for(const auto& e : s)
  6.     {
  7.         cout << e << " ";
  8.     }
  9.     s.erase(30);
  10.     for(const auto& e : s)
  11.     {
  12.         cout << e << " ";
  13.     }
  14.  
  15.     set<int>::iterator pos = s.find(20);
  16.     s.erase(pos);
  17.     for(const auto& e : s)
  18.     {
  19.         cout << e << " ";
  20.     }
  21. }

 我们发现上面我写了两种删除，那么这两种删除方式有什么区别吗？

我们先编译运行一下，我们先屏蔽掉下面删除20的代码

发现是没有任何问题的，我们寻找30，set中没有30它也不会报错，也不会删除

接下来我们使用下面的删除逻辑

 

然后我们发现他就崩了原因是：我们查找20，find没有找到它会返回end，然后我们删除end时，end指向的是最后一个元素的下一个位置，我们把它删除了，程序就会崩溃

这就是两种删除方式的区别。

正确做法

 

  1.  
  2.     set<int>::iterator pos = s.find(20);
  3.     if(pos != s.end())
  4.     {
  5.         s.erase(pos);
  6.     }
  7.     for(const auto& e : s)
  8.     {
  9.         cout << e << " ";
  10.     }

 

 

接下来是count这个函数，它会返回某元素的个数，对于set来说是没有用的，set内部相同元素个数就是1，没有就是0

 这个接口是为了保持接口一致性，主要是给multiset来使用的

multiset和set用法类似，不过就是允许键值冗余的现象存在

  1. void test_multiset()
  2. {
  3.     int a[] = {1, 2, 1, 6, 3, 8, 5};
  4.     multiset<int> ms(a, a + sizeof(a) / sizeof(int));
  5.     for(const auto& e : ms)
  6.     {
  7.         cout << e << " ";
  8.     }
  9.     cout << endl;
  10.  
  11.     cout << ms.count(1) << endl;
  12. }

 

这时我们再调用count，1的个数就变成了2

2、map的介绍

map与set也十分的相似，map是K/V的模型，set是K的模型

map也有两种

区别与set和multiset相同，只是键值是否允许冗余的差别

不过map的插入就比较特别了

 

我们发现insert的参数是一个value_type类型

 

然后我们发现它实际上是一个pair

  1. template <class T1, class T2>
  2. struct pair
  3. {
  4. typedef T1 first_type;
  5. typedef T2 second_type;
  6. T1 first;
  7. T2 second;
  8. pair(): first(T1()), second(T2())
  9. {}
  10. pair(const T1& a, const T2& b): first(a), second(b)
  11. {}
  12. };

 pair又叫做键值对：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

也就是说我们每次插入时传入一个键值对

  1. map<string, string> countMap;
  2.  
  3. countMap.insert(pair<string, string>("苹果", "apple"));

这样显得十分的麻烦，这时我们还可以借助其它函数来帮助我们自动生成pair，就不用我们每次手动传一个pair的匿名对象了

countMap.insert(make_pair("香蕉", "banana"));

同时我们还发现一个奇怪的点map的insert的返回值也是一个pair，那么这个pair中存的是什么呢？

 

通过前面的英文文档我们大概了解了返回值的含义

如果这个元素已经存在了，我们就返回该元素位置的迭代器，也就是pair的第一个参数，pair的第二个 参数就置为flase代表插入失败

如果这个元素不存在，就返回新插入元素的迭代器，返回true

insert的返回值实际上是为了[ ]操作符重载所设计的

map的operator[ ]与我们前面见到的[ ] 都不太一样

[ ]内传入的是V，返回的是K的引用

如果该元素不存在，就插入这个元素，并且调用V的默认构造

  1. void test_map()
  2. {
  3.     string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", 
  4. "苹果", "香蕉", "苹果", "香蕉" };
  5.     map<string, int> countMap;
  6.     for(const auto& e : arr)
  7.     {
  8.         countMap[e]++;
  9.     }
  10.     for(const auto& e : countMap)
  11.     {
  12.         cout << e.first << " : " << e.second << endl;
  13.     }
  14. }

 

这与我们的预期一致，最开始的时候map中什么元素都没有，正常调用[ ]一定会崩，他没有崩并且还将其插入了。

总结：

1、map中有这个key，返回value的引用 （查找，修改value）

2、map中没有这个key，会插入一个pair(key, V())，返回value的引用  （插入+修改） 

二、红黑树的实现

1、具体框架

红黑树基本代码：

  1. #pragma once
  2. #include <iostream>
  3. #include <utility>
  4. #include <cassert>
  5. #include <ctime>
  6.  
  7. using namespace std;
  8.  
  9. enum Colour
  10. {
  11. 	RED,
  12. 	BLACK
  13. };
  14.  
  15. template<class K,class V>
  16. struct RBTreeNode
  17. {
  18. 	RBTreeNode<K, V>* _left;
  19. 	RBTreeNode<K, V>* _right;
  20. 	RBTreeNode<K, V>* _parent;
  21. 	pair<const K, V> _kv;
  22. 	Colour _col;
  23.  
  24. 	RBTreeNode(const pair<const K,V>& kv)
  25. 		:_left(nullptr)
  26. 		,_right(nullptr)
  27. 		,_parent(nullptr)
  28. 		,_kv(kv)
  29. 	{}
  30. };
  31.  
  32. template<class K,class V>
  33. class RBTree
  34. {
  35. 	typedef RBTreeNode<K, V> Node;
  36. public:
  37. 	bool insert(const pair<const K, V> kv)
  38. 	{
  39. 		if (_root == nullptr)
  40. 		{
  41. 			_root = new Node(kv);
  42. 			_root->_col = BLACK;
  43. 			return true;
  44. 		}
  45.  
  46. 		Node* cur = _root;
  47. 		Node* parent = nullptr;
  48. 		while (cur)
  49. 		{
  50. 			if (cur->_kv.first < kv.first)
  51. 			{
  52. 				parent = cur;
  53. 				cur = cur->_right;
  54. 			}
  55. 			else if (cur->_kv.first > kv.first)
  56. 			{
  57. 				parent = cur;
  58. 				cur = cur->_left;
  59. 			}
  60. 			else
  61. 			{
  62. 				return false;
  63. 			}
  64. 		}
  65. 		cur = new Node(kv);
  66. 		cur->_col = RED;
  67. 		if (parent->_kv.first < kv.first)
  68. 		{
  69. 			parent->_right = cur;
  70. 		}
  71. 		else
  72. 		{
  73. 			parent->_left = cur;
  74. 		}
  75. 		cur->_parent = parent;
  76.  
  77. 		//�����ڵ���ɫ
  78. 		//�ߵ��ջ��߸��׵���ɫ�Ǻ�ɫ����ֹͣ����
  79. 		while (parent && parent->_col == RED)
  80. 		{
  81. 			Node* grandfather = parent->_parent;
  82. 			assert(grandfather);
  83. 			assert(grandfather->_col == BLACK);
  84.  
  85. 			if (parent == grandfather->_left)
  86. 			{
  87. 				Node* uncle = grandfather->_right;
  88. 				if (uncle && uncle->_col == RED)
  89. 				{
  90. 					parent->_col = uncle->_col = BLACK;
  91. 					grandfather->_col = RED;
  92.  
  93. 					cur = grandfather;
  94. 					parent = cur->_parent;
  95. 				}
  96. 				else
  97. 				{
  98. 					/*    g
  99. 					*   p
  100. 					* c
  101. 					*/
  102. 					if (cur == parent->_left)
  103. 					{
  104. 						RotateR(grandfather);
  105. 						parent->_col = BLACK;
  106. 						grandfather->_col = RED;
  107. 					}
  108. 					/*    g
  109. 					*   p    u
  110. 					*     c
  111. 					*/
  112. 					else
  113. 					{
  114. 						RotateL(parent);
  115. 						RotateR(grandfather);
  116. 						cur->_col = BLACK;
  117. 						grandfather->_col = RED;
  118. 					}
  119. 					break;
  120. 				}
  121. 			}
  122. 			else
  123. 			{
  124. 				Node* uncle = grandfather->_left;
  125. 				if (uncle && uncle->_col == RED)
  126. 				{
  127. 					parent->_col = uncle->_col = BLACK;
  128. 					grandfather->_col = RED;
  129.  
  130. 					cur = grandfather;
  131. 					parent = cur->_parent;
  132. 				}
  133. 				else
  134. 				{
  135. 					/*    g
  136. 					*         p
  137. 					*            c
  138. 					*/
  139. 					if (cur == parent->_right)
  140. 					{
  141. 						RotateL(grandfather);
  142. 						parent->_col = BLACK;
  143. 						grandfather->_col = RED;
  144. 					}
  145. 					/*    g
  146. 					*   u    p
  147. 					*      c
  148. 					*/
  149. 					else
  150. 					{
  151. 						RotateR(parent);
  152. 						RotateL(grandfather);
  153. 						cur->_col = BLACK;
  154. 						grandfather->_col = RED;
  155. 					}
  156. 				}
  157. 			}
  158. 		}
  159. 		_root->_col = BLACK;
  160. 		return true;
  161. 	}
  162.  
  163. 	void InOrder()
  164. 	{
  165. 		_InOrder(_root);
  166. 	}
  167.  
  168. 	bool IsBalance()
  169. 	{
  170. 		int benchmark = 0;
  171. 		return _PrevCheck(_root, 0, benchmark);
  172. 	}
  173.  
  174. private:
  175.  
  176. 	bool _PrevCheck(Node* root, int blackNum, int& benchmark)
  177. 	{
  178. 		if (root == nullptr)
  179. 		{
  180. 			if (benchmark == 0)
  181. 			{
  182. 				benchmark = blackNum;
  183. 				return true;
  184. 			}
  185.  
  186. 			if (blackNum != benchmark)
  187. 			{
  188. 				cout << "��ɫ�ڵ�����ͬ" << endl;
  189. 				return false;
  190. 			}
  191. 			else
  192. 			{
  193. 				return true;
  194. 			}
  195. 		}
  196. 		if (root->_col == BLACK)
  197. 		{
  198. 			blackNum++;
  199. 		}
  200.  
  201. 		if (root->_col == RED && root->_parent->_col == RED)
  202. 		{
  203. 			cout << "�������ĺ�ɫ�ڵ�" << endl;
  204. 			return false;
  205. 		}
  206.  
  207. 		return _PrevCheck(root->_left, blackNum, benchmark)
  208. 			&& _PrevCheck(root->_right, blackNum, benchmark);
  209. 	}
  210.  
  211. 	void _InOrder(Node* root)
  212. 	{
  213. 		if (root == nullptr)
  214. 		{
  215. 			return;
  216. 		}
  217.  
  218. 		_InOrder(root->_left);
  219. 		cout << root->_kv.first << " : " << root->_kv.second << endl;
  220. 		_InOrder(root->_right);
  221. 	}
  222.  
  223. 	void RotateL(Node* parent)
  224. 	{
  225. 		Node* subR = parent->_right;
  226. 		Node* subRL = subR->_left;
  227. 		parent->_right = subRL;
  228. 		if (subRL)
  229. 		{
  230. 			subRL->_parent = parent;
  231. 		}
  232. 		Node* ppNode = parent->_parent;
  233. 		subR->_left = parent;
  234. 		parent->_parent = subR;
  235. 		if (_root == parent)
  236. 		{
  237. 			_root = subR;
  238. 			subR->_parent = nullptr;
  239. 		}
  240. 		else
  241. 		{
  242. 			if (ppNode->_left == parent)
  243. 			{
  244. 				ppNode->_left = subR;
  245. 			}
  246. 			else
  247. 			{
  248. 				ppNode->_right = subR;
  249. 			}
  250. 			subR->_parent = ppNode;
  251. 		}
  252. 	}
  253.  
  254. 	void RotateR(Node* parent)
  255. 	{
  256. 		Node* subL = parent->_left;
  257. 		Node* subLR = subL->_right;
  258. 		parent->_left = subLR;
  259. 		if (subLR)
  260. 		{
  261. 			subLR->_parent = parent;
  262. 		}
  263. 		Node* ppNode = parent->_parent;//��¼parent��parent����ת���֮������
  264. 		subL->_right = parent;
  265. 		parent->_parent = subL;
  266. 		if (_root == parent)
  267. 		{
  268. 			_root = subL;
  269. 			subL->_parent = nullptr;
  270. 		}
  271. 		else
  272. 		{
  273. 			if (ppNode->_left == parent)
  274. 			{
  275. 				ppNode->_left = subL;
  276. 			}
  277. 			else
  278. 			{
  279. 				ppNode->_right = subL;
  280. 			}
  281. 			subL->_parent = ppNode;
  282. 		}
  283. 	}
  284.  
  285. 	Node* _root = nullptr;
  286. };
  287.  
  288. void testRBTree()
  289. {
  290. 	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  291. 	RBTree<int, int> rb;
  292. 	/*for (const auto& it : a)
  293. 	{
  294. 		rb.insert(make_pair(it, it));
  295. 	}*/
  296. 	//rb.InOrder();
  297. 	const size_t N = 100000;
  298. 	srand(time(0));
  299. 	for (size_t i = 0; i < N; i++)
  300. 	{
  301. 		int x = rand();
  302. 		cout << x << endl;
  303. 		rb.insert(make_pair(x, x));
  304. 	}
  305.  
  306. 	cout << rb.IsBalance() << endl;
  307. }

我们前面已经实现了红黑树的基本功能，接下来就是我们将红黑树封装一下，让它能够既能是K模型也可以是K/V模型，并且给它加上迭代器

使两种模型都能够存在，我们就要将上述的红黑树的节点存储一个模板T

T可以是K也可以是pair，这就解决了一部分问题，接下来的问题就是我们要插入节点，一定会需要进行比较，我们无法区分pair和K，虽然pair库中已经帮我们实现了<和>但是，这种实现方式并不是我们想要的

 

我们的map是只比较pair的第一个元素，库中实现的无法满足我们的需求，我们只好借助与仿函数来实现，我们使用仿函数来获取pair的第一个元素，仿函数的具体实现我们并不关系

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

树的节点内容已经变更为data

2、迭代器

红黑树的迭代器比较像我们的list的迭代器，它们同样不是连续的物理地址空间

  1. template<class T, class Ref, class Ptr>
  2. struct __RBTree_iterator
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5. 	typedef __RBTree_iterator<T, Ref, Ptr> self;
  6.  
  7. 	Node* _node;
  8. };

我们还是写一个结构体，重载它的操作符

对于迭代器来说解引用一定会返回这个节点的值，对于K模型来说就是K，对于K/V模型来说就是pair    ->操作符同样道理，只有指针才会有->操作，所以我们要返回的是节点的地址

  1. 	Ref operator*()
  2. 	{
  3. 		return _node->_data;
  4. 	}
  5.  
  6. 	Ptr operator->() 
  7. 	{
  8. 		return &_node->_data;
  9. 	}

接下来是=操作符重载和 != 操作符重载，这两个操作符十分的重要，遍历容器时一定会用上

  1. 	bool operator!=(const self& s) const
  2. 	{
  3. 		return _node != s._node;
  4. 	}
  5.  
  6. 	bool operator==(const self& s) const
  7. 	{
  8. 		return _node == s._node;
  9. 	}

接下来就是++和--  我们先来看++

假如我们的迭代器现在指向8，按照中序遍历的规则，它的下一个元素就是10，它是8的右子树的最左节点

而如果我们的迭代器指向7呢？

就需要我们去寻找祖先里面孩子不是祖先的右的那个

  1. 	self& operator++()
  2. 	{
  3. 		if(_node->_right)
  4. 		{
  5. 			Node* cur = _node-> _right;
  6. 			while(cur->_left)
  7. 			{
  8. 				cur = cur->_left;
  9. 			}
  10. 			_node = cur;
  11. 		}
  12. 		else
  13. 		{
  14. 			Node* parent = _node->_parent;
  15. 			Node* cur = _node;
  16. 			while(parent && cur == parent->_right)
  17. 			{
  18. 				cur = cur->_parent;
  19. 				parent = parent->_parent;
  20. 			}
  21. 			_node = parent;
  22. 		}
  23. 		return *this;
  24. 	}

对于--就完全跟++相反

  1. 	self& operator--()
  2. 	{
  3. 		if(_node->_left)
  4. 		{
  5. 			Node* cur = _node-> _left;
  6. 			while(cur->_right)
  7. 			{
  8. 				cur = cur->_right;
  9. 			}
  10. 			_node = cur;
  11. 		}
  12. 		else
  13. 		{
  14. 			Node* parent = _node->_parent;
  15. 			Node* cur = _node;
  16. 			while(parent && cur == parent->_left)
  17. 			{
  18. 				cur = cur->_parent;
  19. 				parent = parent->_parent;
  20. 			}
  21. 			_node = parent;
  22. 		}
  23. 		return *this;
  24. 	}

红黑树迭代器实现

  1.  
  2. template<class T, class Ref, class Ptr>
  3. struct __RBTree_iterator
  4. {
  5. 	typedef RBTreeNode<T> Node;
  6. 	typedef __RBTree_iterator<T, Ref, Ptr> self;
  7.  
  8. 	Node* _node;
  9. 	__RBTree_iterator(Node* node)
  10. 		:_node(node)
  11. 	{}
  12.  
  13. 	Ref operator*()
  14. 	{
  15. 		return _node->_data;
  16. 	}
  17.  
  18. 	Ptr operator->() 
  19. 	{
  20. 		return &_node->_data;
  21. 	}
  22.  
  23. 	self& operator++()
  24. 	{
  25. 		if(_node->_right)
  26. 		{
  27. 			Node* cur = _node-> _right;
  28. 			while(cur->_left)
  29. 			{
  30. 				cur = cur->_left;
  31. 			}
  32. 			_node = cur;
  33. 		}
  34. 		else
  35. 		{
  36. 			Node* parent = _node->_parent;
  37. 			Node* cur = _node;
  38. 			while(parent && cur == parent->_right)
  39. 			{
  40. 				cur = cur->_parent;
  41. 				parent = parent->_parent;
  42. 			}
  43. 			_node = parent;
  44. 		}
  45. 		return *this;
  46. 	}
  47.  
  48. 	self& operator--()
  49. 	{
  50. 		if(_node->_left)
  51. 		{
  52. 			Node* cur = _node-> _left;
  53. 			while(cur->_right)
  54. 			{
  55. 				cur = cur->_right;
  56. 			}
  57. 			_node = cur;
  58. 		}
  59. 		else
  60. 		{
  61. 			Node* parent = _node->_parent;
  62. 			Node* cur = _node;
  63. 			while(parent && cur == parent->_left)
  64. 			{
  65. 				cur = cur->_parent;
  66. 				parent = parent->_parent;
  67. 			}
  68. 			_node = parent;
  69. 		}
  70. 		return *this;
  71. 	}
  72.  
  73. 	bool operator!=(const self& s) const
  74. 	{
  75. 		return _node != s._node;
  76. 	}
  77.  
  78. 	bool operator==(const self& s) const
  79. 	{
  80. 		return _node == s._node;
  81. 	}
  82.  
  83. };

接下来回到红黑树的整体框架

红黑树的begin一定是返回中序遍历的第一个节点，也就是我们的最左节点(如果最左节点存在) 

红黑树的end是中序遍历的最后一个节点的下一个节点，也就是nullptr

  1. 	typedef __RBTree_iterator<T, T&, T*> iterator;
  2. 	typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
  3.  
  4. 	iterator begin()
  5. 	{
  6. 		Node* left = _root;
  7. 		while (left && left->_left)
  8. 		{
  9. 			left = left->_left;
  10. 		}
  11. 		return iterator(left);
  12. 	}
  13.  
  14. 	const_iterator begin() const
  15. 	{
  16. 		Node* left = _root;
  17. 		while (left && left->_left)
  18. 		{
  19. 			left = left->_left;
  20. 		}
  21.  
  22. 		return iterator(left);
  23. 	}
  24.  
  25. 	iterator end()
  26. 	{
  27. 		return iterator(nullptr);
  28. 	}
  29.  
  30. 	const_iterator end() const
  31. 	{
  32. 		return iterator(nullptr);
  33. 	}

最后就剩下insert的修改了

insert就是将返回值修改为pair，再根据不同的情况返回不同的值

如果已经存在这个值了，再插入就返回该元素迭代器和false组成的pair

没有这个值，就插入再返回该元素迭代器和true组成的pair

  1. 	pair<iterator, bool> insert(const T& data)
  2. 	{
  3. 		KeyOfT k2t;
  4. 		if (_root == nullptr)
  5. 		{
  6. 			_root = new Node(data);
  7. 			_root->_col = BLACK;
  8. 			return make_pair(iterator(_root), true);
  9. 		}
  10.  
  11. 		Node* cur = _root;
  12. 		Node* parent = nullptr;
  13. 		while (cur)
  14. 		{
  15. 			if (k2t(cur->_data) < k2t(data))
  16. 			{
  17. 				parent = cur;
  18. 				cur = cur->_right;
  19. 			}
  20. 			else if (k2t(cur->_data) > k2t(data))
  21. 			{
  22. 				parent = cur;
  23. 				cur = cur->_left;
  24. 			}
  25. 			else
  26. 			{
  27. 				return make_pair(iterator(cur), false);
  28. 			}
  29. 		}
  30. 		cur = new Node(data);
  31. 		Node* newNode = cur;
  32. 		cur->_col = RED;
  33. 		if (k2t(parent->_data) < k2t(data))
  34. 		{
  35. 			parent->_right = cur;
  36. 		}
  37. 		else
  38. 		{
  39. 			parent->_left = cur;
  40. 		}
  41. 		cur->_parent = parent;
  42.  
  43. 		while (parent && parent->_col == RED)
  44. 		{
  45. 			Node* grandfather = parent->_parent;
  46. 			assert(grandfather);
  47. 			assert(grandfather->_col == BLACK);
  48.  
  49. 			if (parent == grandfather->_left)
  50. 			{
  51. 				Node* uncle = grandfather->_right;
  52. 				if (uncle && uncle->_col == RED)
  53. 				{
  54. 					parent->_col = uncle->_col = BLACK;
  55. 					grandfather->_col = RED;
  56.  
  57. 					cur = grandfather;
  58. 					parent = cur->_parent;
  59. 				}
  60. 				else
  61. 				{
  62. 					/*    g
  63. 					*   p
  64. 					* c
  65. 					*/
  66. 					if (cur == parent->_left)
  67. 					{
  68. 						RotateR(grandfather);
  69. 						parent->_col = BLACK;
  70. 						grandfather->_col = RED;
  71. 					}
  72. 					/*    g
  73. 					*   p    u
  74. 					*     c
  75. 					*/
  76. 					else
  77. 					{
  78. 						RotateL(parent);
  79. 						RotateR(grandfather);
  80. 						cur->_col = BLACK;
  81. 						grandfather->_col = RED;
  82. 					}
  83. 					break;
  84. 				}
  85. 			}
  86. 			else
  87. 			{
  88. 				Node* uncle = grandfather->_left;
  89. 				if (uncle && uncle->_col == RED)
  90. 				{
  91. 					parent->_col = uncle->_col = BLACK;
  92. 					grandfather->_col = RED;
  93.  
  94. 					cur = grandfather;
  95. 					parent = cur->_parent;
  96. 				}
  97. 				else
  98. 				{
  99. 					/*    g
  100. 					*         p
  101. 					*            c
  102. 					*/
  103. 					if (cur == parent->_right)
  104. 					{
  105. 						RotateL(grandfather);
  106. 						parent->_col = BLACK;
  107. 						grandfather->_col = RED;
  108. 					}
  109. 					/*    g
  110. 					*   u    p
  111. 					*      c
  112. 					*/
  113. 					else
  114. 					{
  115. 						RotateR(parent);
  116. 						RotateL(grandfather);
  117. 						cur->_col = BLACK;
  118. 						grandfather->_col = RED;
  119. 					}
  120. 				}
  121. 			}
  122. 		}
  123. 		_root->_col = BLACK;
  124. 		return make_pair(iterator(newNode), true);
  125. 	}

三、set、map的实现

set和map的底层都是红黑树，我们只要将红黑树稍微修改就可以实现set和map了

但是这里有一个问题，set是K的模型map是K/V的模型，它是两棵树，难道我们要写两棵红黑树，一个是K的模型，一个是K/V的模型吗？

其实并不需要，我们查看一下stl源码的实现

我们发现它的红黑树的参数T，set传的是K，map传的是一个pair这样就完美的解决了到底是K的模型还是K/V的模型的问题了。不过在我们find和insert的时候又会有其他的问题了，我们查找时，因为是红黑树，所以我们需要节点存的值进行比较，可是对于set来说还好直接比较K

但是map的T是一个pair，虽然pair库中已经帮我们实

 

1、具体结构

对于set和map而言，我们只需要封装红黑树的迭代器和insert就好了，set和map内部其实什么都没有，就好像栈和队列一样

  1. #include "RBTree.hpp"
  2.  
  3. template<class K>
  4. class set
  5. {
  6.     
  7. public:
  8.  
  9. private:
  10.     RBTree<K, K, K2T> _t;
  11. };

  1.  
  2. template<class K, class V>
  3. class map
  4. {
  5.  
  6. public:
  7.  
  8. private:
  9.     RBTree<K, pair<K, V>, K2T> _m; 
  10. };

这就是最简单的

2、仿函数

根据是map还是set设计出的仿函数是不同的，不过都是返回K

  1. //set仿函数
  2.  
  3. struct K2T
  4.     {
  5.         const K& operator()(const K& key)
  6.         {
  7.             return key;
  8.         }
  9.     };

  1. //map仿函数
  2.  
  3. struct K2T
  4.     {
  5.         const K& operator()(const pair<K, V>& kv)
  6.         {
  7.             return kv.first;
  8.         }
  9.     };

3、insert

insert其实特别的简单,我们只需要调用红黑树的insert就可以了

  1. //set
  2.     pair<iterator, bool> insert(const K& key)
  3.     {
  4.         _t.insert(key);
  5.     }
  6.  
  7.  
  8.    
  9. //map
  10.  pair<iterator, bool> insert(const pair<K, V>& kv)
  11.     {
  12.         return _m.insert(kv);
  13.     }
  14.  
  15.  
  16.

4、迭代器

同理调用红黑树的

  1.    iterator begin()
  2.     {
  3.         return _t.begin();
  4.     }
  5.  
  6.     const_iterator begin() const
  7.     {
  8.         return _t.begin();
  9.     }
  10.  
  11.     iterator end()
  12.     {
  13.         return _t.end();
  14.     }
  15.  
  16.     const_iterator end() const
  17.     {
  18.         return _t.end();
  19.     }

5、operator[ ]

这个是map独有的，我们前面已经介绍了原理，所以我们直接拿出代码

  1.    V& operator[](const K& key)
  2.     {
  3.         pair<iterator, bool> ret = insert(make_pair(key, V()));
  4.         return ret.first->second;
  5.     }

四、完整代码

  1. //RBTree.hpp
  2. #pragma once
  3. #include <iostream>
  4. #include <utility>
  5. #include <cassert>
  6. #include <ctime>
  7.  
  8. using namespace std;
  9.  
  10. enum Colour
  11. {
  12. 	RED,
  13. 	BLACK
  14. };
  15.  
  16. template<class T>
  17. struct RBTreeNode
  18. {
  19. 	RBTreeNode<T>* _left;
  20. 	RBTreeNode<T>* _right;
  21. 	RBTreeNode<T>* _parent;
  22. 	T _data;
  23. 	Colour _col;
  24.  
  25. 	RBTreeNode(const T& data)
  26. 		:_left(nullptr)
  27. 		,_right(nullptr)
  28. 		,_parent(nullptr)
  29. 		,_data(data)
  30. 	{}
  31. };
  32.  
  33. template<class T, class Ref, class Ptr>
  34. struct __RBTree_iterator
  35. {
  36. 	typedef RBTreeNode<T> Node;
  37. 	typedef __RBTree_iterator<T, Ref, Ptr> self;
  38.  
  39. 	Node* _node;
  40. 	__RBTree_iterator(Node* node)
  41. 		:_node(node)
  42. 	{}
  43.  
  44. 	Ref operator*()
  45. 	{
  46. 		return _node->_data;
  47. 	}
  48.  
  49. 	Ptr operator->() 
  50. 	{
  51. 		return &_node->_data;
  52. 	}
  53.  
  54. 	self& operator++()
  55. 	{
  56. 		if(_node->_right)
  57. 		{
  58. 			Node* cur = _node-> _right;
  59. 			while(cur->_left)
  60. 			{
  61. 				cur = cur->_left;
  62. 			}
  63. 			_node = cur;
  64. 		}
  65. 		else
  66. 		{
  67. 			Node* parent = _node->_parent;
  68. 			Node* cur = _node;
  69. 			while(parent && cur == parent->_right)
  70. 			{
  71. 				cur = cur->_parent;
  72. 				parent = parent->_parent;
  73. 			}
  74. 			_node = parent;
  75. 		}
  76. 		return *this;
  77. 	}
  78.  
  79. 	self& operator--()
  80. 	{
  81. 		if(_node->_left)
  82. 		{
  83. 			Node* cur = _node-> _left;
  84. 			while(cur->_right)
  85. 			{
  86. 				cur = cur->_right;
  87. 			}
  88. 			_node = cur;
  89. 		}
  90. 		else
  91. 		{
  92. 			Node* parent = _node->_parent;
  93. 			Node* cur = _node;
  94. 			while(parent && cur == parent->_left)
  95. 			{
  96. 				cur = cur->_parent;
  97. 				parent = parent->_parent;
  98. 			}
  99. 			_node = parent;
  100. 		}
  101. 		return *this;
  102. 	}
  103.  
  104. 	bool operator!=(const self& s) const
  105. 	{
  106. 		return _node != s._node;
  107. 	}
  108.  
  109. 	bool operator==(const self& s) const
  110. 	{
  111. 		return _node == s._node;
  112. 	}
  113.  
  114. };
  115.  
  116. template<class K, class T, class KeyOfT>
  117. class RBTree
  118. {
  119. 	typedef RBTreeNode<T> Node;
  120. public:
  121. 	typedef __RBTree_iterator<T, T&, T*> iterator;
  122. 	typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
  123.  
  124. 	iterator begin()
  125. 	{
  126. 		Node* left = _root;
  127. 		while (left && left->_left)
  128. 		{
  129. 			left = left->_left;
  130. 		}
  131. 		return iterator(left);
  132. 	}
  133.  
  134. 	const_iterator begin() const
  135. 	{
  136. 		Node* left = _root;
  137. 		while (left && left->_left)
  138. 		{
  139. 			left = left->_left;
  140. 		}
  141.  
  142. 		return iterator(left);
  143. 	}
  144.  
  145. 	iterator end()
  146. 	{
  147. 		return iterator(nullptr);
  148. 	}
  149.  
  150. 	const_iterator end() const
  151. 	{
  152. 		return iterator(nullptr);
  153. 	}
  154.  
  155. 	pair<iterator, bool> insert(const T& data)
  156. 	{
  157. 		KeyOfT k2t;
  158. 		if (_root == nullptr)
  159. 		{
  160. 			_root = new Node(data);
  161. 			_root->_col = BLACK;
  162. 			return make_pair(iterator(_root), true);
  163. 		}
  164.  
  165. 		Node* cur = _root;
  166. 		Node* parent = nullptr;
  167. 		while (cur)
  168. 		{
  169. 			if (k2t(cur->_data) < k2t(data))
  170. 			{
  171. 				parent = cur;
  172. 				cur = cur->_right;
  173. 			}
  174. 			else if (k2t(cur->_data) > k2t(data))
  175. 			{
  176. 				parent = cur;
  177. 				cur = cur->_left;
  178. 			}
  179. 			else
  180. 			{
  181. 				return make_pair(iterator(cur), false);
  182. 			}
  183. 		}
  184. 		cur = new Node(data);
  185. 		Node* newNode = cur;
  186. 		cur->_col = RED;
  187. 		if (k2t(parent->_data) < k2t(data))
  188. 		{
  189. 			parent->_right = cur;
  190. 		}
  191. 		else
  192. 		{
  193. 			parent->_left = cur;
  194. 		}
  195. 		cur->_parent = parent;
  196.  
  197. 		while (parent && parent->_col == RED)
  198. 		{
  199. 			Node* grandfather = parent->_parent;
  200. 			assert(grandfather);
  201. 			assert(grandfather->_col == BLACK);
  202.  
  203. 			if (parent == grandfather->_left)
  204. 			{
  205. 				Node* uncle = grandfather->_right;
  206. 				if (uncle && uncle->_col == RED)
  207. 				{
  208. 					parent->_col = uncle->_col = BLACK;
  209. 					grandfather->_col = RED;
  210.  
  211. 					cur = grandfather;
  212. 					parent = cur->_parent;
  213. 				}
  214. 				else
  215. 				{
  216. 					/*    g
  217. 					*   p
  218. 					* c
  219. 					*/
  220. 					if (cur == parent->_left)
  221. 					{
  222. 						RotateR(grandfather);
  223. 						parent->_col = BLACK;
  224. 						grandfather->_col = RED;
  225. 					}
  226. 					/*    g
  227. 					*   p    u
  228. 					*     c
  229. 					*/
  230. 					else
  231. 					{
  232. 						RotateL(parent);
  233. 						RotateR(grandfather);
  234. 						cur->_col = BLACK;
  235. 						grandfather->_col = RED;
  236. 					}
  237. 					break;
  238. 				}
  239. 			}
  240. 			else
  241. 			{
  242. 				Node* uncle = grandfather->_left;
  243. 				if (uncle && uncle->_col == RED)
  244. 				{
  245. 					parent->_col = uncle->_col = BLACK;
  246. 					grandfather->_col = RED;
  247.  
  248. 					cur = grandfather;
  249. 					parent = cur->_parent;
  250. 				}
  251. 				else
  252. 				{
  253. 					/*    g
  254. 					*         p
  255. 					*            c
  256. 					*/
  257. 					if (cur == parent->_right)
  258. 					{
  259. 						RotateL(grandfather);
  260. 						parent->_col = BLACK;
  261. 						grandfather->_col = RED;
  262. 					}
  263. 					/*    g
  264. 					*   u    p
  265. 					*      c
  266. 					*/
  267. 					else
  268. 					{
  269. 						RotateR(parent);
  270. 						RotateL(grandfather);
  271. 						cur->_col = BLACK;
  272. 						grandfather->_col = RED;
  273. 					}
  274. 				}
  275. 			}
  276. 		}
  277. 		_root->_col = BLACK;
  278. 		return make_pair(iterator(newNode), true);
  279. 	}
  280.  
  281. private:
  282.  
  283. 	void RotateL(Node* parent)
  284. 	{
  285. 		Node* subR = parent->_right;
  286. 		Node* subRL = subR->_left;
  287. 		parent->_right = subRL;
  288. 		if (subRL)
  289. 		{
  290. 			subRL->_parent = parent;
  291. 		}
  292. 		Node* ppNode = parent->_parent;
  293. 		subR->_left = parent;
  294. 		parent->_parent = subR;
  295. 		if (_root == parent)
  296. 		{
  297. 			_root = subR;
  298. 			subR->_parent = nullptr;
  299. 		}
  300. 		else
  301. 		{
  302. 			if (ppNode->_left == parent)
  303. 			{
  304. 				ppNode->_left = subR;
  305. 			}
  306. 			else
  307. 			{
  308. 				ppNode->_right = subR;
  309. 			}
  310. 			subR->_parent = ppNode;
  311. 		}
  312. 	}
  313.  
  314. 	void RotateR(Node* parent)
  315. 	{
  316. 		Node* subL = parent->_left;
  317. 		Node* subLR = subL->_right;
  318. 		parent->_left = subLR;
  319. 		if (subLR)
  320. 		{
  321. 			subLR->_parent = parent;
  322. 		}
  323. 		Node* ppNode = parent->_parent;
  324. 		subL->_right = parent;
  325. 		parent->_parent = subL;
  326. 		if (_root == parent)
  327. 		{
  328. 			_root = subL;
  329. 			subL->_parent = nullptr;
  330. 		}
  331. 		else
  332. 		{
  333. 			if (ppNode->_left == parent)
  334. 			{
  335. 				ppNode->_left = subL;
  336. 			}
  337. 			else
  338. 			{
  339. 				ppNode->_right = subL;
  340. 			}
  341. 			subL->_parent = ppNode;
  342. 		}
  343. 	}
  344.  
  345. 	Node* _root = nullptr;
  346. };
  347.  
  1. //set.hpp
  2. #pragma once
  3. #include "RBTree.hpp"
  4.  
  5. template<class K>
  6. class set
  7. {
  8.     struct K2T
  9.     {
  10.         const K& operator()(const K& key)
  11.         {
  12.             return key;
  13.         }
  14.     };
  15. public:
  16.     typedef typename RBTree<K, K, K2T>::iterator iterator;
  17.     typedef typename RBTree<K, K, K2T>::const_iterator const_iterator;
  18.  
  19.     iterator begin()
  20.     {
  21.         return _t.begin();
  22.     }
  23.  
  24.     const_iterator begin() const
  25.     {
  26.         return _t.begin();
  27.     }
  28.  
  29.     iterator end()
  30.     {
  31.         return _t.end();
  32.     }
  33.  
  34.     const_iterator end() const
  35.     {
  36.         return _t.end();
  37.     }
  38.  
  39.     pair<iterator, bool> insert(const K& key)
  40.     {
  41.         _t.insert(key);
  42.     }
  43. private:
  44.     RBTree<K, K, K2T> _t;
  45. };
  46.  
  47.  
  48. void test_set()
  49. {
  50.     set<int> s;
  51.     s.insert(23);
  52.     s.insert(34);
  53.     s.insert(23);
  54.     s.insert(67);
  55.     s.insert(235);
  56.     s.insert(12);
  57.     s.insert(45);
  58.     s.insert(98);
  59.     s.insert(245);
  60.     s.insert(2333);
  61.     s.insert(123);
  62.     set<int>::iterator it = s.begin();
  63.     while(it != s.end())
  64.     {
  65.         cout << *it << " ";
  66.         ++it;
  67.     }
  68.    
  69.     cout << endl;
  70. }

  1. //map.hpp
  2. #pragma once
  3. #include "RBTree.hpp"
  4.  
  5. template<class K, class V>
  6. class map
  7. {
  8.     struct K2T
  9.     {
  10.         const K& operator()(const pair<K, V>& kv)
  11.         {
  12.             return kv.first;
  13.         }
  14.     };
  15. public:
  16.     typedef typename RBTree<K, pair<K, V>, K2T>::iterator iterator;
  17.     typedef typename RBTree<K, pair<K, V>, K2T>::const_iterator const_iterator;
  18.  
  19.     iterator begin()
  20.     {
  21.         return _m.begin();
  22.     }
  23.  
  24.     const_iterator begin() const
  25.     {
  26.         return _m.begin();
  27.     }
  28.  
  29.     iterator end()
  30.     {
  31.         return _m.end();
  32.     }
  33.  
  34.     const_iterator end() const
  35.     {
  36.         return _m.end();
  37.     }
  38.  
  39.     pair<iterator, bool> insert(const pair<K, V>& kv)
  40.     {
  41.         return _m.insert(kv);
  42.     }
  43.  
  44.     V& operator[](const K& key)
  45.     {
  46.         pair<iterator, bool> ret = insert(make_pair(key, V()));
  47.         return ret.first->second;
  48.     }
  49.  
  50. private:
  51.     RBTree<K, pair<K, V>, K2T> _m; 
  52. };
  53.  
  54. void test_map()
  55. {
  56.     string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  57.  
  58. 	map<string, int> countMap;
  59. 	for (auto& str : arr)
  60. 	{
  61. 		countMap[str]++;
  62. 	}
  63. 	map<string, int>::iterator it = countMap.begin();
  64. 	while (it != countMap.end())
  65. 	{
  66. 		cout << it->first << ":" << it->second << endl;
  67. 		++it;
  68. 	}
  69.     cout << endl;
  70. 	for (auto& kv : countMap)
  71. 	{
  72. 		cout << kv.first << ":" << kv.second << endl;
  73. 	}
  74. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/570971?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号