• 【C++】set & map 的底层封装


    在了解底层封装之前除了对set和map的使用情况要有一定了解,还需要先学习一下二叉搜索树,AVL树,红黑树这些数据结构。
    【C++】二叉搜索树
    【C++】AVL树 & 红黑树

    RBTree.h

    enum Colour
    {
    	RED,
    	BLACK
    };
    
    template<class T>
    class RBTreeNode
    {
    public:
    	RBTreeNode(const T& data)
    		: _data(data)
    		, _left(nullptr)
    		, _right(nullptr)
    		, _parent(nullptr)
    	{}
    	
    	T _data;
    	RBTreeNode<T>* _left;
    	RBTreeNode<T>* _right;
    	RBTreeNode<T>* _parent;
    	Colour _col;
    };
    
    template<class T, class Ref, class Ptr>
    // 红黑树的迭代器实现
    class __RBTreeIterator
    {
    public:
    	typedef RBTreeNode<T> Node;
    	typedef __RBTreeIterator<T, Ref, Ptr> Self;
    public:
    	__RBTreeIterator(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
    		{
    			// ++就是找不是其右孩子的祖先
    			Node* parent = _node->_parent;
    			Node* cur = _node;
    			while (parent && parent->_right == cur)
    			{
    				cur = 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* parent = _node->_parent;
    			Node* cur = _node;
    			while (parent && parent->_left == cur)
    			{
    				cur = cur->_parent;
    				parent = parent->_parent;
    			}
    			
    			_node = parent;
    		}
    		return *this;
    	}
    public:
    	Node* _node;
    };
    
    // KeyOfT: 用于获取T中的key的一个仿函数类
    template<class K, class T, class KeyOfT>
    class RBTree
    {
    private:
    	typedef RBTreeNode<T> Node;
    public:
    	typedef __RBTreeIterator<T, T&, T*> iterator;
    
    	RBTree(Node* root = nullptr)
    		: _root(root)
    	{}
    	
    	// begin() 就是找红黑树的最左节点
    	iterator begin()
    	{
    		Node* left = _root;
    		while (left && left->_left)
    		{
    			left = left->_left;
    		}
    		return iterator(left);
    	}
    	
    	// 因为迭代器是左闭右开,所以end()的迭代器设置为空
    	iterator end()
    	{
    		return iterator(nullptr);
    	}
    	
    	pair<iterator, bool> Insert(const T& data)
    	{
    		KeyOfT kot;
    		
    		if (_root == nullptr)
    		{
    			_root = new Node(data);
    			_root->_col = BLACK;
    			return make_pair(iterator(_root), true);
    		}
    
    		Node* parent = nullptr;
    		Node* cur = _root;
    		while (cur)
    		{
    			if (kot(data) > kot(cur->_data))
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (kot(data) < kot(cur->_data))
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
    				return make_pair(iterator(cur), false);
    			}
    		}
    
    		cur = new Node(data);
    		cur->_col = RED;
    		// 保存cur用于返回
    		Node* newnode = cur;
    		
    		if (kot(data) > kot(parent->_data))
    		{
    			parent->_right = cur;
    		}
    		else
    		{
    			parent->_left = cur;
    		}
    		cur->_parent = parent;
    
    		while (parent && parent->_col == RED)
    		{
    			Node* grandparent = parent->_parent;
    
    			if (parent == grandparent->_left)
    			{
    				Node* uncle = grandparent->_right;
    
    				if (uncle && uncle->_col == RED)
    				{
    					parent->_col = uncle->_col = BLACK;
    					grandparent->_col = RED;
    					
    					cur = grandparent;
    					parent = cur->_parent;
    				}
    				else
    				{
    					if (cur == parent->_left)
    					{
    						RotateR(grandparent);
    						
    						parent->_col = BLACK;
    						grandparent->_col = RED;
    					}
    					else
    					{
    						RotateL(parent);
    						RotateR(grandparent);
    						
    						cur->_col = BLACK;
    						grandparent->_col = RED;
    					}
    					break;
    				}
    			}
    			else
    			{
    				Node* uncle = grandparent->_left;
    
    				if (uncle && uncle->_col == RED)
    				{
    					parent->_col = uncle->_col = BLACK;
    					grandparent->_col = RED;
    
    					cur = grandparent;
    					parent = cur->_parent;
    				}
    				else
    				{
    					if (cur == parent->_right)
    					{
    						RotateL(grandparent);
    						
    						parent->_col = BLACK;
    						grandparent->_col = RED;
    					}
    					else
    					{
    						RotateR(parent);
    						RotateL(grandparent);
    						
    						cur->_col = BLACK;
    						grandparent->_col = RED;
    					}
    					break;
    				}
    			}
    		}
    
    		_root->_col = BLACK;
    		return make_pair(iterator(newnode), true);
    	}
    private:
    	void RotateL(Node* parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		parent->_right = subRL;
    		if (subRL)
    		{
    			subRL->_parent = parent;
    		}
    		Node* ppNode = parent->_parent;
    
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		if (_root == parent)
    		{
    			_root = subR;
    			subR->_parent = nullptr;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    			{
    				ppNode->_left = subR;
    			}
    			else
    			{
    				ppNode->_right = subR;
    			}
    			subR->_parent = ppNode;
    		}
    	}
    	void RotateR(Node* parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    		{
    			subLR->_parent = parent;
    		}
    
    		Node* ppNode = parent->_parent;
    		subL->_right = parent;
    		parent->_parent = subL;
    
    		if (_root == parent)
    		{
    			_root = subL;
    			subL->_parent = nullptr;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    			{
    				ppNode->_left = subL;
    			}
    			else
    			{
    				ppNode->_right = subL;
    			}
    			subL->_parent = ppNode;
    		}
    	}
    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

    Set.h

    #include "RBTree.h"
    
    namespace zs
    {
    	template<class K>
    	class set
    	{
    	public:
    		class SetKeyOfT
    		{
    		public:
    			const K& operator()(const K& key)
    			{
    				return key;
    			}
    		};
    
    		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    
    		iterator begin()
    		{
    			return _t.begin();
    		}
    
    		iterator end()
    		{
    			return _t.end();
    		}
    
    		pair<iterator, bool> insert(const K& key)
    		{
    			return _t.Insert(key);
    		}
    	private:
    			// set的底层就是一棵红黑树
    			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

    Map.h

    #include "RBTree.h"
    
    namespace zs
    {
    	template<class K, class V>
    	class map
    	{
    	public:
    		class MapKeyOfT
    		{
    		public:
    			const K& operator()(const pair<K, V>& kv)
    			{
    				return kv.first;
    			}
    		};
    
    		typedef typename RBTree<K, pair<K,V>, MapKeyOfT>::iterator iterator;
    
    		iterator begin()
    		{
    			return _t.begin();
    		}
    
    		iterator end()
    		{
    			return _t.end();
    		}
    		
    		pair<iterator, bool> insert(const pair<K, V>& kv)
    		{
    			return _t.Insert(kv);
    		}
    		
    		// map支持[]操作
    		V& operator[](const K& key)
    		{
    			pair<iterator, bool> ret = insert(make_pair(key, V()));
    			return ret.first->second;
    		}
    	private:
    		// map的底层就是一棵红黑树
    		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
  • 相关阅读:
    抖音a_bogus,mstoken全参数爬虫逆向补环境2024-06-15最新版
    为何我国会成为水稻进口大国?国稻种芯:很简单了---价格
    切换阿里云ES方式及故障应急处理方案
    pycharm2023.3专业版安装后打开无反应
    了解WebGL三维技术
    IDA详细使用教程
    【微信小程序 | 实战开发】ES5、ES6概述和新特性介绍
    在线文档生成:Swagger
    jQuery Callback 方法
    GitHub获120k+star的阿里内网“疯传”葵花宝典JVM虚拟机调优指南
  • 原文地址:https://blog.csdn.net/weixin_62172209/article/details/133606713