• C++库函数——set与map的模拟实现

    目录

    1.红黑树的迭代器与改造

    ①红黑树的迭代器

    ②红黑树的改造

    2.map的模拟实现

    3.set的模拟实现

    4.测试

    1.红黑树的迭代器与改造

    ①红黑树的迭代器

    对于上面这棵红黑树，我们可以很容易得知道begin()是红黑树的最左节点，end()应该是一个空节点。即

    1. iterator begin()
    2. {
    3. 	Node* cur = _root;
    4. 	while (cur && cur->_left)
    5. 	{
    6. 		cur = cur->_left;
    7. 	}
    8.  
    9. 	return cur;
    10. }
    11.  
    12. iterator end()
    13. {
    14. 	return iterator(nullptr);
    15. }

     接下来定义iterator及其具体操作

    1. template<class T>
    2. struct RBTreeIterator
    3. {
    4. 	typedef RBTreeNode Node;
    5. 	typedef RBTreeIterator Self;
    6.  
    7. 	RBTreeIterator(Node* node)
    8. 		: _node(node)
    9. 	{}
    10.  
    11. 	// 让迭代器具有类似指针的行为
    12. 	T& operator*()
    13. 	{
    14. 		return _node->_data;
    15. 	}
    16.  
    17. 	T* operator->()
    18. 	{
    19. 		return &_node->_data;
    20. 	}
    21.  
    22. 	// 迭代器可以移动：前置/后置++  
    23. 	Self& operator++()
    24. 	{
    25. 		// 这里的++是为了找到下一个比当前节点大的位置
    26. 		// 结合图像具体来看就是两种情况
    27. 		// 第一种是如果当前节点有右子树，
    28. 		// 那么下一个节点就是右子树中的最左节点
    29. 		// 第二种是如果当前节点没有右子树，
    30. 		// 那么下一个节点就是“当前节点是父亲的左子树”的节点
    31. 		// 如果不是的话就继续向上更新，直到更新到根节点
    32. 		if (_node->_right)
    33. 		{
    34. 			_node = _node->_right;
    35. 			while (_node->_left)
    36. 			{
    37. 				_node = _node->_left;
    38. 			}
    39. 		}
    40. 		else
    41. 		{
    42. 			Node* cur = _node;
    43. 			Node* parent = cur->_parent;
    44.  
    45. 			while (parent && cur == parent->_right)
    46. 			{
    47. 				cur = parent;
    48. 				parent = parent->_parent;
    49. 			}
    50.  
    51. 			if (parent && cur == parent->_left)
    52. 				_node = parent;
    53. 			else
    54. 				_node = nullptr;
    55. 		}
    56.  
    57. 		return *this;
    58. 	}
    59. 	Self operator++(int)
    60. 	{
    61. 		Self tmp(*this);
    62. 		++(*this);
    63.  
    64. 		return tmp;
    65. 	}
    66.  
    67. 	// 迭代器可以移动：前置/后置-- 
    68. 	Self& operator--()
    69. 	{
    70. 		// 这里的大致逻辑与++类似
    71. 		if (_node->_left)
    72. 		{
    73. 			_node = _node->_left;
    74. 			while (_node->_right)
    75. 			{
    76. 				_node = _node->_right;
    77. 			}
    78. 		}
    79. 		else
    80. 		{
    81. 			Node* cur = _node;
    82. 			Node* parent = cur->_parent;
    83.  
    84. 			while (parent && cur == parent->_left)
    85. 			{
    86. 				cur = parent;
    87. 				parent = parent->_parent;
    88. 			}
    89.  
    90. 			if (parent && cur == parent->_right)
    91. 				_node = parent;
    92. 			else
    93. 				_node = nullptr;
    94. 		}
    95.  
    96. 		return *this;
    97.  
    98. 	}
    99. 	Self operator--(int)
    100. 	{
    101. 		Self tmp(*this);
    102. 		--(*this);
    103.  
    104. 		return tmp;
    105. 	}
    106.  
    107. 	// 让迭代器可以比较
    108. 	bool operator!=(const Self& s)const
    109. 	{
    110. 		return _node != s._node;
    111. 	}
    112.  
    113. 	bool operator==(const Self& s)const
    114. 	{
    115. 		return _node == s._node;
    116. 	}
    117.  
    118. 	Node* _node;
    119. };

    ②红黑树的改造

    1. // set->RBTree _t;
    2. // map->RBTree, MapKeyOfT> _t;
    3. template<class K, class T, class KeyofT>
    4. class RBTree
    5. {
    6. public:
    7. 	typedef RBTreeNode Node;
    8. 	typedef RBTreeIterator iterator;
    9. 	typedef RBTreeIteratorconst T*, const T&> const_iterator;
    10.  
    11. 	iterator begin()
    12. 	{
    13. 		Node* cur = _root;
    14. 		while (cur && cur->_left)
    15. 		{
    16. 			cur = cur->_left;
    17. 		}
    18.  
    19. 		return (iterator)cur;
    20. 	}
    21.  
    22. 	iterator end()
    23. 	{
    24. 		return iterator(nullptr);
    25. 	}
    26.  
    27. 	const_iterator begin() const
    28. 	{
    29. 		Node* cur = _root;
    30. 		while (cur && cur->_left)
    31. 		{
    32. 			cur = cur->_left;
    33. 		}
    34.  
    35. 		return (const_iterator)cur;
    36. 	}
    37.  
    38. 	const_iterator end() const
    39. 	{
    40. 		return const_iterator(nullptr);
    41. 	}
    42.  
    43. 	Node* Find(const T& data)
    44. 	{
    45. 		KeyofT kot;
    46. 		Node* cur = _root;
    47. 		while (cur)
    48. 		{
    49. 			if (kot(data) < kot(cur->_data))
    50. 			{
    51. 				cur = cur->_left;
    52. 			}
    53. 			else if (data > kot(cur->_data))
    54. 			{
    55. 				cur = cur->_right;
    56. 			}
    57. 			else
    58. 			{
    59. 				return cur;
    60. 			}
    61. 		}
    62.  
    63. 		return nullptr;
    64. 	}
    65.  
    66. 	pairbool> Insert(const T& data)
    67. 	{
    68. 		KeyofT kot;
    69. 		if (_root == nullptr)
    70. 		{
    71. 			_root = new Node(data);
    72. 			_root->_color = BLACK;
    73. 			return make_pair((iterator)_root, true);
    74. 		}
    75.  
    76. 		Node* cur = _root;
    77. 		Node* parent = nullptr;
    78. 		// 寻找要插入的位置
    79. 		while (cur)
    80. 		{
    81. 			if (kot(data) < kot(cur->_data))
    82. 			{
    83. 				parent = cur;
    84. 				cur = cur->_left;
    85. 			}
    86. 			else if (kot(data) > kot(cur->_data))
    87. 			{
    88. 				parent = cur;
    89. 				cur = cur->_right;
    90. 			}
    91. 			else
    92. 			{
    93. 				return make_pair((iterator)cur, false);
    94. 			}
    95. 		}
    96.  
    97. 		// 到此处cur已经指向了应该插入的位置，
    98. 		// 然后判断应该插入到parent的哪边
    99. 		cur = new Node(data);
    100. 		if (kot(data) > kot(parent->_data))
    101. 		{
    102. 			parent->_right = cur;
    103. 		}
    104. 		else
    105. 		{
    106. 			parent->_left = cur;
    107. 		}
    108. 		cur->_parent = parent;
    109.  
    110. 		// 插入完成后判断一下
    111. 		// 若父节点是黑就无需调整
    112. 		// 而当父节点是红就需要进行调整
    113. 		while (parent && parent->_color == RED)
    114. 		{
    115. 			Node* grandpa = parent->_parent;
    116. 			if (parent == grandpa->_left)
    117. 			{
    118. 				Node* uncle = grandpa->_right;
    119. 				if (uncle && uncle->_color == RED)
    120. 				{
    121. 					uncle->_color = parent->_color = BLACK;
    122. 					grandpa->_color = RED;
    123.  
    124. 					cur = grandpa;
    125. 					parent = cur->_parent;
    126. 				}
    127. 				else
    128. 				{
    129. 					if (uncle == nullptr)
    130. 					{
    131. 						if (parent->_left == cur)
    132. 						{
    133. 							//              grandpa
    134. 							//      parent
    135. 							//cur
    136. 							RotateR(grandpa);
    137. 							grandpa->_color = RED;
    138. 							parent->_color = BLACK;
    139. 						}
    140. 						else
    141. 						{
    142. 							//              grandpa
    143. 							//      parent
    144. 							//              cur
    145. 							RotateL(parent);
    146. 							RotateR(grandpa);
    147. 							cur->_color = BLACK;
    148. 							grandpa->_color = RED;
    149. 						}
    150. 					}
    151. 					else // uncle存在且为黑
    152. 					{
    153. 						if (parent->_left == cur)
    154. 						{
    155. 							//              grandpa
    156. 							//      parent
    157. 							//cur
    158. 							RotateR(grandpa);
    159. 							grandpa->_color = RED;
    160. 							parent->_color = BLACK;
    161. 						}
    162. 						else
    163. 						{
    164. 							//              grandpa
    165. 							//      parent
    166. 							//              cur
    167. 							RotateL(parent);
    168. 							RotateR(grandpa);
    169. 							cur->_color = BLACK;
    170. 							grandpa->_color = RED;
    171. 						}
    172. 					}
    173.  
    174. 					break;
    175. 				}
    176. 			}
    177. 			else // parent == grandpa->_right
    178. 			{
    179. 				Node* uncle = grandpa->_left;
    180. 				if (uncle && uncle->_color == RED)
    181. 				{
    182. 					uncle->_color = parent->_color = BLACK;
    183. 					grandpa->_color = RED;
    184.  
    185. 					cur = grandpa;
    186. 					parent = cur->_parent;
    187. 				}
    188. 				else
    189. 				{
    190. 					if (uncle == nullptr)
    191. 					{
    192. 						if (parent->_left == cur)
    193. 						{
    194. 							//grandpa
    195. 							//         parent
    196. 							//cur
    197. 							RotateR(parent);
    198. 							RotateL(grandpa);
    199. 							cur->_color = BLACK;
    200. 							grandpa->_color = RED;
    201. 						}
    202. 						else
    203. 						{
    204. 							//grandpa
    205. 							//        parent
    206. 							//               cur
    207. 							RotateL(grandpa);
    208. 							grandpa->_color = RED;
    209. 							parent->_color = BLACK;
    210. 						}
    211. 					}
    212. 					else // uncle存在且为黑
    213. 					{
    214. 						if (parent->_left == cur)
    215. 						{
    216. 							//grandpa
    217. 							//         parent
    218. 							//cur
    219. 							RotateR(parent);
    220. 							RotateL(grandpa);
    221. 							cur->_color = BLACK;
    222. 							grandpa->_color = RED;
    223. 						}
    224. 						else
    225. 						{
    226. 							//grandpa
    227. 							//        parent
    228. 							//               cur
    229. 							RotateL(grandpa);
    230. 							grandpa->_color = RED;
    231. 							parent->_color = BLACK;
    232. 						}
    233. 					}
    234.  
    235. 					break;
    236. 				}
    237. 			}
    238. 		}
    239.  
    240. 		if (cur->_parent == nullptr)
    241. 		{
    242. 			cur->_color = BLACK;
    243. 		}
    244. 		return make_pair((iterator)cur, true);
    245. 	}
    246.  
    247.  
    248. 	void RotateL(Node* parent)
    249. 	{
    250. 		Node* cur = parent->_right;    // 记录当前节点
    251. 		Node* curleft = cur->_left; // 记录当前节点的左节点
    252.  
    253. 		// 如果当前节点的左节点为空说明是h为0的情况
    254. 		// 不为空时就要进行节点间的连接
    255. 		if (curleft)
    256. 		{
    257. 			curleft->_parent = parent;
    258. 		}
    259.  
    260. 		parent->_right = curleft;
    261. 		cur->_left = parent;
    262.  
    263. 		// 此时需要确定parent是否属于子树
    264. 		if (parent == _root)
    265. 		{
    266. 			_root = cur;
    267. 			cur->_parent = nullptr;
    268. 		}
    269. 		else // 此时parent以下的节点属于子树
    270. 		{
    271. 			cur->_parent = parent->_parent;
    272.  
    273. 			// 确认parent与其父节点间的关系
    274. 			// 然后将cur与parent的父节点连接起来
    275. 			if (parent->_parent->_left == parent)
    276. 			{
    277. 				parent->_parent->_left = cur;
    278. 			}
    279. 			else
    280. 			{
    281. 				parent->_parent->_right = cur;
    282. 			}
    283. 		}
    284. 		parent->_parent = cur;
    285. 	}
    286.  
    287. 	void RotateR(Node* parent)
    288. 	{
    289. 		Node* cur = parent->_left;    // 记录当前节点
    290. 		Node* curright = cur->_right; // 记录当前节点的右节点
    291.  
    292. 		// 如果当前节点的右节点为空说明是h为0的情况
    293. 		// 不为空时就要进行节点间的连接
    294. 		if (curright)
    295. 		{
    296. 			curright->_parent = parent;
    297. 		}
    298.  
    299. 		parent->_left = curright;
    300. 		cur->_right = parent;
    301.  
    302. 		// 此时需要确定parent是否属于子树
    303. 		if (parent == _root)
    304. 		{
    305. 			_root = cur;
    306. 			cur->_parent = nullptr;
    307. 		}
    308. 		else // 此时parent以下的节点属于子树
    309. 		{
    310. 			cur->_parent = parent->_parent;
    311.  
    312. 			// 确认parent与其父节点间的关系
    313. 			// 然后将cur与parent的父节点连接起来
    314. 			if (parent->_parent->_left == parent)
    315. 			{
    316. 				parent->_parent->_left = cur;
    317. 			}
    318. 			else
    319. 			{
    320. 				parent->_parent->_right = cur;
    321. 			}
    322. 		}
    323. 		parent->_parent = cur;
    324. 	}
    325.  
    326. private:
    327. 	Node* _root = nullptr;
    328. };

    2.map的模拟实现

    1. namespace my_map
    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 RBTreeconst K, V>, MapKeyOfT>::iterator iterator;
    15. 		typedef typename RBTreeconst K, V>, 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. 		const_iterator begin() const
    28. 		{
    29. 			return _t.begin();
    30. 		}
    31.  
    32. 		const_iterator end() const
    33. 		{
    34. 			return _t.end();
    35. 		}
    36.  
    37. 		V& operator[](const K& key)
    38. 		{
    39. 			pairbool> ret = _t.Insert(make_pair(key, V()));
    40. 			return ret.first->second;
    41. 		}
    42.  
    43. 		pairbool> insert(const pair& kv)
    44. 		{
    45. 			return _t.Insert(kv);
    46. 		}
    47.  
    48. 	private:
    49. 		RBTreeconst K, V>, MapKeyOfT> _t;
    50. 	};
    51. }

    3.set的模拟实现

    1. namespace my_set
    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. 		const_iterator begin() const
    18. 		{
    19. 			return _t.begin();
    20. 		}
    21.  
    22. 		const_iterator end() const
    23. 		{
    24. 			return _t.end();
    25. 		}
    26.  
    27. 		// 使用iterator RBTree::const_iterator时，有
    28. 		// 无法从“std::pair,bool>”
    29. 		// 转换为“std::pair,bool>”
    30. 		// pair insert(const K& key)
    31. 		// {
    32. 		//		return _t.Insert(key);
    33. 		// }
    34.  
    35. 		pairbool> insert(const K& key)
    36. 		{
    37. 			// 将插入后的结果用一个key类型的pair接收
    38. 			pair<typename RBTree::iterator, bool> ret = _t.Insert(key);
    39. 			// 用ret的的元素构造key的特定pair
    40. 			// 目的:这里的iterator实际是const_iterator, 
    41. 			// 转换之后可以使key的第一个元素不被修改
    42. 			return pairbool>(ret.first, ret.second);
    43. 		}
    44. 	private:
    45. 		RBTree _t;
    46. 	};
    47. }

    4.测试

    1. #include "my_map.h"
    2. #include 
    3. #include 
    4. #include "my_set.h"
    5.  
    6. //int main()
    7. //{
    8. //	RBTree> t;
    9. //	for (int i = 0; i < 100; i++)
    10. //	{
    11. //		t.Insert(i);
    12. //	}
    13. //
    14. //	RBTree>::iterator it = t.begin();
    15. //	while (it != t.end())
    16. //	{
    17. //		cout << *it << " ";
    18. //		it++;
    19. //	}
    20. //
    21. //	return 0;
    22. //}
    23.  
    24. //int main()
    25. //{
    26. //	my_set::set st;
    27. //	for (int i = 0; i < 10; i++)
    28. //	{
    29. //		st.insert(i);
    30. //	}
    31. //
    32. //	auto it = st.begin();
    33. //	while (it != st.end())
    34. //	{
    35. //		cout << *it << " ";
    36. //		++it;
    37. //	}
    38. //
    39. //	return 0;
    40. //}
    41.  
    42. //int main()
    43. //{
    44. //	my_set::set st;
    45. //	for (int i = 0; i < 10; i++)
    46. //	{
    47. //		st.insert(i);
    48. //	}
    49. //
    50. //	my_set::set::iterator it = st.begin();
    51. //	while (it != st.end())
    52. //	{
    53. //		//if (*it % 2 == 0)
    54. //		//{
    55. //		//	*it += 10;
    56. //		//}
    57. //		cout << *it << " ";
    58. //		++it;
    59. //	}
    60. //
    61. //	return 0;
    62. //}
    63.  
    64. //int main()
    65. //{
    66. //	my_map::map st;
    67. //	string s1 = "a";
    68. //	string s2 = "b";
    69. //	for (int i = 0; i < 10; i++)
    70. //	{
    71. //		st.insert(make_pair(s1, s2));
    72. //		s1[0]++;
    73. //		s2[0]++;
    74. //	}
    75. //
    76. //	my_map::map::iterator it = st.begin();
    77. //	while (it != st.end())
    78. //	{
    79. //		//if (*it % 2 == 0)
    80. //		//{
    81. //		//	*it += 10;
    82. //		//}
    83. //		cout << (*it).first << ":"<< (*it).second << " "<
    84. //		++it;
    85. //	}
    86. //
    87. //	return 0;
    88. //}
    89.  
    90. int main()
    91. {
    92. 	my_map::map dict;
    93. 	dict.insert(make_pair("sort", "xxx"));
    94. 	dict["left"]; // 插入
    95.  
    96. 	for (const auto& kv : dict)
    97. 	{
    98. 		cout << kv.first << ":" << kv.second << endl;
    99. 	}
    100. 	cout << endl;
    101.  
    102. 	dict["left"] = "左边"; // 修改
    103. 	dict["sort"] = "排序"; // 修改
    104. 	dict["right"] = "右边"; // 插入+修改
    105.  
    106. 	for (const auto& kv : dict)
    107. 	{
    108. 		cout << kv.first << ":" << kv.second << endl;
    109. 	}
    110. 	cout << endl;
    111.  
    112. 	return 0;
    113. }
  • 相关阅读:
    【信息论与编码基础】第3章 离散信道
    无需编程经验，也能制作租车预约微信小程序，快速上手
    vue3环境搭建
    跨域的五种解决方案
    码蹄集 - MT2322 - 还是跑图：还是简单图问题
    写组件的过程中没写过的vue3写法
    神经网络和深度学习-处理多维特征的输入
    ImageProvider工作流程和AssetImage 加载流程
    经济数据预测 | Python实现ARIMA时间序列金融市场预测
    杏仁损伤检测器——基于CNN的图像分类
  • 原文地址：https://blog.csdn.net/qq_73201597/article/details/133151950