• 红黑树同时封装实现 map 和 set——红黑树の华丽二重奏

    传统艺能😎

    小编是双非本科大一菜鸟不赘述，欢迎各位指点江山（期待~）（QQ：1319365055）
    此前博客点我！点我！请搜索博主 【知晓天空之蓝】

    🎉🎉非科班转码社区诚邀您入驻🎉🎉
    小伙伴们，打码路上一路向北，彼岸之前皆是疾苦
    一个人的单打独斗不如一群人的砥砺前行
    这是和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
    社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
    直达： 社区链接点我

    在这里插入图片描述

    我们知道 map 和 set 的底层原理都是红黑树，在 STL 源码中也是清晰可见的，因此这里尝试使用红黑树进行原始的溯源封装来深入了解
    map 和 set 的底层原理。

    模板参数适配🤔

    虽然 set 参数只有 key，但是介于 map 除了 key 还有 value，因此这里我们依然使用红黑树的 KV 模型，以上一篇的红黑树源码为基础：

    enum Colour
{
	RED,
	BLACK
};

//结点定义
template<class K, class V>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	//存储的键值对
	pair<K, V> _kv;

	//结点的颜色
	int _col; //红/黑

	//构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

//红黑树的实现
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//构造函数
	RBTree()
		:_root(nullptr)
	{}

	//拷贝构造
	RBTree(const RBTree<K, V>& t)
	{
		_root = _Copy(t._root, nullptr);
	}

	//赋值运算符重载
	RBTree<K, V>& operator=(RBTree<K, V> t)
	{
		swap(_root, t._root);//借助临时变量实现深拷贝交换
		return *this;
	}

	//析构函数
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	//查找函数
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_kv.first) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (key > cur->_kv.first) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了目标结点
			{
				return cur; //返回该结点
			}
		}
		return nullptr; //查找失败
	}

	//插入函数
	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
		{
			_root = new Node(kv);
			_root->_col = BLACK; //根结点必须是黑色
			return make_pair(_root, true); //插入成功
		}
		//1、按二叉搜索树的插入方法，找到待插入位置
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
			{
				//往该结点的左子树走
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
			{
				//往该结点的右子树走
				parent = cur;
				cur = cur->_right;
			}
			else //待插入结点的key值等于当前结点的key值
			{
				return make_pair(cur, false); //插入失败
			}
		}

		//2、将待插入结点插入到树中
		cur = new Node(kv); //根据所给值构造一个结点
		Node* newnode = cur; //记录新插入的结点（便于后序返回）
		if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
		{
			//插入到parent的左边
			parent->_left = cur;
			cur->_parent = parent;
		}
		else //新结点的key值大于parent的key值
		{
			//插入到parent的右边
			parent->_right = cur;
			cur->_parent = parent;
		}

		//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
		while (parent&&parent->_col == RED)
		{
			Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
			if (parent == grandfather->_left) //parent是grandfather的左孩子
			{
				Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
				if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
				{
					//颜色调整
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况2+情况3：uncle不存在 + uncle存在且为黑
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather); //右单旋

						//颜色调整
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else //cur == parent->_right
					{
						RotateLR(grandfather); //左右双旋

						//颜色调整
						grandfather->_col = RED;
						cur->_col = BLACK;
					}
					break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
				}
			}
			else //parent是grandfather的右孩子
			{
				Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
				if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
				{
					//颜色调整
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else //情况2+情况3：uncle不存在 + uncle存在且为黑
				{
					if (cur == parent->_left)
					{
						RotateRL(grandfather); //右左双旋

						//颜色调整
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else //cur == parent->_right
					{
						RotateL(grandfather); //左单旋

						//颜色调整
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
				}
			}
		}
		_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
		return make_pair(newnode, true); //插入成功
	}
	
private:
	//拷贝树
	Node* _Copy(Node* root, Node* parent)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copyNode = new Node(root->_data);
		copyNode->_parent = parent;
		copyNode->_left = _Copy(root->_left, copyNode);
		copyNode->_right = _Copy(root->_right, copyNode);
		return copyNode;
	}

	//析构函数子函数
	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentParent = parent->_parent;

		//建立subRL与parent之间的联系
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//建立parent与subR之间的联系
		subR->_left = parent;
		parent->_parent = subR;

		//建立subR与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentParent = parent->_parent;

		//建立subLR与parent之间的联系
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//建立parent与subL之间的联系
		subL->_right = parent;
		parent->_parent = subL;

		//建立subL与parentParent之间的联系
		if (parentParent == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

	Node* _root; //红黑树的根结点
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324

    红黑树对两者进行适配的话有点差强人意，我们不妨好好利用红黑树的 KV 模型：

    template<class Key,class Value>
class RBTree

    • 1
    • 2

    对于 set 只有一个 key 我们可以将 kv 同时化为 set 的 key，stl 源码的底层表达出来就是：

    typedef Key  key_type;
typedef Key  value_type;

    • 1
    • 2

    所以 set 定义出来就是：

    template<class K>
class set
{
  public:
	  //...
  private:
	  RBTree<K, K> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    而 map 里面也是一个 KV 模型使用键值对，因此我们不妨将 v 用来表示键值对 pair，底层表达出来就是：

    typedef Key  key_type;
typedef pair<const Key,T> value_type;

    • 1
    • 2

    所以 map 定义出来就是：

    template<class K, class V>
class map
{
  public:
	   //...
  private:
	   RBTree<K, pair<K, V>> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    既然 pair 里面也有 Key，那为什么不能用 map 的封装方式代替 set 呢？

    这是比较核心的问题，主观上这样是没有问题的，但是要注意的是红黑树的第一个参数他一定不能省略，对于 set 倒是无关痛痒，两个 key 少一个还能活，但是 map 不行，map 里面的某些接口是只能通过调用 pair ，而某些接口只能通过调用 key，比如 find 、erase

    数据的存储🤔

    底层红黑树包含 KT 两个参数，因为红黑树上层容器的不同，KT 所代表的具体意义也是不同的

    对于 set 都是 key，所以底层红黑树中的 KT 都是一样的，但是对于 map 红黑树就只能存储 T 了，又因为底层红黑树并不知道上层容器到底是什么，无法确定的情况下红黑树节点中直接存储 T 就行了。

    ==set：（RBTree _t;） + map ：（RBTree> _t;） ==

    template<class K,class T>
class RBTree
{
   typedef RBTreeNode(T) Node;
public:
   //……
private:
   Node* _root;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    如果是 set 的话 T 可以是 Key ，如果是 map 的话 T 就是 pair，所以我们进行糅合直接使用 T 就行了，最后得到既能实现 map 也能实现 set 的红黑树节点定义：

    template<class T>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储的数据
	T _data;

	//结点的颜色
	int _col; //红/黑

	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    仿函数的支持🤔

    T 在是 key 时操作都相对简单，但是如果此时 T 是键值对 pair ，如果需要进行大小比较等操作又该怎么办呢？如何获取键值对的值优势一门学问。

    很明显此时 pair 里面不就有一个 Key 吗，我们直接就地取材把他取出来即可，这时候就需要上层容器 map 提供一个仿函数来获取这个 Key ，我们就相当于直接使用仿函数在比较大小

    首先仿函数是个啥？

    仿函数，就是使一个类的使用看上去像一个函数。其实就是在类中实现一个 operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

    template<class K, class V>
class map
{
	//内部类定义仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值 Key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t; //加上仿函数
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    同时 map 有了 set 也需要搞一个，你可能会说 set 不都是 Key 吗，现成的为什么还需要仿函数呢？其实这个仿函数还是必需的，如果说容器是一瓶好酒，那么仿函数就是开瓶器。

    KeyOfT kot; //比较函数
//……
if(kot(cur->_data) < kot(data));//map与set的值进行比较

    • 1
    • 2
    • 3

    同理，这里我们比较肯定是用上面函数比较，但是好酒和好酒比较，map 有杯子装了，那 set 总不能手捧着喝吧，所以我们为了统一比较所以 set 也使用仿函数机制：

    template<class K>
class set
{
	//内部类定义仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值Key
		{
			return key;
		}
	};
public:
	//...
private:
	RBTree<K, K, SetKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    在这里插入图片描述
    这样一来，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较，下面以红黑树的查找函数为例:

    iterator Find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;
	while (cur)
	{
		if (key < kot(cur->_data))
		{
			cur = cur->_left; //key值小于该结点在左子树中查找
		}
		else if (key > kot(cur->_data))
		{
			cur = cur->_right; //key值大于该结点在右子树中查找
		}
		else 
		{
			return iterator(cur); //查找成功
		}
	}
	return end(); 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    迭代器实现🤔

    正向迭代器🎉

    红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是结点的指针！

    template<class T, class Ref, class Ptr>//自义定，引用，指针类型
struct __TreeIterator
{
	typedef RBTreeNode<T> Node; //结点的类型
	typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器的类型

	Node* _node; //正向迭代器所封装结点的指针
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这样我们就可以构造出一个正向迭代器。

    class __TreeIterator(Node* _node)
      :_node(node); //根据所给结点指针构造一个正向迭代器
    {}

    • 1
    • 2
    • 3

    既然构造出了迭代器，那么必要的重载就必须写出来，比如解引用操作符：

    Ref operator*()
{
	return _node->_data; //返回结点数据的引用
}

    • 1
    • 2
    • 3
    • 4

    以及成员访问操作符 ->：

    Ptr operator->()
{
	return &_node->_data; //返回结点数据的指针
}

    • 1
    • 2
    • 3
    • 4

    != 和 == 运算符

    bool operator!=(const Self& s) const
{
	return _node != s._node; //判断是否不是同一个节点
}

bool operator==(const Self& s) const
{
	return _node == s._node; //判断是否是同一个节点
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    而真正令人头大的，其实是 ++ 和 – 运算符的重载，注意使中序遍历的 ++，–。

    我们就以前置 ++ 为例，++ 逻辑就两种：

    1. 如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
    2. 如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子在祖先左的祖先
    Self operator++()
{
	if (_node->_right) //右子树不为空
	{
		//找右子树中最左结点
		Node* left = _node->_right;
		while (left->_left)
		{
			left = left->_left;
		}
		_node = left; 
	else //结点的右子树为空
	{
		//寻找孩子不在父亲右的祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;//向上查找
		}
		_node = parent;
	}
	return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    同理， – 的逻辑是一样的：

    1. 如果当前结点的左子树不为空，则–操作后应该找到其左子树当中的最右结点
    2. 如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子在祖先右的祖先
    Self operator--()
{
	if (_node->_left) //结点的左子树不为空
	{
		//找左子树中的最右结点
		Node* right = _node->_left;
		while (right->_right)
		{
			right = right->_right;
		}
		_node = right;
	}
	else //结点的左子树为空
	{
		//寻找孩子不在父亲左的祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    我们实现迭代器会将迭代器类型进行 typedef 方便调用，当然记得要在 public 域里进行调用 typedef。完事了不要忘了迭代器还有两个成员函数 begin 和 end ；begin 返回中序序列当中第一个结点的正向迭代器，即起始结点，end 返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器（暴力粗糙处理）：

    template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; //结点的类型
public:
	typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器
	
	iterator begin()
	{
		//寻找最左结点
		Node* left = _root;
		while (left&&left->_left)
		{
			left = left->_left;
		}
		//返回最左结点的正向迭代器
		return iterator(left);
	}
	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器
		return iterator(nullptr);
	}
private:
	Node* _root; //红黑树的根结点
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    之所以我说直接用空指针构造一个正向迭代器是暴力粗糙的处理，实际上这样实现的迭代器是有残次品，因为我们对 end() 位置的正向迭代器进行 – 操作后，理应得到最后一个结点的正向迭代器，但我们 end() 是直接返回由 nullptr 构造的正向迭代器，因此上述代码无法完成此操作。

    所以我们不妨看看 C++ STL 库的实现逻辑：

    在这里插入图片描述

    库里面是采用了类似双向链表的处理，给整个红黑树造了一个哨兵位节点，该节点左边指向最小的最左节点，右边指向最大的右节点，同时还有一个非常 bug 的设计就是这里哨兵位节点 header 的红黑树头结点之间的 parent 相互指向，也就是 header->parent = BSTree_node ,BSTree_node->parent = header

    此时 begin（） 的实现就直接用头结点的左孩子构造一个正向迭代器即可，同样的，如果此时需要 ==rbegin（）==就用头结点的右孩子构造一个反向迭代器，严谨的过程是先构造正向迭代器，再用正向迭代器构造反向迭代器，end（） 和 rend（） 此时就不需要什么 nullptr 了，直接有头结点（哨兵位）进行迭代器构造即可，这样就能完成一个逻辑完整的迭代器了。

    反向迭代器🎉

    上面也说了，反向迭代器的严谨构造过程是用正向迭代器进行封装，我们可以将反向迭代器视为一个迭代器适配器。

    反向迭代器中理所当然的就只有一个成员变量就是正向迭代器：

    template<class Iterator>//迭代器适配器
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self; //反向迭代器
	typedef typename Iterator::reference Ref; //指针的引用
	typedef typename Iterator::pointer Ptr; //结点指针

	Iterator _it; //反向迭代器封装的正向迭代器

	//构造函数
	ReverseIterator(Iterator it)
		:_it(it) //根据所给正向迭代器构造一个反向迭代器
	{}

	Ref operator*()
	{
		return *_it; //调用正向迭代器的operator*返回引用
	}
	
	Ptr operator->()
	{
		return _it.operator->(); //调用正向迭代器的operator->返回指针
	}

	Self& operator++() //前置++
	{
		--_it; //调用正向迭代器的前置--
		return *this;
	}
	//前置--
	Self& operator--()
	{
		++_it; //调用正向迭代器的前置++
		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _it != s._it; 
	}
	bool operator==(const Self& s) const
	{
		return _it == s._it; 
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    为了让反向迭代器能通过正向迭代器获取到结点的引用类型和结点的指针类型，我们需要在正向迭代器中添加 typedef ，因为此时反向迭代器模板参数只有正向迭代器，他压根儿不知道什么引用类型和指针类型，所以还得我们自己动动手：

    template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef Ref reference; //引用
	typedef Ptr pointer; //指针
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    完成后也需要再次在红黑树中对 rbegin 和 rend 成员进行 typedef 并实现：rbegin（）返回最右节点的反向迭代器，rend 返回头结点的前一个节点的反向迭代器，这里也是用 nullptr 直接构造（不严谨），根据上面正向迭代器的实现，我们还是加入哨兵位节点来优化，不赘述。

    set 的实现🤔

    基本操作都倒腾出来了，set 就是 easy case，接口实现直接照搬红黑树的现成，还要将 find 和 insert 返回的指针改成迭代器即可：

    template<class K>
class set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值Key
		{
			return key;
		}
	};
public:
	typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //正向迭代器
	typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器

	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}

	reverse_iterator rbegin()
	{
		return _t.rbegin();
	}
	reverse_iterator rend()
	{
		return _t.rend();
	}

	//插入
	pair<iterator, bool> insert(const K& key)
	{
		return _t.Insert(key);
	}
	//删除
	void erase(const K& key)
	{
		_t.Erase(key);
	}
	//查找
	iterator find(const K& key)
	{
		return _t.Find(key);
	}
private:
	RBTree<K, K, SetKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    map 的实现🤔

    map 也和 set 同理，复用红黑树的底层接口实现，此外还需要实现 [] 运算符的重载：

    template<class K, class V>
class map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
		{
			return kv.first;
		}
	};
public:
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
	
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	
	reverse_iterator rbegin()
	{
		return _t.rbegin();
	}
	reverse_iterator rend()
	{
		return _t.rend();
	}

	//插入
	pair<iterator, bool> insert(const pair<const K, V>& kv)
	{
		return _t.Insert(kv);
	}
	//[]运算符重载
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));
		iterator it = ret.first;
		return it->second;
	}
	//删除
	void erase(const K& key)
	{
		_t.Erase(key);
	}
	//查找
	iterator find(const K& key)
	{
		return _t.Find(key);
	}
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    完整代码🤔

    红黑树

    enum Colour
{
	RED,
	BLACK
};

//红黑树结点的定义
template<class T>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储的数据
	T _data;

	//结点的颜色
	int _col; //红/黑

	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};
//红黑树的实现
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node; //结点的类型
public:
	typedef __TreeIterator<T, T&, T*> iterator; //正向迭代器
	typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器

	reverse_iterator rbegin()
	{
		//寻找最右结点
		Node* right = _root;
		while (right&&right->_right)
		{
			right = right->_right;
		}
		//返回最右结点的反向迭代器
		return reverse_iterator(iterator(right));
	}
	reverse_iterator rend()
	{
		//返回由nullptr构造得到的反向迭代器（不严谨）
		return reverse_iterator(iterator(nullptr));
	}

	iterator begin()
	{
		//寻找最左结点
		Node* left = _root;
		while (left&&left->_left)
		{
			left = left->_left;
		}
		//返回最左结点的正向迭代器
		return iterator(left);
	}
	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器（不严谨）
		return iterator(nullptr);
	}
	//构造函数
	RBTree()
		:_root(nullptr)
	{}

	//拷贝构造
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = _Copy(t._root, nullptr);
	}

	//赋值运算符重载（现代写法）
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this; //支持连续赋值
	}

	//析构函数
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	//查找函数
	iterator Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			if (key < kot(cur->_data)) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (key > kot(cur->_data)) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了目标结点
			{
				return iterator(cur); //返回该结点
			}
		}
		return end(); //查找失败
	}

	//后续省略插入函数


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122

    正向迭代器

    template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef Ref reference; //引用
	typedef Ptr pointer; //指针

	typedef RBTreeNode<T> Node; //结点类型
	typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器类型

	Node* _node; //正向迭代器封装的指针

	__TreeIterator(Node* node)
		:_node(node) //构造正向迭代器
	{}

	Ref operator*()
	{
		return _node->_data; //返回引用
	}
	
	Ptr operator->()
	{
		return &_node->_data; //返回指针
	}
	
	bool operator!=(const Self& s) const
	{
		return _node != s._node; 
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node; 
	}

	//前置++
	Self operator++()
	{
		if (_node->_right) //结点的右子树不为空
		{
			//寻找该结点右子树当中的最左结点
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left; //++后变为该结点
		}
		else //结点的右子树为空
		{
			//寻找孩子在z右的祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent&&cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent; //++后变为该结点
		}
		return *this;
	}

	//前置--
	Self operator--()
	{
		if (_node->_left) //结点的左子树不为空
		{
			//寻找该结点左子树当中的最右结点
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right; //--后变为该结点
		}
		else //结点的左子树为空
		{
			//寻找孩子不在父亲左的祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent&&cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent; //--后变为该结点
		}
		return *this;
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    反向迭代器

    template<class Iterator>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self; //反向迭代器类型
	typedef typename Iterator::reference Ref; //引用
	typedef typename Iterator::pointer Ptr; //指针

	Iterator _it; //反向迭代器封装的正向迭代器

	ReverseIterator(Iterator it)
		:_it(it) //根据正向迭代器构造反向迭代器
	{}

	Ref operator*()
	{
		return *_it; //调用正向迭代器的operator*返回引用
	}
	Ptr operator->()
	{
		return _it.operator->(); //调用正向迭代器的operator->返回指针
	}

	//前置++
	Self& operator++()
	{
		--_it; //调用正向迭代器的前置--
		return *this;
	}
	//前置--
	Self& operator--()
	{
		++_it; //调用正向迭代器的前置++
		return *this;
	}

	bool operator!=(const Self& s) const
	{
		return _it != s._it; 
	}
	bool operator==(const Self& s) const
	{
		return _it == s._it; 
	}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    set 和 map 是上面实现的代码，没有改动这里就不占篇幅了。aqa 芭蕾 eqe 亏内，代表着开心代表着快乐，ok 了家人们！

  • 相关阅读:
    JSD-2204-HTML-CSS-Day02
    电力通信与泛在电力物联网技术的应用与发展-安科瑞黄安南
    【VMware/Linux】虚拟机根目录扩容
    comfyui安装指南及animaldiff使用
    vue3 to使用(五)
    Android 获取版本号
    您的企业内容管理（ECM）系统对敏感信息的保护程度如何？
    sqlibs安装及复现
    【论文精读】VOYAGER: An Open-Ended Embodied Agent with Large Language Models
    Typescript基本类型---下篇
  • 原文地址：https://blog.csdn.net/qq_61500888/article/details/126749816