• C++之Map与Set的模拟实现

    前言：看这篇博客前首先得看博主关于红黑树的实现：C++之红黑树_cls-evd的博客-CSDN博客

    目录

    前言：看这篇博客前首先得看博主关于红黑树的实现：C++之红黑树_cls-evd的博客-CSDN博客

    一、set与map的源码分析

    源码中的set:

    ​编辑源码中的map:​编辑源码中的红黑树：​编辑

    二、map与set的建立

    三、红黑树节点的修改

    四、红黑树的修改

    insert的修改

    五、迭代器的实现

    迭代器的大框架

    begin的实现

    end的实现 

    operator++的实现

    operator--的实现

    operator[] 的实现（针对于map）

    六、红黑树成员函数的实现

    拷贝构造的实现

    拷贝构造的注意事项

    赋值运算符的实现

    总结及代码

    问题：map/set既然是对红黑树的封装，那么他俩为啥不是适配器？

    完整代码 

    一、set与map的源码分析

    map是kv结构，set的key结构，但是它俩的底层都是红黑树，那么我们实现它俩的时候是应该实现一红黑棵树呢？还是应该用两棵树？如果用一棵树该如何控制kv与k呢？但是如果使用两棵树代码又是冗余的，该如何解决呢？基于当前的原因我们可以看一看源码。

    源码中的set:

    源码中的map:源码中的红黑树：

    源码中是只有一颗红黑树的，它实现两个结构的容器的奥秘就在红黑树的节点

    这个容器是set还是map取决于节点里面存的是key还是pair

    我们就根据源码的思想进行实现。

    二、map与set的建立

    三、红黑树节点的修改

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

    四、红黑树的修改

    insert的修改

    （1）原本我们插入的是pair现在都要换成data，最终目的就是实现复用

    （2）同样的insert的比较也就不能使用了，因为现在我们比较的是data。如果data是key没有任何问题，但是如果data是pair我们该如何解决呢？ 

    虽然这里不进行修改也不会报错，因为pair本身就支持比较大小，但是pair的比较大小不符合我们的意义 ，pair的小于的定义是first和second有一个小就可以。但是遇到pair我们期望的是只利用pair里面的first比较大小。解决该问题的关键就是源码中红黑树的keyOfValue模板参数。它的作用就是如果你传过来的是key直接返回key，如果你传过来的是pair返回pair的first，由此进行比较，这个模板参数的本质就是一个仿函数。

    我们自己实现的叫：keyOfT

    相应的map与set建立对应的keyOfT结构体，通过重载()实现返回key或者返回kv.first

     

    红黑树中则通过创建keyOfT的一个对象，这个对象的operator()就可以把他们的值给取出来。

    目前为止set与map的插入就实现好了。

    五、迭代器的实现

    实际上set与map的迭代器就是红黑树的迭代器，所以我们实现出红黑树的迭代器即可。 

    迭代器的大框架

    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. 	Node* _node;
    7.  
    8. 	RBTreeIterator(Node* node)
    9. 		:_node(node)
    10. 	{}
    11.  
    12. 	Ref operator*()
    13. 	{
    14. 		return _node->_data;
    15. 	}
    16.  
    17. 	Ptr operator->()
    18. 	{
    19. 		return &(_node->_data);
    20. 	}
    21.  
    22. 	Self& operator ++()
    23. 	{
    24. 		
    25. 	}
    26.  
    27. 	bool operator!=(const Self& s)
    28. 	{
    29. 		return _node != s._node;
    30. 	}
    31.  
    32. 	//Self& operator--()
    33. 	//{
    34.  
    35. 	//}
    36. };

    红黑树中就需要typedef一个迭代器

    begin的实现

    begin就是最左节点

    1. 	iterator begin()
    2. 	{
    3. 		Node* min = _root;
    4. 		while (min && min->_left) //最左节点
    5. 		{
    6. 			min = min->_left;
    7. 		}
    8. 		return iterator(min);//构造一个迭代器
    9. 	}

    end的实现 

    1. 	iterator end()
    2. 	{
    3. 		return iterator(nullptr); //end也就是最后一个数据的下一个位置，这里我们用nullptr替代
    4. 	}

    operator++的实现

    1.如果右子树不为空，中序的下一个就是右子树的最左节点
    2.如果右子树是空，说明我所在的子树已经访问完了，如果我是父亲的左边，下一个访问的就是父亲。如果我是父亲的右，说明一中序已经完了，我就要访问我父亲的父亲。
    所以我就要沿着根路径，找孩子是父亲左的祖先。直到父亲为空
    因为它有三叉链才能这样不借助栈

    1. 	//前置++
    2. 	Self& operator ++()
    3. 	{
    4. 		if (_node->_right) //访问右子树的最左节点
    5. 		{
    6. 			Node* min = _node->_right;
    7. 			while (min->_left)
    8. 			{
    9. 				min = min->_left;
    10. 			}
    11. 			_node = min;
    12. 		}
    13. 		else
    14. 		{
    15. 			Node* cur = _node;
    16. 			Node* parent = cur->_parent;
    17. 			while (parent && cur == parent->_right) //parent是进判断根节点的
    18. 			{
    19. 				cur = cur->_parent;
    20. 				parent = parent->_parent;
    21. 			}
    22.  
    23. 			_node = parent;
    24. 		}
    25.  
    26. 		return *this;
    27. 	}

    operator--的实现

    1. 	Self& operator--()
    2. 	{  
    3. 		//右根左，左树不为空就访问左树的最右节点，左树为空就去访问祖先里面
    4. 		if (_node->_left)
    5. 		{
    6. 			Node* max = _node->_left;
    7. 			while (max->_right)
    8. 			{
    9. 				max = max->_right;
    10. 			}
    11. 			_node = max;
    12. 		}
    13. 		else
    14. 		{
    15. 			Node* cur = _node;
    16. 			Node* parent = cur->_parent;
    17. 			while (parent&&cur==parent->_left)
    18. 			{
    19. 				cur = cur->_parent;
    20. 				parent = parent->_parent;
    21. 			}
    22. 			_node = parent;
    23. 		}
    24. 		
    25. 		return *this;
    26. 	}

    Find的实现

    map/set对Find进行一次封装就是find

    1. 	iterator Find(const K& key)
    2. 	{
    3. 		Node* cur = _root;
    4. 		KeyOfT kot;
    5. 		while (cur)
    6. 		{
    7. 			if (kot(cur->_data) < key)
    8. 			{
    9. 				cur = cur->_right;
    10. 			}
    11. 			else if (kot(cur->_data) > key)
    12. 			{
    13. 				cur = cur->_left;
    14. 			}
    15. 			else
    16. 			{
    17. 				return iterator(cur);
    18. 			}
    19. 		}
    20.  
    21. 		return end();
    22. 	}

    operator[] 的实现（针对于map）

    首先改造一个插入。将插入的返回值设置为pair,并且跟据相应的规则，如果插入成功返回新插入的节点，如果插入失败返回当前节点。 

    [ ]的实现:

    返回map中的value，ret就是pair<iterator,bool>，pair的first就是iterator，map的iterator就是pair<key,value>。V()会调用V对应的默认构造函数。

    1. 		V& operator[](const K& key)
    2. 		{
    3. 			auto ret = _t.Insert(make_pair(key, V()));
    4. 			return ret.first->second;
    5. 		}

    执行结果： 

    六、红黑树成员函数的实现

    拷贝构造的实现

    这里我们没写拷贝构造发现拷贝成功了，是不是就意味着不需要我们再写了呢？

    现在是一个浅拷贝，没有在这里崩溃就是因为我们没写析构函数，析构两次才会崩溃的。

    当我们实现好红黑树的析构以后，自然而然的也就崩溃了

    所以我们得自己实现深拷贝。

    深拷贝实现的思路就是递归的去拷贝，同时要注意我们这里是三叉链要进行链接parent，颜色也需要我们进行拷贝。

    1. 	RBTree(const RBTree<K, T, KeyOfT>& t)
    2. 	{
    3. 		_root = Copy(t._root);
    4. 	}
    5.  
    6. 	Node* Copy(Node* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			return nullptr;
    11. 		}
    12. 		
    13. 		Node* newRoot = new Node(root->_data);
    14. 		newRoot->_col = root->_col;
    15.  
    16. 		newRoot->_left = Copy(root->_left);
    17. 		newRoot->_right = Copy(root->_right);
    18. 		
    19. 		if (newRoot->_left)
    20. 		{
    21. 			newRoot->_left->_parent = newRoot;
    22. 		}
    23.  
    24. 		if (newRoot->_right)
    25. 		{
    26. 			newRoot->_right->_parent = newRoot;
    27. 		}
    28.  
    29. 		return newRoot;
    30. 	}

    这下我们的拷贝构造就没有问题了

    拷贝构造的注意事项

    1.不能去调用红黑树叶子节点的拷贝构造

    new这里用的就是拷贝构造，我们的节点没有写拷贝构造会调用默认的，又因为我们节点中定义的全是指针，全是内置类型，都会进行拷贝

    结果看似正确，但是实际这棵树已经非常的乱了。

     我们以根放的左子树为例

    copy这棵树唯独parent没有进行深拷贝还是进行了浅拷贝，因此copy这个数的祖先和s这个数的祖先一模一样，这种问题很难被发现，尤其是当你进行插入的时候，如果你往copy这个树插入节点你就会惊奇的发现新插入的节点居然出现在了s这棵树上。

    赋值运算符的实现

    1. 	RBTree<K, T, KeyOfT>& operator =(RBTree<K, T, KeyOfT>& t)
    2. 	{
    3. 		swap(_root, t._root);
    4. 		return *this;
    5. 	}

    empty()接口的实现

    红黑树为空返回0，不为空返回1

    1. 	bool Empty()const
    2. 	{
    3. 		if (_root == nullptr)
    4. 			return false;
    5.  
    6. 		return true;
    7. 	}

    size()接口的实现

    返回红黑树总结点的个数

    1. 	size_t Size()const
    2. 	{
    3. 		return SizeNode(_root);
    4. 	}
    5.  
    6. 	size_t SizeNode(Node* root) const
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			return 0;
    11. 		}
    12. 		return SizeNode(root->_left) + SizeNode(root->_right) + 1;
    13. 	}

    clear()接口的实现 

    将树中的节点全都清理掉

    1. 	void Clear()
    2. 	{
    3. 		Destroy(_root);
    4. 		_root = nullptr;
    5. 	}
    6. 	void Destroy(Node* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			return;
    11. 		}
    12. 		Destroy(root->_left);
    13. 		Destroy(root->_right);
    14. 		delete root;
    15. 	}

    总结及代码

    map和set就是依靠我们的红黑树实现的，它俩本身就是一个空壳子，就是再对红黑树进行封装。我们同时发现map与set我们都没有进行实现成员函数都用的是默认的成员函数，因为红黑树是set/map里面的自定义类型.eg:我们去调用set/map的构造，但是set/map没有写构造就会调用他们的默认构造函数，默认构造函数对于自定义类型就会去调用红黑树的构造。

    总之默认生成的成员函数就会去调用红黑树成员函数。

    问题：map/set既然是对红黑树的封装，那么他俩为啥不是适配器？

    stack/queue/priority_queue 封装的是deque/vector 他们是适配器，而map/set 封住的是红黑树 他们就不是不是适配器

    这里以stack和map为例

    关键点就在于这个Container，它是可以进行任意替换的，但是map/set就不存在这样的一个Container，简单来说就是stack的底层能改，但是map的底层是改不了的。所以map/set就不是适配器。     

    完整代码 

    RBTree.h

    1. #pragma once
    2. #include<iostream>
    3. #include<vector>
    4. using namespace std;
    5.  
    6. enum Colour
    7. {
    8. 	RED,
    9. 	BLACK
    10. };
    11.  
    12. template<class T>
    13. struct RBTreeNode
    14. {
    15. 	RBTreeNode<T>* _left;
    16. 	RBTreeNode<T>* _right;
    17. 	RBTreeNode<T>* _parent;
    18. 	T _data;
    19. 	
    20. 	Colour _col;
    21.  
    22. 	RBTreeNode(const T& data)
    23. 		:_left(nullptr)
    24. 		, _right(nullptr)
    25. 		, _parent(nullptr)
    26. 		, _col(RED) //红的黑的都无所谓
    27. 		, _data(data)
    28. 	{}
    29. };
    30.  
    31. template<class T, class Ref, class Ptr>
    32. struct RBTreeIterator
    33. {
    34. 	typedef RBTreeNode<T> Node;
    35. 	typedef RBTreeIterator<T, Ref, Ptr> Self;
    36.  
    37.  
    38. 	RBTreeIterator(Node* node) //只需要构造函数，迭代器没什么资源要去释放，一个迭代器赋值给另外一个迭代器只需要浅拷贝就可
    39. 		:_node(node)
    40. 	{}
    41.  
    42. 	Ref operator*() //返回里面的数据
    43. 	{
    44. 		return _node->_data;
    45. 	}
    46.  
    47. 	Ptr operator->() //返回地址
    48. 	{
    49. 		return &(_node->_data);
    50. 	}
    51.  
    52. 	//前置++
    53. 	Self& operator ++()
    54. 	{
    55. 		Increament();
    56. 		return *this;
    57. 	}
    58. 	Self operator++(int)
    59. 	{
    60. 		Self tmp(*this);
    61. 		Increament();
    62. 		return tmp;
    63. 	}
    64.  
    65. 	Self& operator--()
    66. 	{
    67. 		DeIncreament();
    68. 		return *this;
    69. 	}
    70.  
    71. 	Self operator--(int)
    72. 	{
    73. 		Self tmp(*this);
    74. 		DeIncreament();
    75. 		return tmp;
    76. 	}
    77. 	bool operator!=(const Self& s) const
    78. 	{
    79. 		return _node != s._node;
    80. 	}
    81. 	bool operator==(const Self& s) const
    82. 	{
    83. 		return _node == s._node;
    84. 	}
    85.  
    86.  
    87.  
    88. private:
    89. 	void Increament()
    90. 	{
    91. 		if (_node->_right) //访问右子树的最左节点
    92. 		{
    93. 			Node* min = _node->_right;
    94. 			while (min->_left)
    95. 			{
    96. 				min = min->_left;
    97. 			}
    98. 			_node = min;
    99. 		}
    100. 		else
    101. 		{
    102. 			Node* cur = _node;
    103. 			Node* parent = cur->_parent;
    104. 			while (parent && cur == parent->_right) //parent是进判断根节点的
    105. 			{
    106. 				cur = cur->_parent;
    107. 				parent = parent->_parent;
    108. 			}
    109.  
    110. 			_node = parent;
    111. 		}
    112. 	}
    113. 	void DeIncreament()
    114. 	{
    115. 		//右根左，左树不为空就访问左树的最右节点，左树为空就去访问祖先里面
    116. 		if (_node->_left)
    117. 		{
    118. 			Node* max = _node->_left;
    119. 			while (max->_right)
    120. 			{
    121. 				max = max->_right;
    122. 			}
    123. 			_node = max;
    124. 		}
    125. 		else
    126. 		{
    127. 			Node* cur = _node;
    128. 			Node* parent = cur->_parent;
    129. 			while (parent && cur == parent->_left)
    130. 			{
    131. 				cur = cur->_parent;
    132. 				parent = parent->_parent;
    133. 			}
    134. 			_node = parent;
    135. 		}
    136. 	}
    137. 	Node* _node; //迭代器就是一个节点的指针
    138. };
    139.  
    140.  
    141.  
    142. //set RBTree<K,K,MapKeyOfT>
    143. //map RBTree<K,pair<K,V>,MapKeyOfT>
    144. template<class K, class T, class KeyOfT> 
    145. struct RBTree
    146. {
    147. 	typedef RBTreeNode<T> Node;
    148. public:
    149.  
    150. 	typedef RBTreeIterator<T, T&, T*> iterator;
    151. 	typedef RBTreeIterator<T, const T&, const T*> const_iterator;
    152.  
    153. 	iterator begin()
    154. 	{
    155. 		Node* min = _root;
    156. 		while (min && min->_left) //最左节点
    157. 		{
    158. 			min = min->_left;
    159. 		}
    160. 		return iterator(min);//构造一个迭代器
    161. 	}
    162.  
    163. 	iterator end()
    164. 	{
    165. 		return iterator(nullptr); //end也就是最后一个数据的下一个位置，这里我们用nullptr替代
    166. 	}
    167.  
    168. 	iterator Find(const K& key)
    169. 	{
    170. 		Node* cur = _root;
    171. 		KeyOfT kot;
    172. 		while (cur)
    173. 		{
    174. 			if (kot(cur->_data) < key)
    175. 			{
    176. 				cur = cur->_right;
    177. 			}
    178. 			else if (kot(cur->_data) > key)
    179. 			{
    180. 				cur = cur->_left;
    181. 			}
    182. 			else
    183. 			{
    184. 				return iterator(cur);
    185. 			}
    186. 		}
    187.  
    188. 		return end();
    189. 	}
    190.  
    191. 	bool Empty()const
    192. 	{
    193. 		if (_root == nullptr)
    194. 			return false;
    195.  
    196. 		return true;
    197. 	}
    198.  
    199. 	size_t Size()const
    200. 	{
    201. 		return SizeNode(_root);
    202. 	}
    203.  
    204. 	void Clear()
    205. 	{
    206. 		Destroy(_root);
    207. 		_root = nullptr;
    208. 	}
    209.  
    210. 	RBTree()
    211. 		:_root(nullptr)
    212. 	{}
    213.  
    214. 	RBTree(const RBTree<K, T, KeyOfT>& t)
    215. 	{
    216. 		_root = Copy(t._root);
    217. 	}
    218.  
    219. 	RBTree<K, T, KeyOfT>& operator =(RBTree<K, T, KeyOfT>& t)
    220. 	{
    221. 		swap(_root, t._root);
    222. 		return *this;
    223. 	}
    224.  
    225. 	~RBTree()
    226. 	{
    227. 		Destroy(_root);
    228. 		_root = nullptr;
    229. 	}
    230.  
    231. 	pair<iterator, bool> Insert(const T& data) //如果是set T就是key,如果是map，T就是pair
    232. 	{
    233. 		if (_root == nullptr)
    234. 		{
    235. 			_root = new Node(data);
    236. 			_root->_col = BLACK; //将根节点处理成黑色
    237. 			return make_pair(iterator(_root), true);
    238. 		}
    239.  
    240. 		KeyOfT kot;
    241.  
    242. 		Node* parent = nullptr;
    243. 		Node* cur = _root;
    244. 		while (cur)
    245. 		{
    246. 			if (kot(cur->_data) < kot(data))
    247. 			{
    248. 				parent = cur;
    249. 				cur = cur->_right;
    250. 			}
    251. 			else if (kot(cur->_data) > kot(data))
    252. 			{
    253. 				parent = cur;
    254. 				cur = cur->_left;
    255. 			}
    256. 			else
    257. 			{
    258. 				return make_pair(iterator(cur), false);
    259. 			}
    260. 		}
    261.  
    262. 		cur = new Node(data);
    263. 		Node* newnode = cur;
    264. 		cur->_col = RED; //新增节点处理成红色
    265.  
    266. 		if (kot(parent->_data) < kot(data))
    267. 		{
    268. 			parent->_right = cur;
    269. 			cur->_parent = parent; //把三叉链链上
    270. 		}
    271. 		else
    272. 		{
    273. 			parent->_left = cur;
    274. 			cur->_parent = parent;
    275. 		}
    276.  
    277. 		//控制平衡
    278. 		while (parent&& parent->_col == RED) //父亲存在且为红一定不是根
    279. 		{
    280. 			Node* grangfather = parent->_parent;
    281. 			if (parent == grangfather->_left) //父亲在g的左
    282. 			{
    283. 				Node* uncle = grangfather->_right;
    284. 				if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红
    285. 				{
    286. 					//变色+继续向上处理
    287. 					parent->_col = uncle->_col = BLACK;
    288. 					grangfather->_col = RED;
    289.  
    290. 					cur = grangfather;
    291. 					parent = cur->_parent;
    292. 				}
    293. 				else //情况二+三：叔叔存在/叔叔存在且为黑  
    294. 				{
    295. 					//        g    
    296. 					//    p
    297. 					//c
    298.  
    299. 					//        g
    300. 					//    p
    301. 					//        c
    302.  
    303. 					if (cur == parent->_left) //情况二
    304. 					{ 
    305. 						//单旋
    306. 						RotateR(grangfather);
    307. 						parent->_col = BLACK;
    308. 						grangfather->_col = RED;
    309. 					}
    310. 					else  //情况三
    311. 					{
    312. 						//双旋
    313. 						RotateL(parent);
    314. 						RotateR(grangfather);
    315. 						cur->_col = BLACK;
    316. 						grangfather->_col = RED;
    317. 					}
    318.  
    319. 					break; //我这棵树旋转完成了后，每条路径黑节点的个数没变，不会影响其他路径，这棵字树的根已经是黑色了，与情况一不同
    320. 				}
    321.  
    322. 			}
    323. 			else//parent == grangfather->_right p在g的右
    324. 			{
    325. 				Node* uncle = grangfather->_left;
    326. 				if (uncle && uncle->_col == RED)//情况一：叔叔存在且为红
    327. 				{
    328. 					//变色+继续向上处理
    329. 					parent->_col = uncle->_col = BLACK;
    330. 					grangfather->_col = RED;
    331.  
    332. 					cur = grangfather;
    333. 					parent = cur->_parent;
    334. 				}
    335. 				else //情况二+三：叔叔存在/叔叔存在且为黑  
    336. 				{
    337. 					//      g
    338. 					//           p
    339. 					//               c
    340.  
    341.  
    342. 					//      g
    343. 					//           p
    344. 					//      c
    345. 					if (cur == parent->_right) //情况二
    346. 					{
    347. 						RotateL(grangfather);
    348. 						parent->_col = BLACK;
    349. 						grangfather->_col = RED;
    350. 					}
    351. 					else //情况三
    352. 					{
    353. 						RotateR(parent);
    354. 						RotateL(grangfather);
    355. 						cur->_col = BLACK;
    356. 						grangfather->_col = RED;
    357. 					}
    358.  
    359. 					break; //我这棵树旋转完成了后，每条路径黑节点的个数没变，不会影响其他路径，这棵字树的根已经是黑色了，与情况一不同
    360. 				}
    361. 			}
    362. 		}
    363.  
    364. 		_root->_col = BLACK;
    365.  
    366. 		return make_pair(iterator(newnode), true);
    367. 	}
    368.  
    369. private:
    370. 	void Destroy(Node* root)
    371. 	{
    372. 		if (root == nullptr)
    373. 		{
    374. 			return;
    375. 		}
    376. 		Destroy(root->_left);
    377. 		Destroy(root->_right);
    378. 		delete root;
    379. 	}
    380.  
    381. 	Node* Copy(Node* root)
    382. 	{
    383. 		if (root == nullptr)
    384. 		{
    385. 			return nullptr;
    386. 		}
    387.  
    388.  
    389. 		Node* newRoot = new Node(root->_data);
    390. 		newRoot->_col = root->_col;
    391.  
    392. 		newRoot->_left = Copy(root->_left);
    393. 		newRoot->_right = Copy(root->_right);
    394.  
    395. 		//增加上三叉连的链接关系
    396. 		if (newRoot->_left)
    397. 		{
    398. 			newRoot->_left->_parent = newRoot;
    399. 		}
    400.  
    401. 		if (newRoot->_right)
    402. 		{
    403. 			newRoot->_right->_parent = newRoot;
    404. 		}
    405.  
    406. 		return newRoot;
    407. 	}
    408.  
    409. 	size_t SizeNode(Node* root) const
    410. 	{
    411. 		if (root == nullptr)
    412. 		{
    413. 			return 0;
    414. 		}
    415. 		return SizeNode(root->_left) + SizeNode(root->_right) + 1;
    416. 	}
    417.  
    418. 	void RotateR(Node* parent)
    419. 	{
    420. 		Node* subL = parent->_left;
    421. 		Node* subLR = subL->_right;
    422.  
    423. 		parent->_left = subLR;
    424. 		if (subLR) //不为空才链接，否则就出现空指针问题
    425. 		{
    426. 			subLR->_parent = parent;
    427. 		}
    428.  
    429. 		Node* parentParent = parent->_parent; //提前记录一下parent的父亲
    430.  
    431. 		subL->_right = parent;
    432. 		parent->_parent = subL;
    433.  
    434. 		if (parent == _root) //如果是一颗独立的树
    435. 		{
    436. 			_root = subL;
    437. 			_root->_parent = nullptr;
    438. 		}
    439. 		else
    440. 		{
    441. 			if (parentParent->_left == parent) //改变parent父亲的链接
    442. 			{
    443. 				parentParent->_left = subL;
    444. 			}
    445. 			else
    446. 			{
    447. 				parentParent->_right = subL;
    448. 			}
    449.  
    450. 			subL->_parent = parentParent; //注意三叉链接
    451. 		}
    452.  
    453. 	}
    454.  
    455. 	void RotateL(Node* parent)
    456. 	{
    457. 		Node* subR = parent->_right;
    458. 		Node* subRL = subR->_left;
    459.  
    460. 		parent->_right = subRL;
    461. 		if (subRL)
    462. 		{
    463. 			subRL->_parent = parent;
    464. 		}
    465.  
    466. 		Node* parentParent = parent->_parent;
    467. 		subR->_left = parent;
    468. 		parent->_parent = subR;
    469.  
    470. 		if (parent == _root)
    471. 		{
    472. 			_root = subR;
    473. 			_root->_parent = nullptr;
    474. 		}
    475. 		else
    476. 		{
    477. 			if (parentParent->_left == parent)
    478. 			{
    479. 				parentParent->_left = subR;
    480. 			}
    481. 			else
    482. 			{
    483. 				parentParent->_right = subR;
    484. 			}
    485. 			subR->_parent = parentParent;
    486. 		}
    487.  
    488. 	}
    489.  
    490.  
    491. private:
    492. 	Node* _root; //内置类型
    493.  
    494. };

    MySet.h

    1. #pragma once
    2. #include"RBTree.h"
    3. namespace pxl
    4. {
    5. 	template<class K>
    6. 	class set 
    7. 	{
    8. 	public:
    9. 		struct SetKeyOfT
    10. 		{
    11. 			const K& operator()(const K& k)
    12. 			{
    13. 				return k;
    14. 			}
    15. 		};
    16.  
    17. 		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    18.  
    19. 		iterator begin()
    20. 		{
    21. 			return _t.begin();
    22. 		}
    23.  
    24. 		iterator end()
    25. 		{
    26. 			return _t.end();
    27. 		}
    28.  
    29. 		pair<iterator, bool> insert(const K& key)
    30. 		{
    31. 			return _t.Insert(key);
    32. 		}
    33.  
    34. 		iterator find(const K& key)
    35. 		{
    36. 			return _t.Find(key);
    37. 		}
    38. 		bool empty()const
    39. 		{
    40. 			return _t.Empty();
    41. 		}
    42.  
    43. 		size_t size()const
    44. 		{
    45. 			return _t.Size();
    46. 		}
    47. 		void clear()
    48. 		{
    49. 			_t.Clear();
    50. 		}
    51. 	private:
    52. 		RBTree<K, K, SetKeyOfT> _t; //自定义类型，调用它的拷贝构造，但是红黑树的拷贝构造也没写
    53. 		//红黑树是set/map里面的自定义类型，我们去调用set的构造，但是set没有写构造，就会去调用红黑树的构造
    54. 		//总之默认生成的成员函数就会去调用红黑树成员函数
    55. 	};
    56.  
    57.  
    58. 	void test_set()
    59. 	{
    60. 		set<int> s;
    61. 		s.insert(1);
    62. 		s.insert(4);
    63. 		s.insert(2);
    64. 		s.insert(6);
    65. 	
    66. 		set<int>::iterator it = s.begin();
    67. 		while (it != s.end())
    68.         {
    69. 			cout << *it <<" ";
    70. 			++it;
    71. 		}
    72. 		cout << endl;
    73.  
    74. 		set<int> copy(s);
    75. 		for (auto e : copy)
    76. 		{
    77. 			cout << e << " ";
    78. 		}
    79. 	}
    80. }

    MyMap.h

    1. #pragma once
    2. #include"RBTree.h"
    3.  
    4. namespace pxl
    5. {
    6. 	template<class K, class V>
    7. 	class map
    8. 	{
    9. 	public:
    10. 		struct MapKeyOfT
    11. 		{
    12. 			const K& operator()(const pair<K, V>& kv)
    13. 			{
    14. 				return kv.first;
    15. 			}
    16. 		};
    17. 		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 
    18. 		//对类模板里面的内嵌类型进行typedef
    19.  
    20. 		iterator begin()
    21. 		{
    22. 			return _t.begin();
    23. 		}
    24.  
    25. 		iterator end()
    26. 		{
    27. 			return _t.end();
    28. 		}
    29.  
    30. 		pair<iterator, bool> insert(const pair<K, V>& kv)
    31. 		{
    32. 			return _t.Insert(kv);
    33. 		}
    34.  
    35. 		iterator find(const K& key)
    36. 		{
    37. 			return _t.Find(key);
    38. 		}
    39.  
    40. 		V& operator[](const K& key)
    41. 		{
    42. 			auto ret = _t.Insert(make_pair(key, V()));
    43. 			return ret.first->second;
    44. 		}
    45. 		bool empty()const
    46. 		{
    47. 			return _t.Empty();
    48. 		}
    49.  
    50. 		size_t size()const
    51. 		{
    52. 			return _t.Size();
    53. 		}
    54. 		void clear()
    55. 		{
    56. 			_t.Clear();
    57. 		}
    58. 	private:
    59. 		RBTree<K, pair<K, V>, MapKeyOfT> _t;
    60. 	};
    61.  
    62. 	void test_map()
    63. 	{
    64. 		map<int, int> m;
    65. 		m.insert(make_pair(3, 3));
    66. 		m.insert(make_pair(5, 5));
    67. 		m.insert(make_pair(1, 1));
    68. 		m.insert(make_pair(8, 8));
    69. 		m[7];
    70. 		m[8] = 88;
    71.  
    72. 		map<int,int>::iterator it = m.begin();
    73. 		while (it != m.end())
    74. 		{
    75. 			cout << it->first << ":" << it->second << endl;
    76. 			++it;
    77. 		}
    78. 		cout << endl;
    79.  
    80. 	}
    81. }

  • 相关阅读:
    终极篇章1——(16000字)SpringBoot启动原理分析(第一部分)
    Talk预告 | 北京大学杨灵：扩散生成模型的方法、关联与应用
    C++ STL标准模板库(一)
    Python基本功
    策略模式实现方式之Map＜K,Function＞
    Hyperf基础使用
    阿里在开源领域又有哪些新动向？来首届阿里开源开放周找答案！
    实时语音通讯技术：多人通话和语音识别
    K8S的控制器Deployment,ReplicaSet,StatefulSet,CronJob,最小单位pod
    【C语言进阶】文件操作（二）
  • 原文地址：https://blog.csdn.net/qq_52433890/article/details/124942770