• C++精通之路：红黑树的应用（模拟实现map/set）

    文章目录

    很多小伙伴为了刷题发愁
    今天为大家推荐一款刷题神奇哦：刷题面试神器牛客
    各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo全场面试官

    一：红黑树的迭代器

    • 需要注意的是：
    1. 迭代器本质上是指针的一个封装的类，其底层就是指针；好处是可以方便遍历，是数据结构的底层实现与用户透明
    2. 对于string,vector,list等容器，其本身的结构上是比较简单的，迭代器的实现也很简单；但是对于二叉树结构的红黑树来说需要考虑很多的问题

    1.begin()与end()

    STL明确规定，begin()与end()代表的是一段前闭后开的区间

    对红黑树进行中序遍历后，可以得到一个有序的序列，因此begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置即nullptr

    • 如图：
      在这里插入图片描述

    2.operator++()与operator–()

    • ++逻辑的实现：
    1. 因为红黑树的中序是有序的，所以++是找到该节点在中序中的下一个节点
    2. 因为中序是左中右，所以我们可以分为右子树存在和不存在来讨论下一个节点是谁
    1. 当右子树存在时，右子树的最左节点即是下一个节点
    2. 当右子树不存在时，我们需要向上寻找，因为中序是左中右的，所以该子树已经被遍历完了，则++操作后应该在该结点的祖先结点中找到孩子不在父亲右的祖先
    • –的逻辑是一样的

    代码实现：

    • operator++()
    Self& operator++()
{
    if (_node->_right)//右子节点存在
    {
        //找到右子树中最左节点
        Node* cur = _node->_right;
        while (cur->_left)
        {
            cur = cur->_left;
        }
        _node = cur;
    }
    else//右子节点不存在，向上找
    {
        Node* cur = _node;//记录走过的节点
        Node* parent = _node->_parent;
        while (parent && parent->_right == cur)
        {
            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
    • operator–()：
    Self& operator--()
{
    if (_node->_left)//左子节点存在
    {
        //找左子树中的最右节点
        Node* cur = _node->_left;
        while (cur->_right)
        {
            cur = cur->_right;
        }
        _node = cur;
    }
    else//左子节点不存在
    {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent && parent->_left == cur)
        {
            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

    反向迭代器适配器

    因为反向迭代器与正向迭代器在原理实现中是相同的，只是方向反了而已
    所以我们可以用正向迭代器来封装出反向迭代器，在正向迭代器的基础上，对其接口进行封装达到反向迭代器的效果

    • 正向迭代器实现代码：
    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& it)const
	{
		return _node == it._node;
	}

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

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent && parent->_left == cur)
			{
				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
    • 反向迭代器实现代码：
    //适配器构造反向迭代器
template<class Iterator>
struct ReverseIterator
{
	//类型未实例化，无法取出里面的类型，此时需要使用typename：告诉编译器等实例化后再到类里面找对应的类型
	typedef typename Iterator::reference Ref;
	typedef typename Iterator::pointer Ptr;
	typedef ReverseIterator<Iterator> Self;

	Iterator _it;

	ReverseIterator(Iterator it)
		:_it(it)
	{}
    
	//在正向迭代器接口上进行封装复用   
	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return _it.operator->();
	}

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

	bool operator!= (const Self& it)const//两个const
	{
		return _it != it._it;
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self& operator--()
	{
		++_it;
		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

    二：改造红黑树来模拟实现map/set

    因为set是K模型的容器，而map是KV模型的容器.所以要用红黑树来模拟实现这两个容器，需要添加一些东西使得其能适配两者，添加和改变的东西如下：

    1. 节点的改变：

    对于红黑树的节点我们需要节点对于set来说储存key，对于map来说储存key-value键值对，所以这里我们就直接让节点类型的阈值类型为T，用来控制储存类型

    • 代码的实现：
    template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;//T可以是key也可以是pair
	Colour _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

    2. 主体的改变

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


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

    K是用来比较的类型，T是用来存储的类型

    • 这里就体现了对map和set的兼容。
    • 当为map时，传进来的T为pirpair
    • 当为set时，传进来的T为K
    • 达到了存储不同数据类型的目的

    3. 添加仿函数来适配数据间的比较

    在删除添加时，我们要进行节点中数据的比较，
    当为map时，pirpair与Kl类型无法比较时，这里就需要仿函数来帮助我们适配

    • 对于不同容器我们需要不同的仿函数类型，由此在红黑树的模板列表中还需要一个模板类型参数，灵活控制传入的仿函数类型

    仿函数的本质是创造一个类，通过operator（）的重载来实现的，与函数重载类似，但在模板内，就只能使用仿函数来实现了。

    • 红黑树框架：
    template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
	//...
private:
	Node* _root;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • map实现框架：
    namespace cole
{
	template<class K, class V>
	class map
	{
		struct MapOfKey
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		//...
	private:
		RBTree<K, pair<const K, V>, MapOfKey> _t;
	};
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • set实现框架：
    namespace cole
{
	template<class K>
	class set
	{
		struct SetOfKey
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//...
	private:
		RBTree<K, K, SetOfKey> _t;
	};
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 仿函数使用示例：
      Node* Find(const K& key)
      {
      KeyOfT kot;
      Node* cur = _root;
      while (cur)
      {
      if (kot(cur->_kv.first) > key)
      {
      cur = cur->_left;
      }
      else if (kot(cur->_kv.first) < key)
      {
      cur = cur->_right;
      }
      else
      {
      return cur;
      }
      }
      return nullptr;
      }

    三：红黑树的封装与适配

    • 代码：
    //颜色
enum Colour
{
	RED,
	BLACK,
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;//T可以是key也可以是pair
	Colour _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 _TreeIterator<T,const T&, const T*> const_iterator;
	typedef ReverseIterator<iterator> reverse_iterator;
	typedef ReverseIterator<const_iterator> reverse_const_iterator;

	RBTree()
		:_root(nullptr)
	{}

	~RBTree()
	{
		_Destory(_root);
	}

	iterator begin()
	{
		Node* cur = _root;
		while (cur&&cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

	reverse_iterator rbegin()
	{
		Node* cur = _root;
		while (cur&&cur->_right)
		{
			cur = cur->_right;
		}
		return reverse_iterator(iterator(cur));
	}

	reverse_iterator rend()
	{
		return reverse_iterator(iterator(nullptr));
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	Node* Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_kv.first) > key)
			{
				cur = cur->_left;
			}
			else if (kot(cur->_kv.first) < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	pair<iterator, bool> Insert(const T& data)
	{
		//空树的情况
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		KeyOfT kot;
		//查找位置插入节点
		Node* cur = _root, * parent = _root;
		while (cur)
		{
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		//创建链接节点
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//父节点存在且为红，则需要调整（不能存在连续的红色节点）
		while (parent && parent->_col == RED)
		{
			//此时当前节点一定有祖父节点
			Node* granparent = parent->_parent;
			//具体调整情况主要看叔叔节点
			//分左右讨论
			if (parent == granparent->_left)
			{
				Node* uncle = granparent->_right;
				//情况1：叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//修改颜色，继续向上检查
					granparent->_col = RED;
					parent->_col = uncle->_col = BLACK;

					cur = granparent;
					parent = cur->_parent;
				}
				else//情况2和3：叔叔节点不存在 或者存在且为黑
				{
					//单旋(三代节点为斜线)+变色
					if (cur == parent->_left)
					{
						RotateR(granparent);

						granparent->_col = RED;
						parent->_col = BLACK;
					}
					else//双旋(三代节点为折线)+变色
					{
						RotateL(parent);
						RotateR(granparent);

						cur->_col = BLACK;
						granparent->_col = RED;
					}
					//旋转后不需再向上调整了
					break;
				}
			}
			else//parent=grandparent->right
			{
				Node* uncle = granparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					granparent->_col = RED;

					cur = granparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(granparent);

						parent->_col = BLACK;
						granparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(granparent);

						cur->_col = BLACK;
						granparent->_col = RED;
					}
					break;
				}
			}
		}

		//确保根节点为黑
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	bool IsRBTree()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根节点为红色" << endl;
			return false;
		}

		int Blacknum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				Blacknum++;
			cur = cur->_left;
		}

		int i = 0;
		return _IsRBTree(_root, Blacknum, i);
	}

private:
    void _Destory(Node*& root)
	{
		if (root == nullptr)
			return;

		_Destory(root->_left);
		_Destory(root->_right);

		delete root;
		root = nullptr;
	}
    
	bool _IsRBTree(Node* root, int blacknum, int count)
	{
		if (root == nullptr)
		{
			if (blacknum == count)
				return true;
			cout << "各路径上黑色节点个数不同" << endl;
			return false;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
			count++;

		return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentP = parent->_parent;


		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = parentP;
			if (parentP->_left == parent)
			{
				parentP->_left = subR;
			}
			else
			{
				parentP->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentP = parent->_parent;


		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = parentP;
			if (parentP->_left == parent)
			{
				parentP->_left = subL;
			}
			else
			{
				parentP->_right = subL;
			}
		}
	}

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
    • 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
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355

    四：map的封装和模拟实现

    • 代码：
    namespace ymhh
{
	template<class K, class V>
	class map
	{
		struct MapOfKey
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapOfKey>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapOfKey>::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()));
			return ret.first->second;
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

	private:
		RBTree<K, pair<const K, V>, MapOfKey> _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

    五： set的封装和模拟实现

    • 代码：
    namespace ymhh
{
	template<class K>
	class set
	{
		struct SetOfKey
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K,K, SetOfKey>::iterator iterator;
		typedef typename RBTree<K,K, SetOfKey>::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);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

	private:
		RBTree<K, K, SetOfKey> _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

    总结

    因为红黑树的增删查改都是O（logN）,所以用红黑树实现的map/set的增删查改也是O（logN），是个非常优秀的容器

  • 相关阅读:
    Request方法的使用、JSON文件介绍、Python中的JSON数据以及获取到的JSON数据的解析。
    [工业互联-4]：工业有线互联总线之IO-Link
    Docker中使用Tomcat并部署war工程
    问题：anaconda的bin和envs目录莫名奇妙消失！
    海康摄像机取流RTSP地址规则说明
    【C语言】联合（共用体）
    王学岗生成泛型的简易Builder
    【无标题】
    16、架构-可观测性-事件日志详细解析
    Java核心篇，二十三种设计模式（二十二），行为型——模板方法
  • 原文地址：https://blog.csdn.net/yin_ming_hui/article/details/126049293