• c++——map和set的封装

    注：该封装基于前面博客已实现红黑树，map和set封装并不难，主要还是对红黑树的理解

    目录

    一. 改造红黑树

    1. 改变节点的定义，使用更高维度的泛型

    2. 红黑树追加迭代器的实现

    1. 红黑树迭代器的构造函数和基本框架

    2. begin()和end()的实现

    3. operator*和operator->的实现

    4. operator++和operator--的实现

    5. operator!=和operator==的实现

    ３. 对RBTree类进行改变

    1. 改造insert

    2. 增加find的实现

    4. 改造后的RBTree树代码展示

    二. 封装set

    三. 封装map

    一. 改造红黑树

    颜色定义不更改，但是由于我们是使用一颗红黑树同时来作为封装set和map的底层结构，因此对数据类型需要进行处理，这里参考stl源码给出的解决方式是使用更高维度的泛型，因此我们也定义成更高维度的泛型，即数据类型这里我们使用T来接受va类型。

    即我们不再使用KV的形式接受数据，而是用T来接受数据，T决定红黑树存什么数据。

    这里和节点定义一样，我们使用T来接受数据，T决定红黑树存什么数据，对于set来说RBTree传进来的是K，对于map来说RBTree>传进来的是pair类型。

    虽然用T能解决传进来不同的数据类型，但是由于我们需要取K，对于set来说K就是K，但是，对于map来说是pair的第一个参数，所以由于无法确定T是K还是pair类型，无法准确去取出来T中的类型。

    根据官方库可以发现再引进来一个模板参数KeyOfT，用来取出T中的类型，而这个KeOfT传给RBTree的，查看set和map后源码后发现KeyOfT其实是一个仿函数，用来提取T中类型的K的，因此我们就知道RBTree应该有三个模板参数，分别是K，T和KeyOfT

    1. 改变节点的定义，使用更高维度的泛型

    有了以上推论，我们可以对节点定义进行改变

    1. //改变红黑节点的定义，使用更高维度的泛型
    2. template<class T>
    3. struct RBTreeNode
    4. {
    5. 	RBTreeNode* _left;
    6. 	RBTreeNode* _right;
    7. 	RBTreeNode* _parent;
    8. 	T _data;
    9. 	color _col;
    10.  
    11. 	//构造函数
    12. 	RBTreeNode(const T& data)
    13. 		:_left(nullptr)
    14. 		,_right(nullptr)
    15. 		,_parent(nullptr)
    16. 		,_data(data)
    17. 		,_col(RED)
    18. 	{}
    19. };

    这里使用T来标识数据类型，因为节点可能是K类型的（set传过来的），也可能是pair类型的（map传过来的）

    2. 红黑树追加迭代器的实现

    由于map和set都需要用到迭代器，但是两者的迭代器实际上都是封装了红黑树的迭代器，因此我们要先实现红黑树的迭代器，这里迭代器的实现和链表极其相似，因此，也是使用三个模板参数，分别代表普通类型，引用类型，指针类型，库里的实现是采用了哨兵卫的头节点的方式，但是这里并不这样做

    1. 红黑树迭代器的构造函数和基本框架

    1. template<class T, class Ref, class Ptr>
    2. struct __RBTreeIterator
    3. {
    4. 	typedef RBTreeNode Node;//方便使用节点
    5. 	typedef __RBTreeIterator Self;//方便使用自己
    6. 	Node* _node;//节点指针
    7.  
    8.     //迭代器构造函数
    9. 	__RBTreeIterator(Node* node)
    10. 		:_node(node)
    11. 	{}
    12.  
    13. 	operator*()
    14. 	{}
    15.  
    16. 	operator->()
    17. 	{}
    18.  
    19. 	operator++()
    20. 	{}
    21.  
    22. 	operator++(int)
    23. 	{}
    24.  
    25. 	operator--()
    26. 	{}
    27.  
    28. 	operator--(int)
    29. 	{}
    30.  
    31. 	operator!=(const Self& s) const
    32. 	{}
    33.  
    34. 	operator==(const Self& s) const
    35. 	{}
    36.  
    37. };

    和链表迭代器的实现基本一致，将迭代器的基本功能实现

    2. begin()和end()的实现

    由于迭代器访问的顺序是按照二叉平衡搜索树的中序的顺序访问的，因此我们也不能坏这个规则。

    按中序访问的思路，左子树->根->右子树：

    begin应该返回中序的第一个元素，即需要去找二叉平衡搜索树的最左节点：

    1.     iterator Begin()
    2. 	{
    3. 		Node* subleft = _root;
    4. 		while (subleft && subleft->_left)
    5. 		{
    6. 			subleft = subleft->_left;
    7. 		}
    8.  
    9. 		return iterator(subleft);
    10. 	}

    由于迭代器是自己实现的类，因此应该用迭代器创建对象并返回

     end()应该返回的是nullptr，因为最后遍历完成后应该是遍历到最右节点的nullptr节点

    1.     iterator End()
    2. 	{
    3. 		return iterator(nullptr);
    4. 	}

    直接用迭代器创建一个对象并传nullptr

    3. operator*和operator->的实现

    和链表一样，operator*返回节点中的数据operator->返回节点数据的地址（原因已在链表迭代器实现已解释，不做过多赘述）

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

    4. operator++和operator--的实现

    由于begin()，是按照中序的方式访问的，++可以分为两种情况，当右子树不存在为空时，找孩子是祖先的左的那个祖先节点，当右子树存在不为空时，找右子树的最左节点

    有如下图红黑树：

    一开始begin()迭代器应该位于节点为1处，当我们要++遍历这颗红黑树时：

    由于1的右子树不为空，找右子树的最左节点，最左节点为空，则++以后访问到是6，由于6的右子树为空，再++应该去找孩子是祖先的左的那个祖先节点，此时找到就是节点为8的祖先节点，此时发现，这就已经按中序的方式运行起来了

    ++迭代器的实现方式如下代码：

    1.     Self& operator++()
    2. 	{
    3. 		if (_node->_right == nullptr)
    4. 		{
    5. 			Node* cur = _node;
    6. 			Node* parent = cur->_parent;
    7. 			while (parent && parent->_right == cur)
    8. 			{
    9. 				cur = parent;
    10. 				parent = parent->_parent;
    11. 			}
    12.  
    13. 			_node = parent;
    14. 		}
    15. 		else
    16. 		{
    17. 			Node* subleft = _node->_right;
    18. 			while (subleft->_left)
    19. 			{
    20. 				subleft = subleft->_left;
    21. 			}
    22.  
    23. 			_node = subleft;
    24. 		}
    25.  
    26. 		return *this;
    27. 	}
    28.  
    29. 	Self operator++(int)
    30. 	{
    31. 		Self tmp(*this);
    32. 		++(*this);
    33.  
    34. 		return tmp;
    35. 	}

    由于begin()，是按照中序的方式访问的，--可以分为两种情况，当左子树不存在为空时，找孩子是祖先的右的那个祖先节点，当左子树存在不为空时，找左子树的最右节点

    以下图红黑树为例：

    假设此时迭代器已经遍历到节点为11的地方：

    当我们要--遍历红黑树时，由于11的左子树不存在为空，往上找孩子是祖先的右的祖先节点，我发现11就是8的右，于是迭代器访问的是节点8的祖先节点，再次--，此时节点8的左子树存在不为空，找左子树的最右节点，此时节点6是1的最右节点，因此找到的节点是节点6，此时，发现已经是在按中序的方式遍历了

    --的迭代器的实现代码如下：

    1.     Self& operator--()
    2. 	{
    3. 		if (_node->_left == nullptr)
    4. 		{
    5. 			// 找祖先里面，孩子是父亲
    6. 			Node* cur = _node;
    7. 			Node* parent = cur->_parent;
    8. 			while (parent && cur == parent->_left)
    9. 			{
    10. 				cur = cur->_parent;
    11. 				parent = parent->_parent;
    12. 			}
    13.  
    14. 			_node = parent;
    15. 		}
    16. 		else
    17. 		{
    18. 			// 左子树的最右节点
    19. 			Node* subRight = _node->_left;
    20. 			while (subRight->_right)
    21. 			{
    22. 				subRight = subRight->_right;
    23. 			}
    24.  
    25. 			_node = subRight;
    26. 		}
    27.  
    28. 		return *this;
    29. 	}
    30.  
    31. 	Self operator--(int)
    32. 	{
    33. 		Self tmp(*this);
    34.  
    35. 		--(*this);
    36.  
    37. 		return tmp;
    38. 	}

    5. operator!=和operator==的实现

    比两个对象中的节点即可

    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. 	}

    至此迭代器的基本实现已完成

    ３. 对RBTree类进行改变

    由于模板参数的改变和迭代器的实现，使RBTree的实现更加完整，需要对RBTree类进行改变。

    1. 改造insert

    首先就是对insert进行改变，有了迭代器的实现，我们应该和库里面的一样，返回的是pair而不是bool，以及在比较的时候应该使用KeyOfT这个仿函数模板参数来接受K，修改完成代码如下：

    1.     pairbool> Insert(const T& data)
    2. 	{
    3. 		// 1、搜索树的规则插入
    4. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    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;
    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->_right;
    22. 			}
    23. 			else if (kot(cur->_data) > kot(data))
    24. 			{
    25. 				parent = cur;
    26. 				cur = cur->_left;
    27. 			}
    28. 			else
    29. 			{
    30. 				return make_pair(iterator(cur), true);
    31. 			}
    32. 		}
    33.  
    34. 		cur = new Node(data);
    35. 		Node* newnode = cur;
    36. 		cur->_col = RED;  
    37. 		if (kot(parent->_data) < kot(data))
    38. 		{
    39. 			parent->_right = cur;
    40. 		}
    41. 		else
    42. 		{
    43. 			parent->_left = cur;
    44. 		}
    45.  
    46. 		cur->_parent = parent;
    47.  
    48. 		// 存在连续红色节点
    49. 		while (parent && parent->_col == RED)
    50. 		{
    51. 			Node* grandfater = parent->_parent;
    52. 			assert(grandfater);
    53.  
    54. 			if (grandfater->_left == parent)
    55. 			{
    56. 				Node* uncle = grandfater->_right;
    57. 				// 情况一：
    58. 				if (uncle && uncle->_col == RED) // 叔叔存在且为红
    59. 				{
    60. 					// 变色
    61. 					parent->_col = uncle->_col = BLACK;
    62. 					grandfater->_col = RED;
    63.  
    64. 					// 继续往上处理
    65. 					cur = grandfater;
    66. 					parent = cur->_parent;
    67. 				}
    68. 				else // 叔叔不存在 或者 叔叔存在且为黑
    69. 				{
    70. 					if (cur == parent->_left) // 单旋
    71. 					{
    72. 						//     g
    73. 						//   p
    74. 						// c
    75. 						RotateR(grandfater);
    76. 						parent->_col = BLACK;
    77. 						grandfater->_col = RED;
    78. 					}
    79. 					else // 双旋
    80. 					{
    81. 						//     g
    82. 						//   p
    83. 						//     c 
    84. 						RotateL(parent);
    85. 						RotateR(grandfater);
    86. 						cur->_col = BLACK;
    87. 						grandfater->_col = RED;
    88. 					}
    89.  
    90. 					break;
    91. 				}
    92. 			}
    93. 			else //(grandfater->_right == parent)
    94. 			{
    95. 				Node* uncle = grandfater->_left;
    96. 				// 情况一：
    97. 				if (uncle && uncle->_col == RED)
    98. 				{
    99. 					// 变色
    100. 					parent->_col = uncle->_col = BLACK;
    101. 					grandfater->_col = RED;
    102.  
    103. 					// 继续往上处理
    104. 					cur = grandfater;
    105. 					parent = cur->_parent;
    106. 				}
    107. 				else
    108. 				{
    109. 					if (cur == parent->_right)
    110. 					{
    111. 						// g
    112. 						//   p
    113. 						//     c 
    114. 						RotateL(grandfater);
    115. 						parent->_col = BLACK;
    116. 						grandfater->_col = RED;
    117. 					}
    118. 					else // 双旋
    119. 					{
    120. 						// g
    121. 						//   p
    122. 						// c
    123. 						RotateR(parent);
    124. 						RotateL(grandfater);
    125. 						cur->_col = BLACK;
    126. 						grandfater->_col = RED;
    127. 					}
    128.  
    129. 					break;
    130. 				}
    131. 			}
    132. 		}
    133.  
    134. 		_root->_col = BLACK;
    135.  
    136. 		return make_pair(iterator(newnode), true);//创建并返回iterator对象
    137. 	}

    相比原来的insert对返回值做了修改，并用KeyOfT仿函数创建对象来接受其中的K，来进行比较

    2. 增加find的实现

    利用KeyOfT提取T中的K来进行比较找想要找的元素，找到返回迭代器元素位置的迭代器否则返回end()，具体代码实现如下：

    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. 	}

    4. 改造后的RBTree树代码展示

    1. enum Colour
    2. {
    3. 	RED,
    4. 	BLACK,
    5. };
    6.  
    7. template<class T>
    8. struct RBTreeNode
    9. {
    10. 	RBTreeNode* _left;
    11. 	RBTreeNode* _right;
    12. 	RBTreeNode* _parent;
    13. 	T _data; // 数据
    14.  
    15. 	Colour _col;
    16.  
    17. 	RBTreeNode(const T& data)
    18. 		:_data(data)
    19. 		, _left(nullptr)
    20. 		, _right(nullptr)
    21. 		, _parent(nullptr)
    22. 		, _col(RED)
    23. 	{}
    24. };
    25.  
    26. template<class T, class Ref, class Ptr>
    27. struct __RBTreeIterator
    28. {
    29. 	typedef RBTreeNode Node;
    30. 	typedef __RBTreeIterator Self;
    31. 	Node* _node;
    32.  
    33. 	__RBTreeIterator(Node* node)
    34. 		:_node(node)
    35. 	{}
    36.  
    37. 	Ref operator*()
    38. 	{
    39. 		return _node->_data;
    40. 	}
    41.  
    42. 	Ptr operator->()
    43. 	{
    44. 		return &_node->_data;
    45. 	}
    46. 	// 休息17:00
    47. 	Self& operator++()
    48. 	{
    49. 		if (_node->_right == nullptr)
    50. 		{
    51. 			// 找祖先里面，孩子是父亲左的那个
    52. 			Node* cur = _node;
    53. 			Node* parent = cur->_parent;
    54. 			while (parent && parent->_right == cur)
    55. 			{
    56. 				cur = cur->_parent;
    57. 				parent = parent->_parent;
    58. 			}
    59.  
    60. 			_node = parent;
    61. 		}
    62. 		else
    63. 		{
    64. 			// 右子树的最左节点
    65. 			Node* subLeft = _node->_right;
    66. 			while (subLeft->_left)
    67. 			{
    68. 				subLeft = subLeft->_left;
    69. 			}
    70.  
    71. 			_node = subLeft;
    72. 		}
    73. 		
    74. 		return *this;
    75. 	}
    76.  
    77. 	Self operator++(int)
    78. 	{
    79. 		Self tmp(*this);
    80. 		
    81. 		++(*this);
    82.  
    83. 		return tmp;
    84. 	}
    85.  
    86. 	Self& operator--()
    87. 	{
    88. 		if (_node->_left == nullptr)
    89. 		{
    90. 			// 找祖先里面，孩子是父亲
    91. 			Node* cur = _node;
    92. 			Node* parent = cur->_parent;
    93. 			while (parent && cur == parent->_left)
    94. 			{
    95. 				cur = cur->_parent;
    96. 				parent = parent->_parent;
    97. 			}
    98.  
    99. 			_node = parent;
    100. 		}
    101. 		else
    102. 		{
    103. 			// 左子树的最右节点
    104. 			Node* subRight = _node->_left;
    105. 			while (subRight->_right)
    106. 			{
    107. 				subRight = subRight->_right;
    108. 			}
    109.  
    110. 			_node = subRight;
    111. 		}
    112.  
    113. 		return *this;
    114. 	}
    115.  
    116. 	Self operator--(int)
    117. 	{
    118. 		Self tmp(*this);
    119.  
    120. 		--(*this);
    121.  
    122. 		return tmp;
    123. 	}
    124.  
    125. 	bool operator!=(const Self& s) const
    126. 	{
    127. 		return _node != s._node;
    128. 	}
    129.  
    130. 	bool operator==(const Self& s) const
    131. 	{
    132. 		return _node == s->_node;
    133. 	}
    134. };
    135.  
    136. // T决定红黑树存什么数据
    137. // set  RBTree
    138. // map  RBTree>
    139. // KeyOfT -> 支持取出T对象中key的仿函数
    140. template<class K, class T, class KeyOfT>
    141. class RBTree
    142. {
    143. 	typedef RBTreeNode Node;
    144. public:
    145. 	typedef __RBTreeIterator iterator;
    146. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    147.  
    148. 	// 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
    149.  
    150. 	iterator Begin()
    151. 	{
    152. 		Node* subLeft = _root;
    153. 		while (subLeft && subLeft->_left)
    154. 		{
    155. 			subLeft = subLeft->_left;
    156. 		}
    157.  
    158. 		return iterator(subLeft);
    159. 	}
    160.  
    161. 	iterator End()
    162. 	{
    163. 		return iterator(nullptr);
    164. 	}
    165.  
    166. 	const_iterator Begin() const
    167. 	{
    168. 		Node* subLeft = _root;
    169. 		while (subLeft && subLeft->_left)
    170. 		{
    171. 			subLeft = subLeft->_left;
    172. 		}
    173.  
    174. 		return const_iterator(subLeft);
    175. 	}
    176.  
    177. 	const_iterator End() const
    178. 	{
    179. 		return const_iterator(nullptr);
    180. 	}
    181.  
    182. 	pairbool> Insert(const T& data)
    183. 	{
    184. 		// 1、搜索树的规则插入
    185. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    186. 		if (_root == nullptr)
    187. 		{
    188. 			_root = new Node(data);
    189. 			_root->_col = BLACK;
    190. 			return make_pair(iterator(_root), true);
    191. 		}
    192.  
    193. 		KeyOfT kot;
    194.  
    195. 		Node* parent = nullptr;
    196. 		Node* cur = _root;
    197. 		while (cur)
    198. 		{
    199. 			if (kot(cur->_data) < kot(data))
    200. 			{
    201. 				parent = cur;
    202. 				cur = cur->_right;
    203. 			}
    204. 			else if (kot(cur->_data) > kot(data))
    205. 			{
    206. 				parent = cur;
    207. 				cur = cur->_left;
    208. 			}
    209. 			else
    210. 			{
    211. 				return make_pair(iterator(cur), true);
    212. 			}
    213. 		}
    214.  
    215. 		cur = new Node(data);
    216. 		Node* newnode = cur;
    217. 		cur->_col = RED;  
    218. 		if (kot(parent->_data) < kot(data))
    219. 		{
    220. 			parent->_right = cur;
    221. 		}
    222. 		else
    223. 		{
    224. 			parent->_left = cur;
    225. 		}
    226.  
    227. 		cur->_parent = parent;
    228.  
    229. 		// 存在连续红色节点
    230. 		while (parent && parent->_col == RED)
    231. 		{
    232. 			Node* grandfater = parent->_parent;
    233. 			assert(grandfater);
    234.  
    235. 			if (grandfater->_left == parent)
    236. 			{
    237. 				Node* uncle = grandfater->_right;
    238. 				// 情况一：
    239. 				if (uncle && uncle->_col == RED) // 叔叔存在且为红
    240. 				{
    241. 					// 变色
    242. 					parent->_col = uncle->_col = BLACK;
    243. 					grandfater->_col = RED;
    244.  
    245. 					// 继续往上处理
    246. 					cur = grandfater;
    247. 					parent = cur->_parent;
    248. 				}
    249. 				else // 叔叔不存在 或者 叔叔存在且为黑
    250. 				{
    251. 					if (cur == parent->_left) // 单旋
    252. 					{
    253. 						//     g
    254. 						//   p
    255. 						// c
    256. 						RotateR(grandfater);
    257. 						parent->_col = BLACK;
    258. 						grandfater->_col = RED;
    259. 					}
    260. 					else // 双旋
    261. 					{
    262. 						//     g
    263. 						//   p
    264. 						//     c 
    265. 						RotateL(parent);
    266. 						RotateR(grandfater);
    267. 						cur->_col = BLACK;
    268. 						grandfater->_col = RED;
    269. 					}
    270.  
    271. 					break;
    272. 				}
    273. 			}
    274. 			else //(grandfater->_right == parent)
    275. 			{
    276. 				Node* uncle = grandfater->_left;
    277. 				// 情况一：
    278. 				if (uncle && uncle->_col == RED)
    279. 				{
    280. 					// 变色
    281. 					parent->_col = uncle->_col = BLACK;
    282. 					grandfater->_col = RED;
    283.  
    284. 					// 继续往上处理
    285. 					cur = grandfater;
    286. 					parent = cur->_parent;
    287. 				}
    288. 				else
    289. 				{
    290. 					if (cur == parent->_right)
    291. 					{
    292. 						// g
    293. 						//   p
    294. 						//     c 
    295. 						RotateL(grandfater);
    296. 						parent->_col = BLACK;
    297. 						grandfater->_col = RED;
    298. 					}
    299. 					else // 双旋
    300. 					{
    301. 						// g
    302. 						//   p
    303. 						// c
    304. 						RotateR(parent);
    305. 						RotateL(grandfater);
    306. 						cur->_col = BLACK;
    307. 						grandfater->_col = RED;
    308. 					}
    309.  
    310. 					break;
    311. 				}
    312. 			}
    313. 		}
    314.  
    315. 		_root->_col = BLACK;
    316.  
    317. 		return make_pair(iterator(newnode), true);
    318. 	}
    319.  
    320. 	void RotateL(Node* parent)
    321. 	{
    322. 		Node* subR = parent->_right;
    323. 		Node* subRL = subR->_left;
    324.  
    325. 		parent->_right = subRL;
    326. 		if (subRL)
    327. 			subRL->_parent = parent;
    328.  
    329. 		Node* ppNode = parent->_parent;
    330.  
    331. 		subR->_left = parent;
    332. 		parent->_parent = subR;
    333.  
    334. 		if (parent == _root)
    335. 		{
    336. 			_root = subR;
    337. 			_root->_parent = nullptr;
    338. 		}
    339. 		else
    340. 		{
    341. 			if (parent == ppNode->_left)
    342. 			{
    343. 				ppNode->_left = subR;
    344. 			}
    345. 			else
    346. 			{
    347. 				ppNode->_right = subR;
    348. 			}
    349.  
    350. 			subR->_parent = ppNode;
    351. 		}
    352. 	}
    353.  
    354. 	void RotateR(Node* parent)
    355. 	{
    356. 		Node* subL = parent->_left;
    357. 		Node* subLR = subL->_right;
    358.  
    359. 		parent->_left = subLR;
    360. 		if (subLR)
    361. 			subLR->_parent = parent;
    362.  
    363. 		Node* ppNode = parent->_parent;
    364.  
    365. 		subL->_right = parent;
    366. 		parent->_parent = subL;
    367.  
    368. 		if (parent == _root)
    369. 		{
    370. 			_root = subL;
    371. 			_root->_parent = nullptr;
    372. 		}
    373. 		else
    374. 		{
    375. 			if (ppNode->_left == parent)
    376. 			{
    377. 				ppNode->_left = subL;
    378. 			}
    379. 			else
    380. 			{
    381. 				ppNode->_right = subL;
    382. 			}
    383. 			subL->_parent = ppNode;
    384. 		}
    385. 	}
    386.  
    387. 	iterator Find(const K& key)
    388. 	{
    389. 		Node* cur = _root;
    390. 		KeyOfT kot;
    391. 		while (cur)
    392. 		{
    393. 			if (kot(cur->_data) < key)
    394. 			{
    395. 				cur = cur->_right;
    396. 			}
    397. 			else if (kot(cur->_data) > key)
    398. 			{
    399. 				cur = cur->_left;
    400. 			}
    401. 			else
    402. 			{
    403. 				return iterator(cur);
    404. 			}
    405. 		}
    406.  
    407. 		return End();
    408. 	}
    409.  
    410. private:
    411. 	Node* _root = nullptr;
    412. };

    二. 封装set

    set的底层结构就是红黑树，因此在set中直接封装一棵红黑树，然后将其接口包装下即可

    由于在RBTree中传了KeyOfT来获取K，因此我们在set中需要实现一个仿函数来获取set的K

    1.     template<class K>
    2. 	class set
    3. 	{
    4. 		//给红黑树获取K
    5. 		struct SetkeyOfT
    6. 		{
    7. 			const K& operator()(const K& key)
    8. 			{
    9. 				return key;
    10. 			}
    11. 		};

    其他都是包装RBTree的接口即可

    注意：

    由于set的Key是不能改变的，所以set的iterator应该用const_iterator包装。

    但是会进一步导致insert函数在返回时，由于RBTree的iterator里的参数没有被const修饰是普通迭代器，但是set的iterator是const_iterator，就会出现iterator向const_iterator的转化，这是两个封装后毫无关系的类型，无法直接转化，因此我们需要先提取出来返回值稍作修改后重新封装，因此insert应该做出如下改造：

    1. pairbool> insert(const K& key)
    2. {
    3.     //pair::iterator, bool> ret = _t.Insert(key);
    4. 	auto ret = _t.Insert(key);
    5. 	return pairbool>(iterator(ret.first._node), ret.second);
    6. }

    注意：

    这里和list实现迭代器一样，当我们typedef迭代器时，会出现内嵌类型的问题，需要使用到typename关键字

    set具体封装的实现代码：

    1. #include "RBTree.h"
    2.  
    3. namespace mystl
    4. {
    5. 	template<class K>
    6. 	class set
    7. 	{
    8. 		//给红黑树获取K
    9. 		struct SetkeyOfT
    10. 		{
    11. 			const K& operator()(const K& key)
    12. 			{
    13. 				return key;
    14. 			}
    15. 		};
    16. 	public:
    17.  
    18. 		typedef typename RBTree::const_iterator iterator;
    19. 		typedef typename RBTree::const_iterator const_iterator;
    20.  
    21. 		//set不能修改，只提供const版本
    22. 		iterator begin() const
    23. 		{
    24. 			return _t.Begin();
    25. 		}
    26.  
    27. 		iterator end() const
    28. 		{
    29. 			return _t.End();
    30. 		}
    31.  
    32. 		pairbool> insert(const K& key)
    33. 		{
    34. 			//pair::iterator, bool> ret = _t.Insert(key);
    35. 			auto ret = _t.Insert(key);
    36. 			return pairbool>(iterator(ret.first._node), ret.second);
    37. 		}
    38.  
    39. 		iterator find(const K& key)
    40. 		{
    41. 			return _t.find(key);
    42. 		}
    43.  
    44. 	private:
    45. 		RBTree _t;
    46. 	};
    47. }

    三. 封装map

    这里需要的注意事项和set，唯一不同的是这里insert没有set的问题，因为map的iterator就是RBTree的普通迭代器封装的，因map的V是可以更改的，map和set的K是不能更改的，所以map的普通迭代器应该封装成普通的迭代器供V改变，因此，insert可以直接返回封装的insert的返回值。

    map实现了operator[]，这里也可以实现，直接封装RBTree的insert，返回值是RBTree返回值的V的引用供修改即可

    实现代码如下：

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

    其他直接封装RBTree的接口即可，j具体实现代码如下：
     

    1. #include "RBTree.h"
    2.  
    3. namespace mystl
    4. {
    5. 	template<class K, class V>
    6. 	class map
    7. 	{
    8. 		//给红黑树获取K
    9. 		struct MapkeyOfT
    10. 		{
    11. 			const K& operator()(const pair& kv)
    12. 			{
    13. 				return kv.first;
    14. 			}
    15. 		};
    16.  
    17. 	public:
    18.  
    19. 		typedef typename RBTree, MapkeyOfT>::iterator iterator;
    20. 		typedef typename RBTree, MapkeyOfT>::const_iterator const_iterator;
    21.  
    22. 		//map可以修改都提供
    23. 		iterator begin()
    24. 		{
    25. 			return _t.Begin();
    26. 		}
    27.  
    28. 		iterator end()
    29. 		{
    30. 			return _t.End();
    31. 		}
    32.  
    33. 		pairbool> insert(const pair& kv)
    34. 		{
    35. 			return _t.Insert(kv);
    36. 		}
    37.  
    38. 		iterator find(const K& key)
    39. 		{
    40. 			return _t.find(key);
    41. 		}
    42.  
    43. 		V& operator[](const K& key)
    44. 		{
    45. 			pairbool> ret = insert(make_pair(key, V()));
    46.  
    47. 			return ret.first->second;
    48. 		}
    49.  
    50. 	private:
    51. 		RBTree, MapkeyOfT>  _t;
    52. 	};
    53. }
  • 相关阅读:
    概念解析 | 网络安全数字孪生(Digital Twin of Cyber Security, DTCS)技术
    【面试经典150 | 矩阵】生命游戏
    无人机实践：DJI A3 飞控---使用
    神经网络和深度学习-梯度下降Gradient Descent
    【智能家居项目】裸机版本——设备子系统(LED && Display && 风扇)
    找不到msvcr120.dll无法执行代码?教你6种方法快速解决问题
    基于Springboot外卖系统11：菜品新增类别+类别信息分页查询
    数据分析的流程是啥样？
    软件测试面试题库和答案解析
    图论第6天
  • 原文地址：https://blog.csdn.net/Britney_dark/article/details/127944455