• C++ 基于红黑树的map和set

    目录

    一、红黑树

    1 红黑树的概念

    2 红黑树的性质 

    3 红黑树节点的定义 

    4 红黑树的插入操作

    5 红黑树的验证

    6 红黑树的删除

    7 红黑树与AVL树的比较

    二 红黑树模拟实现STL中的map与set

    1 红黑树的迭代器

    一、红黑树

    1 红黑树的概念

    红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

    2 红黑树的性质 

    1、每个结点不是红色就是黑色
    2、根节点是黑色的
    3、如果一个节点是红色的，则它的两个孩子结点是黑色的
    4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
    5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

    红黑树能够保证：其最长路径中节点个数不会超过最短路径节点个数的两倍。

    最短路径为全黑，最长路径就是红黑节点交替（因为红色节点不能连续），每条路径的黑色节点相同，则最长路径、刚好是最短路径的两倍。

    3 红黑树节点的定义 

    1. // 节点的颜色
    2. enum Color { RED, BLACK };
    3. // 红黑树节点的定义
    4. template<class ValueType>
    5. struct RBTreeNode
    6. {
    7. 	RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
    8. 		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
    9. 		, _data(data), _color(color)
    10. 	{}
    11. 	RBTreeNode* _pLeft; // 节点的左孩子
    12. 	RBTreeNode* _pRight; // 节点的右孩子
    13. 	RBTreeNode* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
    14. 	ValueType _data; // 节点的值域
    15. 	Color _color; // 节点的颜色
    16. };

    4 红黑树的插入操作

    红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

    1、按照二叉搜索树的规则插入新节点

    1. template<class ValueType>
    2. class RBTree
    3. {
    4. 	//……
    5. 	bool Insert(const ValueType& data)
    6. 	{
    7. 		PNode& pRoot = GetRoot();
    8. 		if (nullptr == pRoot)
    9. 		{
    10. 			pRoot = new Node(data, BLACK);
    11. 			// 根的双亲为头节点
    12. 			pRoot->_pParent = _pHead;
    13. 			_pHead->_pParent = pRoot;
    14. 		}
    15. 		else
    16. 		{
    17. 			// 1. 按照二叉搜索的树方式插入新节点
    18. 			// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
    19. 			// 若满足直接退出，否则对红黑树进行旋转着色处理
    20. 		}
    21. 		// 根节点的颜色可能被修改，将其改回黑色
    22. 		pRoot->_color = BLACK;
    23. 		_pHead->_pLeft = LeftMost();
    24. 		_pHead->_pRight = RightMost();
    25. 		return true;
    26. 	}
    27. private:
    28. 	PNode& GetRoot() { return _pHead->_pParent; }
    29. 	// 获取红黑树中最小节点，即最左侧节点
    30. 	PNode LeftMost();
    31. 	// 获取红黑树中最大节点，即最右侧节点
    32. 	PNode RightMost();
    33. private:
    34. 	PNode _pHead;
    35. };

    2、检测新节点插入后，红黑树的性质是否遭到破坏

    因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

    约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

    情况一: cur为红，p为红，g为黑，u存在且为红

    情况二: cur为红，p为红，g为黑，u不存在/u为黑

    p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，

    p为g的右孩子，cur为p的右孩子，则进行左单旋转

    p、g变色--p变黑，g变红

    情况三: cur为红，p为红，g为黑，u不存在/u为黑

    p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，

    p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

    则转换成了情况2

    对每种情况进行相应的处理即可。

    1. bool Insert(const ValueType& data)
    2. {
    3. 	// ...
    4. 	// 新节点插入后，如果其双亲节点的颜色为空色，则违反性质3：不能有连在一起的红色结点
    5. 	while (pParent && RED == pParent->_color)
    6. 	{
    7. 		// 注意：grandFather一定存在
    8. 		// 因为pParent存在，且不是黑色节点，则pParent一定不是根，则其一定有双亲
    9. 		PNode grandFather = pParent->_pParent;
    10. 		// 先讨论左侧情况
    11. 		if (pParent == grandFather->_pLeft)
    12. 		{
    13. 			PNode unclue = grandFather->_pRight;
    14. 			// 情况三：叔叔节点存在，且为红
    15. 			if (unclue && RED == unclue->_color)
    16. 			{
    17. 				pParent->_color = BLACK;
    18. 				unclue->_color = BLACK;
    19. 				grandFather->_color = RED;
    20. 				pCur = grandFather;
    21. 				pParent = pCur->_pParent;
    22. 			}
    23. 			else
    24. 			{
    25. 				// 情况五：叔叔节点不存在，或者叔叔节点存在且为黑
    26. 				if (pCur == pParent->_pRight)
    27. 				{
    28. 					_RotateLeft(pParent);
    29. 					swap(pParent, pCur);
    30. 				}
    31. 				// 情况五最后转化成情况四
    32. 				grandFather->_color = RED;
    33. 				pParent->_color = BLACK;
    34. 				_RotateRight(grandFather);
    35. 			}
    36. 		}
    37. 		else
    38. 		{
    39.  
    40. 		}
    41. 	}
    42. 	// ...
    43. }

    5 红黑树的验证

    红黑树的检测分为两步：

    1、检测其是否满足二叉搜索树(中序遍历是否为有序序列)

    2、检测其是否满足红黑树的性质
     

    1. bool IsValidRBTree()
    2. {
    3. 	PNode pRoot = GetRoot();
    4. 	// 空树也是红黑树
    5. 	if (nullptr == pRoot)
    6. 		return true;
    7. 	// 检测根节点是否满足情况
    8. 	if (BLACK != pRoot->_color)
    9. 	{
    10. 		cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    11. 		return false;
    12. 	}
    13. 	// 获取任意一条路径中黑色节点的个数
    14. 	size_t blackCount = 0;
    15. 	PNode pCur = pRoot;
    16. 	while (pCur)
    17. 	{
    18. 		if (BLACK == pCur->_color)
    19. 			blackCount++;
    20. 		pCur = pCur->_pLeft;
    21. 	}
    22. 	// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    23. 	size_t k = 0;
    24. 	return _IsValidRBTree(pRoot, k, blackCount);
    25. }
    26. bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
    27. {
    28. 	//走到null之后，判断k和black是否相等
    29. 	if (nullptr == pRoot)
    30. 	{
    31. 		if (k != blackCount)
    32. 		{
    33. 			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    34. 			return false;
    35. 		}
    36. 		return true;
    37. 	}
    38. 	// 统计黑色节点的个数
    39. 	if (BLACK == pRoot->_color)
    40. 		k++;
    41. 	// 检测当前节点与其双亲是否都为红色
    42. 	PNode pParent = pRoot->_pParent;
    43. 	if (pParent && RED == pParent->_color && RED == pRoot->_color)
    44. 	{
    45. 		cout << "违反性质三：没有连在一起的红色节点" << endl;
    46. 		return false;
    47. 	}
    48. 	return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&
    49. 		_IsValidRBTree(pRoot->_pRight, k, blackCount);
    50. }

    6 红黑树的删除

    此部分不做讲解，相比较插入，删除部分复杂一些。

    7 红黑树与AVL树的比较

    红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

    二 红黑树模拟实现STL中的map与set

    1 红黑树的迭代器

    迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。

    在迭代器部分比较难写的是重载++和--；

    下面附上源码

    RBTree.h

    1. #pragma once
    2. enum Color
    3. {
    4. 	RED = 0,
    5. 	BLACK
    6. };
    7. template <class T>
    8. struct RBTreeNode
    9. {
    10. 	typedef RBTreeNode Node;
    11. 	RBTreeNode* _left;
    12. 	RBTreeNode* _right;
    13. 	RBTreeNode* _parent;
    14. 	Color _col;
    15. 	T _data;
    16. 	RBTreeNode(const T data = T())
    17. 		:_left(nullptr),
    18. 		_right(nullptr),
    19. 		_parent(nullptr),
    20. 		_col(RED),
    21. 		_data(data)
    22. 	{}
    23. };
    24. template <class T,class Ref,class Ptr>
    25. struct RBTreeIterator
    26. {
    27. public:
    28. 	typedef RBTreeNode Node;
    29. 	typedef RBTreeIterator Self;
    30. 	RBTreeIterator(Node* ptr)
    31. 		:_Node(ptr)
    32. 	{}
    33. 	T& operator*()
    34. 	{
    35. 		return _Node->_data;
    36. 	}
    37. 	T* operator->()
    38. 	{
    39. 		return &(_Node->_data);
    40. 	}
    41. 	bool operator!=(Self it)
    42. 	{
    43. 		return _Node != it._Node;
    44. 	}
    45. 	bool operator==(Self it)
    46. 	{
    47. 		return _Node == it._Node;
    48. 	}
    49. 	Self& operator++()
    50. 	{
    51. 		Increament();
    52. 		return *this;
    53. 	}
    54. 	Self& operator--()
    55. 	{
    56. 		DeIncreament();
    57. 		return *this;
    58. 	}
    59.  
    60. private:
    61. 	void Increament()
    62. 	{
    63. 		if (_Node->_right)
    64. 		{
    65. 			_Node = _Node->_right;
    66. 			//节点的右边存在，则在右边子树中找到最左边的那个节点
    67. 			while (_Node->_left)
    68. 			{
    69. 				_Node = _Node->_left;
    70. 			}
    71. 		}
    72. 		else
    73. 		{
    74. 			//节点的右边不存在，则向上找父亲
    75. 			Node* parent = _Node->_parent;
    76. 			while (parent && _Node == parent->_right)
    77. 			{
    78. 				_Node = parent;
    79. 				parent = _Node->_parent;
    80. 			}
    81. 			_Node = parent;
    82. 		}
    83. 	}
    84. 	void DeIncreament()
    85. 	{
    86. 		if (_Node->_left)
    87. 		{
    88. 			_Node = _Node->_left;
    89. 			while (_Node->_right)
    90. 			{
    91. 				_Node = _Node->_right;
    92. 			}
    93. 		}
    94. 		else
    95. 		{
    96. 			Node* parent = _Node->_parent;
    97. 			while (parent&& _Node == parent->_left)
    98. 			{
    99. 				_Node = parent;
    100. 				parent = _Node->_parent;
    101. 			}
    102. 			_Node = parent;
    103. 		}
    104. 	}
    105. 	Node* _Node;
    106. };
    107. template <class K,class T, class KeyOfValue>
    108. class RBTree
    109. {
    110. public:
    111. 	typedef RBTreeNode Node;
    112. 	typedef RBTreeIterator Iterator;
    113. 	typedef RBTreeIterator<const T, const T&, const T*> const_Iterator;
    114. 	RBTree()
    115. 		:_root(nullptr)
    116. 	{}
    117. 	RBTree(const RBTree& RBT)
    118. 	{
    119. 		_root = Copy(RBT._root);
    120. 	}
    121. 	Iterator begin()
    122. 	{
    123. 		Node* left = _root;
    124. 		while (left->_left)
    125. 		{
    126. 			left = left->_left;
    127. 		}
    128. 		return Iterator(left);
    129. 	}
    130. 	Iterator end()
    131. 	{
    132. 		return 	Iterator(nullptr);
    133. 	}
    134. 	pairbool> Insert(const T data)
    135. 	{
    136. 		if (_root == nullptr)
    137. 		{
    138. 			_root = new Node(data);
    139. 			_root->_col = BLACK;
    140. 			return make_pair(Iterator(_root), true);
    141. 		}
    142. 		//插入
    143. 		//首先找到要插入的位置
    144. 		Node* cur = _root;
    145. 		Node* parent = _root;
    146. 		while (cur)
    147. 		{
    148. 			if (kov(cur->_data) > kov(data))
    149. 			{
    150. 				parent = cur;
    151. 				cur = cur->_left;
    152. 			}
    153. 			else if (kov(cur->_data) < kov(data))
    154. 			{
    155. 				parent = cur;
    156. 				cur = cur->_right;
    157. 			}
    158. 			else//找到了相同的Key值
    159. 			{
    160. 				return make_pair(Iterator(cur), false);
    161. 			}
    162. 		}
    163. 		//连接parent和cur
    164. 		cur = new Node(data);
    165. 		Node* newnode = cur;
    166. 		cur->_col = RED;
    167. 		cur->_parent = parent;
    168. 		if (kov(data) > kov(parent->_data))
    169. 		{
    170. 			parent->_right = cur;
    171.  
    172. 		}
    173. 		else if (kov(data) < kov(parent->_data))
    174. 		{
    175. 			parent->_left = cur;
    176. 		}
    177. 		//连接好了，开始修正
    178. 		//不能出现连续的红节点
    179. 		//一个红节点
    180. 		while (parent && parent->_col == RED)
    181. 		{
    182. 			Node* grandfather = parent->_parent;
    183. 			if (parent == grandfather->_left)
    184. 			{
    185. 				Node* uncle = grandfather->_right;
    186. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    187. 				{
    188. 					parent->_col = BLACK;
    189. 					uncle->_col = BLACK;
    190. 					grandfather->_col = RED;
    191. 					cur = grandfather;
    192. 					parent = cur->_parent;
    193. 				}
    194. 				else//叔叔不存在或为黑
    195. 				{
    196. 					if (cur == parent->_left)
    197. 					{
    198. 						//右单旋
    199. 						RotateR(grandfather);
    200. 						parent->_col = BLACK;
    201. 						grandfather->_col = RED;
    202. 					}
    203. 					else
    204. 					{
    205. 						//左右单旋
    206. 						RotateL(parent);
    207. 						RotateR(grandfather);
    208. 						cur->_col = BLACK;
    209. 						grandfather->_col = RED;
    210. 					}
    211. 					break;
    212. 				}
    213. 			}
    214. 			else
    215. 			{
    216. 				Node* uncle = grandfather->_left;
    217. 				if (uncle && uncle->_col == RED)//叔叔存在且为红
    218. 				{
    219. 					parent->_col = BLACK;
    220. 					uncle->_col = BLACK;
    221. 					grandfather->_col = RED;
    222. 					cur = grandfather;
    223. 					parent = cur->_parent;
    224. 				}
    225. 				else//叔叔不存在或为黑
    226. 				{
    227. 					if (cur == parent->_right)
    228. 					{
    229. 						//左单旋
    230. 						RotateL(grandfather);
    231. 						parent->_col = BLACK;
    232. 						grandfather->_col = RED;
    233. 					}
    234. 					else
    235. 					{
    236. 						//右左单旋
    237. 						RotateR(parent);
    238. 						RotateL(grandfather);
    239. 						cur->_col = BLACK;
    240. 						grandfather->_col = RED;
    241. 					}
    242. 					break;
    243. 				}
    244. 			}
    245. 		}
    246. 		_root->_col = BLACK;
    247. 		return make_pair(Iterator(newnode), true);
    248. 	}
    249. 	Iterator Find(const K& key)
    250. 	{
    251. 		Node* cur = _root;
    252. 		while (cur)
    253. 		{
    254. 			if (kov(cur->_data) > key)
    255. 			{
    256. 				cur = cur->_left;
    257. 			}
    258. 			else if (kov(cur->_data) < key)
    259. 			{
    260. 				cur = cur->_right;
    261. 			}
    262. 			else
    263. 			{
    264. 				return Iterator(cur);
    265. 			}
    266. 		}
    267. 		return nullptr;
    268. 	}
    269. 	Node* LeftMost()
    270. 	{
    271. 		Node* left = _root;
    272. 		while (left->_left)
    273. 		{
    274. 			left = left->_left;
    275. 		}
    276. 		return left;
    277. 	}
    278. 	Node* RightMost()
    279. 	{
    280. 		Node* right = _root;
    281. 		while (right->_right)
    282. 		{
    283. 			right = right->_right;
    284. 		}
    285. 		return right;
    286. 	}
    287. 	//void Inorder()
    288. 	//{
    289. 	//	_Inorder(_root);
    290. 	//}
    291. 	bool IsBanlance()
    292. 	{
    293. 		if (_root && _root->_col == RED)
    294. 		{
    295. 			cout << "根节点不是黑色" << endl;
    296. 			return false;
    297. 		}
    298. 		int benchmark = 0;
    299. 		Node* left = _root;
    300. 		while (left)
    301. 		{
    302. 			if (left->_col == BLACK)
    303. 			{
    304. 				benchmark++;
    305. 			}
    306. 			left = left->_left;
    307. 		}
    308. 		int blacknum = 0;
    309. 		return _IsBanlance(_root, benchmark, blacknum);
    310. 	}
    311. 	int Height()
    312. 	{
    313. 		return _Height(_root);
    314. 	}
    315. 	Node*& GetRoot()
    316. 	{
    317. 		return _root;
    318. 	}
    319. private:
    320. 	Node* Copy(Node* root)
    321. 	{
    322. 		if (root == nullptr)
    323. 		{
    324. 			return nullptr;
    325. 		}
    326. 		Node* newnode = new Node(root->_data);
    327. 		newnode->_col = root->_col;
    328. 		newnode->_left = Copy(root->_left);
    329. 		newnode->_right = Copy(root->_right);
    330. 		if (newnode->_left)
    331. 		{
    332. 			newnode->_left->_parent = newnode;
    333. 		}
    334. 		if (newnode->_right)
    335. 		{
    336. 			newnode->_right->_parent = newnode;
    337. 		}
    338. 		return newnode;
    339. 	}
    340. 	int _Height(Node* root)
    341. 	{
    342. 		if (root == nullptr)
    343. 		{
    344. 			return 0;
    345. 		}
    346. 		int leftheight = _Height(root->_left);
    347. 		int rightheight = _Height(root->_right);
    348. 		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
    349. 	}
    350. 	bool _IsBanlance(Node* root, int benchmark, int blacknum)
    351. 	{
    352. 		//检查每条路径黑节点的个数是否一致
    353. 		//以及是否有连续的红节点
    354. 		if (root == nullptr)
    355. 		{
    356. 			if (blacknum != benchmark)
    357. 			{
    358. 				cout << "存在路径黑色节点的数量不相等" << endl;
    359. 				return false;
    360. 			}
    361. 			return true;
    362. 		}
    363. 		if (root->_col == RED && root->_parent->_col == RED)//之所以可以这样是因为根节点是黑
    364. 		{
    365. 			cout << "存在连续的红节点" << endl;
    366. 		}
    367. 		if (root->_col == BLACK)
    368. 		{
    369. 			blacknum++;
    370. 		}
    371. 		return _IsBanlance(root->_left, benchmark, blacknum) && _IsBanlance(root->_right, benchmark, blacknum);
    372. 	}
    373. 	//void _Inorder(Node* root)
    374. 	//{
    375. 	//	if (root == nullptr)
    376. 	//	{
    377. 	//		return;
    378. 	//	}
    379. 	//	_Inorder(root->_left);
    380. 	//	cout << kov(root->_data) << endl;
    381. 	//	_Inorder(root->_right);
    382. 	//}
    383. 	void RotateR(Node* parent)
    384. 	{
    385. 		Node* subL = parent->_left;
    386. 		Node* subLR = subL->_right;
    387. 		if (subLR)
    388. 		{
    389. 			subLR->_parent = parent;
    390. 		}
    391. 		parent->_left = subLR;
    392. 		Node* Pparent = parent->_parent;
    393. 		subL->_right = parent;
    394. 		parent->_parent = subL;
    395. 		if (parent == _root)
    396. 		{
    397. 			_root = subL;
    398. 			subL->_parent = nullptr;
    399. 		}
    400. 		else
    401. 		{
    402. 			subL->_parent = Pparent;
    403. 			if (kov(parent->_data) > kov(Pparent->_data))
    404. 			{
    405. 				Pparent->_right = subL;
    406. 			}
    407. 			else
    408. 			{
    409. 				Pparent->_left = subL;
    410. 			}
    411. 		}
    412. 	}
    413. 	void RotateL(Node* parent)
    414. 	{
    415. 		Node* subR = parent->_right;
    416. 		Node* subRL = subR->_left;
    417. 		if (subRL)
    418. 		{
    419. 			subRL->_parent = parent;
    420. 		}
    421. 		parent->_right = subRL;
    422. 		Node* Pparent = parent->_parent;
    423. 		subR->_left = parent;
    424. 		parent->_parent = subR;
    425. 		if (parent == _root)
    426. 		{
    427. 			_root = subR;
    428. 			subR->_parent = nullptr;
    429. 		}
    430. 		else
    431. 		{
    432. 			subR->_parent = Pparent;
    433. 			if (kov(parent->_data) > kov(Pparent->_data))
    434. 			{
    435. 				Pparent->_right = subR;
    436. 			}
    437. 			else
    438. 			{
    439. 				Pparent->_left = subR;
    440. 			}
    441. 		}
    442. 	}
    443. 	Node* _root;
    444. 	KeyOfValue kov;
    445. };

    Mymap.h

    1. #pragma once
    2. #include "RBTree.h"
    3. namespace myset_map
    4. {
    5. 	template<class K,class V>
    6. 	class map
    7. 	{
    8. 	public:
    9. 		struct MapOfKey
    10. 		{
    11. 			const K& operator()(const pair& data)
    12. 			{
    13. 				return data.first;
    14. 			}
    15. 		};
    16. 		typedef typename RBTree, MapOfKey>::Iterator Iterator;
    17. 		Iterator begin()
    18. 		{
    19. 			return _t.begin();
    20. 		}
    21. 		Iterator end()
    22. 		{
    23. 			return _t.end();
    24. 		}
    25. 		pairbool> Insert(const pair& data)
    26. 		{
    27. 			return _t.Insert(data);
    28. 		}
    29. 		Iterator Find(const K& data)
    30. 		{
    31. 			return _t.Find(data);
    32. 		}
    33. 	private:
    34. 		RBTree, MapOfKey> _t;
    35. 	};
    36. }

    Myset.h

    1. #pragma once
    2. #include "RBTree.h"
    3. namespace myset_map
    4. {
    5. 	template<class K>
    6. 	class set
    7. 	{
    8. 	public:
    9. 		struct SetOfKey
    10. 		{
    11. 			const K& operator()(const K& key)
    12. 			{
    13. 				return key;
    14. 			}
    15. 		};
    16. 		typedef typename RBTree::Iterator Iterator;
    17. 		Iterator begin()
    18. 		{
    19. 			return _t.begin();
    20. 		}
    21. 		Iterator end()
    22. 		{
    23. 			return _t.end();
    24. 		}
    25. 		pairbool> Insert(const K& data)
    26. 		{
    27. 			return _t.Insert(data);
    28. 		}
    29. 		Iterator Find(const K& data)
    30. 		{
    31. 			return _t.Find(data);
    32. 		}
    33. 	private:
    34. 		RBTree _t;//使用拷贝构造的时候，对于类里面的成员，系统会自己完成浅拷贝。
    35. 								  //在一棵红黑树中，需要完成深拷贝。
    36. 	};
    37. }

    test.cpp(程序的入口)

    1. #include 
    2. using namespace std;
    3. #include "RBTree.h"
    4. #include "Myset.h"
    5. #include "Mymap.h"
    6. #include 
    7. #include 
    8. void test_myset()
    9. {
    10. 	myset_map::set<int> s;
    11. 	s.Insert(10);
    12. 	s.Insert(9);
    13. 	s.Insert(8);
    14. 	s.Insert(7);
    15. 	auto it = s.begin();
    16. 	while (it != s.end())
    17. 	{
    18. 		cout << *it << endl;
    19. 		++it;
    20. 	}
    21. 	cout << *s.Find(7) << endl;
    22. 	myset_map::set<int> copys(s);
    23. 	for (auto e : copys)
    24. 	{
    25. 		cout << e << endl;
    26. 	}
    27. }
    28. void test_mymap()
    29. {
    30. 	myset_map::map<int,int> s;
    31. 	//myset_map::map::MapOfKey kov;
    32. 	//cout << kov(make_pair(10, 10)) << endl;
    33. 	srand(time(0));
    34. 	vector<int> v;
    35. 	int N = 1000;
    36. 	for (int i = 0; i < 100; i++)
    37. 	{
    38. 		//v.push_back(rand() % 100);
    39. 		v.push_back(i);
    40. 	}
    41. 	for (auto e : v)
    42. 	{
    43. 		s.Insert(make_pair(e, e));
    44. 	}
    45. 	auto it = s.begin();
    46. 	while (it != s.end())
    47. 	{
    48. 		cout << it->first << it->second << " ";
    49. 		++it;
    50. 	}
    51. 	cout << endl;
    52. 	if (s.Find(7) != nullptr)
    53. 	{
    54. 		cout << s.Find(7)->first << endl;
    55. 	}
    56. 	myset_map::map<int,int> copys(s);
    57. 	auto its = copys.Find(99);
    58. 	cout << its->first << endl;
    59. 	//for (auto e : copys)
    60. 	//{
    61. 	//	cout << e.first << e.second << " ";
    62. 	//}
    63. 	while (its != copys.begin())
    64. 	{
    65. 		cout << its->first << its->second << " ";
    66. 		--its;
    67. 	}
    68. }
    69. int main()
    70. {
    71. 	//test_myset();
    72. 	test_mymap();
    73. 	return 0;
    74. }
  • 相关阅读:
    观测云产品更新 | 监控、图表、服务管理、单点登录、Pipeline 等优化
    Java 轻松删除PDF指定页、空白页 （免费工具分享）
    LDA代码训练报错记录
    Go语言相比较于Python的优势
    Golang开发软件
    【KCP】UDP可靠性传输
    Linux文件系统
    【算法与数据结构】235、LeetCode二叉搜索树的最近公共祖先
    并发编程中常见的设计模式
    redis命令使用
  • 原文地址：https://blog.csdn.net/qq_54178958/article/details/127392810