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

C++：map和set的封装

作者：Monodyee | 2024-05-30 05:13:50

赞

踩

C++：map和set的封装

      关于红黑树的模拟实现，大家不清楚的先去看看博主的博客再来看这篇文章，因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容，而更多的是去为了契合STL中的红黑树去进行改造，让封装的set和map能够去复用我们的这份代码

DS进阶：AVL树和红黑树-CSDN博客

      在模拟实现之前，我们肯定要尝试去看看源码是如何实现的！我们会发现其实map和set的底层都是用的红黑树去封装的

      但是你可能会有这样的疑惑，map是kv模型，set是k模型，那难道stl底层封装了两颗红黑树么？？其实并不是的，创建stl的大佬们为了增加代码的复用性，想方设法地想让map和set同时复用一颗红黑树。而解决方法就是通过控制模版参数来区分map和set。

     既然底层是套的红黑树的壳子，我们就要来研究库里面的红黑树究竟通过了什么方法来让map和set都能够复用这份代码。

一、STL中的红黑树

1.1 利用模版参数控制和区分map和set

我们先来看看stl中的红黑树的模版参数，然后进行分析

   接下来我们来看看第三个模版参数的作用究竟是什么

总结：

第1个模版参数是为了帮助我们拿到Key的类型，因为find、erase的接口都是Key类型比较方便

第2个模版参数决定了红黑树节点中存的是key还是pair，以此来区分map和set

第3个模版参数是通过仿函数决定了是拿什么去进行比较，对set来说就是拿key，对pair来说就是拿他的first。

第4个模版参数是具体的比较逻辑，比如说我们传的是指针，但是我们并不想通过指针比而是通过指针解引用的类型比，就可以通过传这个仿函数去控制其比较的行为。

第5个是stl实现的一个堆内存管理器，是为了提高从堆区申请内存的效率，基本上所有的stl容器都会涉及到这个，所以目前暂时不需要太在意！

1.2 stl中的红黑树结构

在该图中，设置了一个哨兵节点，哨兵节点的左指向最小节点5，最大节点的右指向哨兵节点header， 为什么要这样设计呢？？

      STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位
置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最
后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：
 

       但是这样虽然方便我们找到第一个节点和最后一个节点，但是每一次都要最最左端和最右端的节点进行和头节点之间的联系，其实比较麻烦，所以下面我们直接改造成不带哨兵节点的红黑树。去模拟实现迭代器。

1.3 改造并模拟实现红黑树的迭代器

但是最最关键的逻辑就是，实现++和--这样迭代器才能跑的起来，下面我们来进行分析

迭代器的封装

  1. template<class T,class Ref,class Ptr>
  2. struct _RBTreeIterator
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5.     typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器
  6.     typedef _RBTreeIterator<T, T&, T*> iterator; //用来转化成const迭代器
  7.     Node* _node;
  8.  
  9. 	_RBTreeIterator(Node* node)  //利用节点去构造迭代器
  10. 		:_node(node)
  11. 	{}
  12.  
  13.  
  14. 	// 1、typedef __RBTreeIterator<T, T&, T*> itertaor;  拷贝构造
  15. 	// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
  16. 	//  支持普通迭代器构造const迭代器的构造函数
  17.  
  18. 	_RBTreeIterator(const iterator& it) //隐私类型转化
  19. 		:_node(it._node)
  20. 	{}
  21.  
  22.  
  23.  
  24.  
  25. 	Ref operator*()
  26. 	{
  27. 		return _node->_data; //解引用拿到对应的东西  map拿到pair set拿到key
  28. 	}
  29.  
  30. 	Ptr operator->() //返回对应的指针类型
  31. 	{
  32. 		return &operator*();
  33. 	}
  34.  
  35. 	bool operator!=(const Self& s)
  36. 	{
  37. 		return _node != s._node;//判断两个迭代器是否相同
  38. 	}
  39.  
  40. 	bool operator==(const Self& s)
  41. 	{
  42. 		return _node == s._node;//判断两个迭代器是否相同
  43. 	}
  44.  
  45. 	Self& operator++()  //实现迭代器的++
  46. 	{
  47. 		if (_node->_right)
  48. 		{
  49. 		   //如有右不为空，那么就去找到  右子树的最左路节点
  50. 			Node* subright = _node->_right;
  51. 			while (subright->_left)  subright = subright->_left; //找到最左路节点
  52. 			_node = subright;
  53. 		}
  54. 		else
  55. 		{
  56. 		   //右为空，沿着到根的路径，找孩子是父亲左的那个祖先
  57. 			Node* cur = _node;
  58. 			Node* parent = cur->_parent;
  59. 			while (parent && parent->_right == cur)
  60. 			{
  61. 				cur = parent;
  62. 				parent = parent->_parent;
  63. 			}
  64. 			_node = parent;
  65. 		}
  66. 		return *this;
  67. 	}
  68.  
  69.      Self operator++(int)  //实现迭代器的后置++
  70.     {
  71. 	Self temp = *this;
  72. 	++*this;
  73. 	return temp;
  74.     }
  75.  
  76. 	Self& operator--()  //实现迭代器的--     右  根  左
  77. 	{
  78. 		if (_node->_left)
  79. 		{
  80. 			//如有左不为空，那么就去找到  左子树的最右路节点
  81. 			Node* subright = _node->_left;
  82. 			while (subright->_right)  subright = subright->_right; //找到最左路节点
  83. 			_node = subright;
  84. 		}
  85. 		else
  86. 		{
  87. 			//左为空，沿着到根的路径，找孩子是父亲右的那个祖先
  88. 			Node* cur = _node;
  89. 			Node* parent = cur->_parent;
  90. 			while (parent && parent->_left == cur)
  91. 			{
  92. 				cur = parent;
  93. 				parent = parent->_parent;
  94. 			}
  95. 			_node = parent;
  96. 		}
  97. 		return *this;
  98. 	}
  99.  
  100.  
  101.    Self operator--(int)  //实现迭代器的后置--
  102. {
  103. 	Self temp = *this;
  104. 	--*this;
  105. 	return temp;
  106. }
  107. };

1.4 红黑树实现的全部代码 

  1. enum Colour
  2. {
  3. 	RED,
  4. 	BLACK,
  5. };
  6.  
  7. template<class T> //T表示传的是K还是pair
  8. struct RBTreeNode
  9. {
  10. 	RBTreeNode<T>* _left;
  11. 	RBTreeNode<T>* _right;
  12. 	RBTreeNode<T>* _parent;
  13. 	T _data;
  14. 	Colour _col;
  15.  
  16. 	RBTreeNode(const T& data)
  17. 		: _left(nullptr)
  18. 		, _right(nullptr)
  19. 		, _parent(nullptr)
  20. 		, _data(data)
  21. 		, _col(RED)
  22. 	{}
  23. };
  24.  
  25. template<class T,class Ref,class Ptr>
  26. struct _RBTreeIterator
  27. {
  28. 	typedef RBTreeNode<T> Node;
  29. 	typedef _RBTreeIterator<T, Ref, Ptr> Self; //返回一个自身的迭代器
  30. 	typedef _RBTreeIterator<T, T&, T*> iterator; //用来转化成const迭代器
  31. 	Node* _node;
  32.  
  33. 	_RBTreeIterator(Node* node)  //利用节点去构造迭代器
  34. 		:_node(node)
  35. 	{}
  36.  
  37.  
  38. 	// 1、typedef __RBTreeIterator<T, T&, T*> itertaor;  拷贝构造
  39. 	// 2、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
  40. 	//  支持普通迭代器构造const迭代器的构造函数  为的是隐式类型转化
  41.  
  42. 	_RBTreeIterator(const iterator& it) //隐私类型转化  为了set去服务的 因为set的普通迭代器也是const迭代器
  43. 		:_node(it._node)
  44. 	{}
  45.  
  46.  
  47.  
  48.  
  49. 	Ref operator*()
  50. 	{
  51. 		return _node->_data; //解引用拿到对应的东西  map拿到pair set拿到key
  52. 	}
  53.  
  54. 	Ptr operator->() //返回对应的指针类型
  55. 	{
  56. 		return &operator*();
  57. 	}
  58.  
  59. 	bool operator!=(const Self& s)
  60. 	{
  61. 		return _node != s._node;//判断两个迭代器是否相同
  62. 	}
  63.  
  64. 	bool operator==(const Self& s)
  65. 	{
  66. 		return _node == s._node;//判断两个迭代器是否相同
  67. 	}
  68.  
  69. 	Self& operator++()  //实现迭代器的++
  70. 	{
  71. 		if (_node->_right)
  72. 		{
  73. 		   //如有右不为空，那么就去找到  右子树的最左路节点
  74. 			Node* subright = _node->_right;
  75. 			while (subright->_left)  subright = subright->_left; //找到最左路节点
  76. 			_node = subright;
  77. 		}
  78. 		else
  79. 		{
  80. 		   //右为空，沿着到根的路径，找孩子是父亲左的那个祖先
  81. 			Node* cur = _node;
  82. 			Node* parent = cur->_parent;
  83. 			while (parent && parent->_right == cur)
  84. 			{
  85. 				cur = parent;
  86. 				parent = parent->_parent;
  87. 			}
  88. 			_node = parent;
  89. 		}
  90. 		return *this;
  91. 	}
  92.  
  93. 	Self operator++(int)  //实现迭代器的后置++
  94. 	{
  95. 		Self temp = *this;
  96. 		++*this;
  97. 		return temp;
  98. 	}
  99.  
  100. 	Self& operator--()  //实现迭代器的--     右  根  左
  101. 	{
  102. 		if (_node->_left)
  103. 		{
  104. 			//如有左不为空，那么就去找到  左子树的最右路节点
  105. 			Node* subright = _node->_left;
  106. 			while (subright->_right)  subright = subright->_right; //找到最左路节点
  107. 			_node = subright;
  108. 		}
  109. 		else
  110. 		{
  111. 			//左为空，沿着到根的路径，找孩子是父亲右的那个祖先
  112. 			Node* cur = _node;
  113. 			Node* parent = cur->_parent;
  114. 			while (parent && parent->_left == cur)
  115. 			{
  116. 				cur = parent;
  117. 				parent = parent->_parent;
  118. 			}
  119. 			_node = parent;
  120. 		}
  121. 		return *this;
  122. 	}
  123.  
  124. 	Self operator--(int)  //实现迭代器的后置--
  125. 	{
  126. 		Self temp = *this;
  127. 		--*this;
  128. 		return temp;
  129. 	}
  130.  
  131. };
  132.  
  133.  
  134.  
  135. //K是为了单独拿到key的类型 因为find erase 的接口都是key   而第二个模版参数T决定是这边传的是pair还是key
  136. template<class K, class T,class KeyOfT>  //KeyofT 取出来比较的是k 还是pair中的k
  137. class RBTree
  138. {
  139. 	typedef RBTreeNode<T> Node;
  140. public:
  141. 	typedef _RBTreeIterator<T, T&, T*>  iterator;
  142. 	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
  143.  
  144. 	iterator begin()
  145. 	{
  146. 		Node* cur = _root;
  147. 		while (cur && cur->_left)  cur = cur->_left;
  148. 		//找到最左路的节点
  149. 		return iterator(cur);
  150. 	} 
  151.  
  152. 	iterator end()
  153. 	{
  154. 		return iterator(nullptr);
  155. 	}
  156.  
  157. 	const_iterator begin() const
  158. 	{
  159. 		Node* cur = _root;
  160. 		while (cur && cur->_left)  cur = cur->_left;
  161. 		//找到最左路的节点
  162. 		return const_iterator(cur);
  163. 	}
  164.  
  165. 	const_iterator end() const
  166. 	{
  167. 		return const_iterator(nullptr);
  168. 	}
  169.  
  170.  
  171. 	~RBTree()
  172. 	{
  173. 		_Destroy(_root);
  174. 		_root = nullptr;
  175. 	}
  176.  
  177. 	iterator Find(const K& key) const
  178. 	{
  179. 		Node* cur = _root;
  180. 		KeyOfT kot;//控制  是在pair中拿key还是直接拿key
  181. 		while (cur)
  182. 		{
  183. 			if (kot(cur->_data) < key) cur = cur->_right;  //我比你小，你往右找
  184. 			else if (kot(cur->_data) > key)  cur = cur->_left;  //我比你大，你往左找
  185. 			else return iterator(cur);
  186. 		}
  187. 		return iterator(nullptr);//说明找不到
  188. 	}
  189.  
  190. 	//先用搜索树的逻辑插入节点，然后再去更新平衡因子。
  191. 	pair<iterator,bool> Insert(const T& data)
  192. 	{
  193. 		//如果为空树，新节点就是根
  194. 		if (_root == nullptr)
  195. 		{
  196. 			_root = new Node(data);
  197. 			_root->_col = BLACK;
  198. 			return make_pair(iterator(_root),true);
  199. 		}
  200.  
  201. 		KeyOfT kot;//控制  是在pair中拿key还是直接拿key
  202. 		//如果不为空树
  203. 		Node* parent = nullptr;
  204. 		Node* cur = _root;
  205. 		while (cur)
  206. 		{
  207. 			if (kot(cur->_data) > kot(data)) //如果我比你大，到左子树去
  208. 			{
  209. 				parent = cur;
  210. 				cur = cur->_left;
  211. 			}
  212. 			else if (kot(cur->_data) < kot(data)) //比你小，你去右子树
  213. 			{
  214. 				parent = cur;
  215. 				cur = cur->_right;
  216. 			}
  217. 			else return make_pair(iterator(cur), false);//相等 
  218. 		}
  219. 		//此时肯定是对应地接在parent的后面
  220. 		cur = new Node(data);
  221. 		Node* newnode = cur;//记住新加入的节点
  222. 		if (kot(parent->_data)> kot(data))   parent->_left = cur;                //比父亲小连左边
  223. 		else  parent->_right = cur; //比父亲大连右边
  224. 		//别忘了父亲指针
  225. 		cur->_parent = parent;
  226.  
  227.  
  228. 		while (parent && parent->_col == RED)
  229. 		{
  230. 			Node* grandfather = parent->_parent;
  231. 			//情况1，如果u为存在且为红
  232. 			if (grandfather->_left == parent)//如果p是g的左边，u就在右边
  233. 			{
  234. 				Node* uncle = grandfather->_right;
  235. 				//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
  236. 				if (uncle && uncle->_col == RED)
  237. 				{
  238. 					parent->_col = BLACK;
  239. 					uncle->_col = BLACK;
  240. 					grandfather->_col = RED;
  241. 					//继续向上调整
  242. 					cur = grandfather;
  243. 					parent = cur->_parent;
  244. 				}
  245. 				else //情况2或者情况3， u为黑或者不存在   旋转+变色
  246. 				{
  247. 					if (cur == parent->_left) //情况2 右单旋+p变黑 g变红
  248. 					{
  249. 						//      g
  250. 						//   p    u
  251. 						// c
  252. 						RotateR(grandfather);
  253. 						parent->_col = BLACK;
  254. 						grandfather->_col = RED;
  255. 					}
  256. 					else  //情况3 右左双旋  c变黑 g变红
  257. 					{
  258. 						//          g
  259. 							//   p     u
  260. 							//     c
  261. 						RotateL(parent);
  262. 						RotateR(grandfather);
  263. 						cur->_col = BLACK;
  264. 						grandfather->_col = RED;
  265. 					}
  266. 					break;//情况2和情况3都要跳出循环
  267. 				}
  268.  
  269. 			}
  270. 			else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边    几乎一样，就是旋转的逻辑不同
  271. 			{
  272. 				Node* uncle = grandfather->_left;
  273. 				//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
  274. 				if (uncle && uncle->_col == RED)
  275. 				{
  276. 					parent->_col = BLACK;
  277. 					uncle->_col = BLACK;
  278. 					grandfather->_col = RED;
  279. 					//继续向上调整
  280. 					cur = grandfather;
  281. 					parent = cur->_parent;
  282. 				}
  283. 				else//情况2或者情况3， u为黑或者不存在   旋转+变色
  284. 				{
  285. 					if (cur == parent->_right) //情况2 左单旋+p变黑 g变红
  286. 					{
  287. 						//      g
  288. 						//   p    u
  289. 						//          c
  290. 						RotateL(grandfather);
  291. 						parent->_col = BLACK;
  292. 						grandfather->_col = RED;
  293. 					}
  294. 					else  //情况3 左右双旋  c变黑 g变红
  295. 					{
  296. 						//          g
  297. 							//   p     u
  298. 							//       c
  299. 						RotateR(parent);
  300. 						RotateL(grandfather);
  301. 						cur->_col = BLACK;
  302. 						grandfather->_col = RED;
  303. 					}
  304. 					break;//情况2和情况3都要跳出循环
  305. 				}
  306. 			}
  307. 		}
  308. 		_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错
  309. 		 return make_pair(iterator(newnode), true);
  310. 	}
  311.  
  312. 	void InOrder()
  313. 	{
  314. 		_InOrder(_root);
  315. 		cout << endl;
  316. 	}
  317.  
  318. 	bool IsBalance()
  319. 	{
  320. 		if (_root && _root->_col == RED)
  321. 		{
  322. 			cout << "根节点颜色是红色" << endl;
  323. 			return false;
  324. 		}
  325. 		int benchmark = 0;//找到一条路径作为基准值 然后看看其他路径是否相等
  326. 		Node* cur = _root;
  327. 		while (cur)
  328. 		{
  329. 			if (cur->_col == BLACK)
  330. 				++benchmark;
  331. 			cur = cur->_left;
  332. 		}
  333.  
  334. 		// 连续红色节点
  335. 		return _Check(_root, 0, benchmark);
  336. 	}
  337.  
  338. 	int Height()
  339. 	{
  340. 		return _Height(_root);
  341. 	}
  342.  
  343.  
  344. private:
  345.  
  346.  
  347. 	void _Destroy(Node* root)
  348. 	{
  349. 		if (root == nullptr) return;
  350. 		//后序遍历销毁
  351. 		_Destroy(root->_left);
  352. 		_Destroy(root->_right);
  353. 		delete root;
  354. 	}
  355.  
  356. 	int _Height(Node* root)
  357. 	{
  358. 		if (root == nullptr)
  359. 			return 0;
  360.  
  361. 		int leftH = _Height(root->_left);
  362. 		int rightH = _Height(root->_right);
  363.  
  364. 		return leftH > rightH ? leftH + 1 : rightH + 1;
  365. 	}
  366.  
  367. 	bool _Check(Node* root, int blackNum, int benchmark)
  368. 	{
  369. 		if (root == nullptr)
  370. 		{
  371. 			if (benchmark != blackNum)
  372. 			{
  373. 				cout << "某条路径黑色节点的数量不相等" << endl;
  374. 				return false;
  375. 			}
  376.  
  377. 			return true;
  378. 		}
  379.  
  380. 		if (root->_col == BLACK)
  381. 		{
  382. 			++blackNum;
  383. 		}
  384.  
  385. 		if (root->_col == RED
  386. 			&& root->_parent
  387. 			&& root->_parent->_col == RED)
  388. 		{
  389. 			cout << "存在连续的红色节点" << endl;
  390. 			return false;
  391. 		}
  392.  
  393. 		return _Check(root->_left, blackNum, benchmark)
  394. 			&& _Check(root->_right, blackNum, benchmark);
  395. 	}
  396.  
  397. 	void _InOrder(Node* root)
  398. 	{
  399. 		if (root == nullptr)
  400. 		{
  401. 			return;
  402. 		}
  403.  
  404. 		_InOrder(root->_left);
  405. 		cout << root->_kv.first << " ";
  406. 		_InOrder(root->_right);
  407. 	}
  408.  
  409.  
  410.  
  411. 	//旋转代码和AVL树是一样的，只不过不需要搞平衡因子
  412. 	void RotateL(Node* parent)
  413. 	{
  414. 		//旋转前，先记录对应的节点
  415. 		Node* subR = parent->_right;
  416. 		Node* subRL = subR->_left;
  417. 		Node* ppnode = parent->_parent;//子树的前驱节点
  418. 		//先让b变成30的边
  419. 		parent->_right = subRL;
  420. 		if (subRL) subRL->_parent = parent;
  421. 		//让30变成60的左边
  422. 		subR->_left = parent;
  423. 		parent->_parent = subR;
  424. 		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
  425. 		if (ppnode == nullptr)
  426. 		{
  427. 			_root = subR;
  428. 			_root->_parent = nullptr;
  429. 		}
  430. 		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
  431. 		else
  432. 		{
  433. 			if (ppnode->_left == parent) ppnode->_left = subR;
  434. 			else ppnode->_right = subR;
  435. 			//向上连接
  436. 			subR->_parent = ppnode;
  437. 		}
  438. 	}
  439.  
  440.  
  441. 	void RotateR(Node* parent)
  442. 	{
  443. 		//旋转前，先记录对应的节点
  444. 		Node* subL = parent->_left;
  445. 		Node* subLR = subL->_right;
  446. 		Node* ppnode = parent->_parent;//子树的前驱节点
  447. 		//先让b变成60的左边
  448. 		parent->_left = subLR;
  449. 		if (subLR) subLR->_parent = parent;
  450. 		//让60变成30的右边
  451. 		subL->_right = parent;
  452. 		parent->_parent = subL;
  453. 		//此时与前驱节点连接起来 如果前驱节点为空，直接改变根
  454. 		if (ppnode == nullptr)
  455. 		{
  456. 			_root = subL;
  457. 			_root->_parent = nullptr;
  458. 		}
  459. 		//如果前驱节点不为空，此时要根据之前paernt的情况决定插在哪边
  460. 		else
  461. 		{
  462. 			if (ppnode->_left == parent) ppnode->_left = subL;
  463. 			else ppnode->_right = subL;
  464. 			//向上连接
  465. 			subL->_parent = ppnode;
  466. 		}
  467. 	}
  468.  
  469. 	Node* _root = nullptr;
  470. };

二、set的模拟实现

前面我们已经将架子搭好了，这个时候就可以直接开始用了！！

  1. namespace cyx
  2. {
  3. 	template<class K>
  4. 	class set
  5. 	{
  6. 		struct SetKeyofT
  7. 		{ 
  8. 			const K& operator()(const K& key) //为了跟map保持一致
  9. 			{
  10. 				return key;
  11. 			}
  12. 		};
  13. 	public:
  14. 		typedef typename RBTree< K,K,SetKeyofT>::const_iterator  iterator;//在没有实例化的时候  编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
  15. 		typedef typename RBTree< K, K, SetKeyofT>::const_iterator  const_iterator;
  16. 		iterator begin()
  17. 		{
  18. 			return _t.begin();
  19. 		}
  20.  
  21. 		iterator end()
  22. 		{
  23. 			return _t.end();
  24. 		}
  25.  
  26. 		const_iterator begin() const
  27. 		{
  28. 			return _t.begin();
  29. 		}
  30.  
  31. 		const_iterator end() const
  32. 		{
  33. 			return _t.end();
  34. 		}
  35.  
  36. 		pair<iterator, bool> insert(const K&key)
  37. 		{
  38. 			return _t.Insert(key);
  39. 		}
  40.  
  41.  
  42. 	private:
  43. 		RBTree<K, K, SetKeyofT> _t;
  44. 	};
  45.  
  46.  
  47. 	void test_set1()
  48. 	{
  49. 		int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  50. 		set<int> s;
  51. 		for (auto e : a)
  52. 		{
  53. 			s.insert(e);
  54. 		}
  55.  
  56. 		set<int>::iterator it = s.begin();
  57. 		while (it != s.end())
  58. 		{
  59. 			cout << *it << " ";
  60. 			//*it = 1;
  61.  
  62. 			++it;
  63. 		}
  64. 		cout << endl;
  65.  
  66. 		for (auto e : s)
  67. 		{
  68. 			cout << e << " ";
  69. 		}
  70. 		cout << endl;
  71. 	}
  72. }

注意：

1、在没有实例化的时候 ，编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题

 2、对于insert返回值的改造，本质上是为了map去服务的，set只是配合而已。

三、map的模拟实现

3.1 insert的改装

在stl中 insert的返回值是pair<iterator,bool> 一开始我不太能理解为什么要这么设计。后来我明白了其实本质上为了后面重载[ ]的实现做铺垫。我们可以通过返回值去拿到iterator，并对对应节点的value进行直接修改！！

  1. //先用搜索树的逻辑插入节点，然后再去更新平衡因子。
  2. pair<iterator,bool> Insert(const T& data)
  3. {
  4. 	//如果为空树，新节点就是根
  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;//控制  是在pair中拿key还是直接拿key
  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->_left;
  22. 		}
  23. 		else if (kot(cur->_data) < kot(data)) //比你小，你去右子树
  24. 		{
  25. 			parent = cur;
  26. 			cur = cur->_right;
  27. 		}
  28. 		else return make_pair(iterator(cur), false);//相等 
  29. 	}
  30. 	//此时肯定是对应地接在parent的后面
  31. 	cur = new Node(data);
  32. 	Node* newnode = cur;//记住新加入的节点
  33. 	if (kot(parent->_data)> kot(data))   parent->_left = cur;                //比父亲小连左边
  34. 	else  parent->_right = cur; //比父亲大连右边
  35. 	//别忘了父亲指针
  36. 	cur->_parent = parent;
  37.  
  38.  
  39. 	while (parent && parent->_col == RED)
  40. 	{
  41. 		Node* grandfather = parent->_parent;
  42. 		//情况1，如果u为存在且为红
  43. 		if (grandfather->_left == parent)//如果p是g的左边，u就在右边
  44. 		{
  45. 			Node* uncle = grandfather->_right;
  46. 			//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
  47. 			if (uncle && uncle->_col == RED)
  48. 			{
  49. 				parent->_col = BLACK;
  50. 				uncle->_col = BLACK;
  51. 				grandfather->_col = RED;
  52. 				//继续向上调整
  53. 				cur = grandfather;
  54. 				parent = cur->_parent;
  55. 			}
  56. 			else //情况2或者情况3， u为黑或者不存在   旋转+变色
  57. 			{
  58. 				if (cur == parent->_left) //情况2 右单旋+p变黑 g变红
  59. 				{
  60. 					//      g
  61. 					//   p    u
  62. 					// c
  63. 					RotateR(grandfather);
  64. 					parent->_col = BLACK;
  65. 					grandfather->_col = RED;
  66. 				}
  67. 				else  //情况3 右左双旋  c变黑 g变红
  68. 				{
  69. 					//          g
  70. 						//   p     u
  71. 						//     c
  72. 					RotateL(parent);
  73. 					RotateR(grandfather);
  74. 					cur->_col = BLACK;
  75. 					grandfather->_col = RED;
  76. 				}
  77. 				break;//情况2和情况3都要跳出循环
  78. 			}
  79.  
  80. 		}
  81. 		else//if (grandfather->_right == parent)//如果p是g的右边，u就在左边    几乎一样，就是旋转的逻辑不同
  82. 		{
  83. 			Node* uncle = grandfather->_left;
  84. 			//情况1，如果u为存在且为红 p u变黑，g变红 向上调整
  85. 			if (uncle && uncle->_col == RED)
  86. 			{
  87. 				parent->_col = BLACK;
  88. 				uncle->_col = BLACK;
  89. 				grandfather->_col = RED;
  90. 				//继续向上调整
  91. 				cur = grandfather;
  92. 				parent = cur->_parent;
  93. 			}
  94. 			else//情况2或者情况3， u为黑或者不存在   旋转+变色
  95. 			{
  96. 				if (cur == parent->_right) //情况2 左单旋+p变黑 g变红
  97. 				{
  98. 					//      g
  99. 					//   p    u
  100. 					//          c
  101. 					RotateL(grandfather);
  102. 					parent->_col = BLACK;
  103. 					grandfather->_col = RED;
  104. 				}
  105. 				else  //情况3 左右双旋  c变黑 g变红
  106. 				{
  107. 					//          g
  108. 						//   p     u
  109. 						//       c
  110. 					RotateR(parent);
  111. 					RotateL(grandfather);
  112. 					cur->_col = BLACK;
  113. 					grandfather->_col = RED;
  114. 				}
  115. 				break;//情况2和情况3都要跳出循环
  116. 			}
  117. 		}
  118. 	}
  119. 	_root->_col = BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑，总没错
  120. 	 return make_pair(iterator(newnode), true);
  121. }

3.2 重载[ ]的实现

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

通过insert拿到对应位置的迭代器，然后指向其second 这样就可以直接进行修改了。 

3.3 模拟实现的代码

  1. namespace cyx
  2. {
  3. 	template<class K, class V>
  4. 	class map
  5. 	{
  6. 		struct MapKeyofT
  7. 		{
  8. 			const K& operator()(const pair<const K, V>& kv) //为了跟map保持一致
  9. 			{
  10. 				return kv.first;
  11. 			}
  12. 		};
  13. 	public:
  14. 		//模版类型的内嵌类型  加typename
  15. 		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator  iterator;//在没有实例化的时候  编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题
  16. 		typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator  const_iterator;
  17. 		iterator begin()
  18. 		{
  19. 			return _t.begin();
  20. 		}
  21.  
  22. 		iterator end()
  23. 		{
  24. 			return _t.end();
  25. 		}
  26.  
  27.  
  28. 		const_iterator begin() const
  29. 		{
  30. 			return _t.begin();
  31. 		}
  32.  
  33. 		const_iterator end() const
  34. 		{
  35. 			return _t.end();
  36. 		}
  37.  
  38. 		V& operator[](const K& key)
  39. 		{
  40. 			pair<iterator, bool> ret = _t.Insert(make_pair(key, V())); //默认构造
  41. 			return ret.first->second;
  42. 		}
  43.  
  44. 		pair<iterator, bool> insert(const pair<const K, V>& kv)
  45. 		{
  46. 			return _t.Insert(kv);
  47. 		}
  48.  
  49.  
  50. 	private:
  51. 		RBTree<K, pair<const K,V>, MapKeyofT> _t;
  52. 	};
  53.  
  54.  
  55. 	void test_map()
  56. 	{
  57. 		map<string, string> dict;
  58. 		dict.insert(make_pair("sort", "排序"));
  59. 		dict.insert(make_pair("left", "左边"));
  60. 		dict.insert(make_pair("right", "右边"));
  61. 		dict.insert(make_pair("hello", "你好"));
  62. 		map<string, string>::iterator it = dict.begin();
  63. 		cout << it->first<<endl;
  64. 		it++;
  65. 		cout << it->first << endl;
  66. 		it--;
  67. 		cout << it->first << endl;
  68. 		while (it != dict.end())
  69. 		{
  70. 			cout << it->first << ":" << it->second << endl;
  71. 			++it;
  72. 		}
  73.  
  74. 		//for(auto&kv:dict)  cout << kv.first << ":" << kv.second << endl;
  75. 	}
  76.  
  77. 	void test_map2()
  78. 	{
  79. 		string arr[] = { "西瓜", "梨子", "香蕉", "香蕉", "苹果", "西瓜", "梨子", "香蕉", "西瓜", "西瓜", "苹果", "火龙果", "橙子", "梨子"};
  80. 		map<string, int> countMap;
  81. 		for (auto& e : arr)
  82. 		{
  83. 			++countMap[e];
  84. 		}
  85.  
  86. 		for (auto& kv : countMap)
  87. 		{
  88. 			//kv.second = 2; 控制first不能被修改 或者是key不能被修改
  89. 			cout << kv.first << ":" << kv.second << endl;
  90. 		}
  91. 	}
  92.  
  93.  
  94. }

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

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

  

闽ICP备14008679号