-
【C++模拟实现】map、set容器的模拟实现
【C++模拟实现】map、set容器的模拟实现
作者：爱写代码的刚子
时间：2023.9.17
前言：本篇博客有关map、set的模拟实现，其底层采用了红黑树的结构，记录了模拟实现时的问题和解决方案。
map、set模拟实现的代码（insert部分）
部分一：红黑树的迭代器以及红黑树
enum Colour { BLACK, RED }; ///红黑树的节点/// template<class T> struct RBTreeNode { RBTreeNode(const T& kv) :_left(nullptr) ,_parent(nullptr) ,_right(nullptr) ,_c(RED) ,_kv(kv) {} RBTreeNode* _left; RBTreeNode* _parent; RBTreeNode* _right; Colour _c; T _kv; }; //红黑树的迭代器类 template<class T,class Ref,class Ptr> class __iterator { typedef RBTreeNode<T> Node; typedef __iterator<T,Ref,Ptr> Self; typedef __iterator<T,T&,T*> Iterator; public: __iterator(Node* it) :_it(it) {} //如果这个对象是const迭代器，实现的是普通迭代器转为const迭代器， //如果这个对象是普通迭代器，实现的是普通迭代器的拷贝构造。 __iterator(const Iterator& t) :_it(t._it) {} Ref operator*() { return _it->_kv; } Ptr operator->() { return &_it->_kv; } Self& operator++()//前置++ { if(_it->_right) { Node* subLeft=_it->_right; while(subLeft->_left) { subLeft=subLeft->_left; } _it=subLeft; } else{ Node* cur = _it; Node* parent=_it->_parent; while(parent&&parent->_right==cur) { cur=cur->_parent; parent=cur->_parent; } _it=parent; } return *this; } Self operator++(int)//后置++ { __iterator tmp(_it); if(_it->_right) { Node* subLeft=_it->_right; while(subLeft->_left) { subLeft=subLeft->_left; } _it=subLeft; } else{ Node* cur = _it; Node* parent=_it->_parent; while(parent&&parent->_right==cur) { cur=cur->_parent; parent=cur->_parent; } _it=parent; } return tmp; } ///对--的重载暂时不实现(思路和++相反,将operator++中的_left换成_right,将_right换成_left即可) bool operator!=(const Self& l) const { return _it!=l._it; } bool operator==(const Self& l) const { return _it==l._it; } Node* _it; }; //红黑树的模拟实现 template<class K,class T,class SetKeyOfT> struct RBTree { typedef RBTreeNode<T> Node; typedef __iterator<T,T&,T*> iterator; typedef __iterator<T,const T&,const T*> const_iterator; RBTree() :_root(nullptr) {} //红黑树迭代器begin和end/// iterator begin() { Node* cur=_root; if(!_root) { return nullptr; } while(cur->_left) { cur=cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* cur=_root; if(!_root) { return nullptr; } while(cur->_left) { cur=cur->_left; } return const_iterator(cur); } const_iterator end() const { return const_iterator(nullptr); } Node* Find(const K& key) { Node* cur = _root; SetKeyOfT k; while (cur) { if (k(cur->_data) < key) { cur = cur->_right; } else if (k(cur->_data) > key) { cur = cur->_left; } else { return cur; } } return nullptr; } pair<iterator,bool> insert(const T& kv) { if(_root==nullptr) { _root=new Node(kv); _root->_c=BLACK; return make_pair(iterator(_root),true); } Node* cur=_root; Node* parent=nullptr; SetKeyOfT k; while(cur) { if(k(cur->_kv)>k(kv)) { parent=cur; cur=cur->_left; } else if(k(cur->_kv)<k(kv)) { parent=cur; cur=cur->_right; } else{ return make_pair(iterator(cur),false); } } cur=new Node(kv); Node* newnode = cur; / if(k(parent->_kv)>k(kv)) { parent->_left=cur; } else{ parent->_right=cur; } cur->_parent=parent; //需要调整的情况 while(parent&&parent->_c==RED) { Node* grandfather=parent->_parent; if(grandfather->_left==parent) { Node* uncle=grandfather->_right; //判断uncle的几种情况 if(uncle&&uncle->_c==RED) { uncle->_c=parent->_c=BLACK; grandfather->_c=RED; cur=grandfather; parent=cur->_parent; } else { if(cur==parent->_left) { _RotateR(grandfather); grandfather->_c=RED; parent->_c=BLACK; } else{ _RotateL(parent); _RotateR(grandfather); grandfather->_c=RED; cur->_c=BLACK; } break; } } else { Node* uncle=grandfather->_left; if(uncle&&uncle->_c==RED) { uncle->_c=parent->_c=BLACK; grandfather->_c=RED; cur=grandfather; parent=cur->_parent; } else { if(cur==parent->_right) { _RotateL(grandfather); parent->_c=BLACK; grandfather->_c=RED; } else{ _RotateR(parent); _RotateL(grandfather); cur->_c=BLACK; grandfather->_c=RED; } break; } } } _root->_c=BLACK; return make_pair(iterator(newnode),true); } void _RotateR(Node* parent) { Node*cur=parent->_left; Node*curRight=cur->_right; Node*ppnode=parent->_parent; cur->_right=parent; parent->_left=curRight; if(curRight) { curRight->_parent=parent; } parent->_parent=cur; //处理ppnode if(parent==_root) { _root=cur; cur->_parent=nullptr; } else { if(ppnode->_left==parent) { ppnode->_left=cur; } else{ ppnode->_right=cur; } cur->_parent=ppnode; } } void _RotateL(Node* parent) { Node* cur=parent->_right; Node* curLeft=cur->_left; Node* ppnode=parent->_parent; cur->_left=parent; parent->_right=curLeft; if(curLeft) { curLeft->_parent=cur; } parent->_parent=cur; if(parent==_root) { _root=cur; cur->_parent=nullptr; } else { if(ppnode->_left==parent) { ppnode->_left=cur; } else{ ppnode->_right=cur; } cur->_parent=ppnode; } } 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
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
部分二：对set进行封装
template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key)//仿函数 { return key; } }; public: typedef typename RBTree<K,K,SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K,K,SetKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair<iterator,bool> insert(const K& key) { pair<typename RBTree<K,K,SetKeyOfT>::iterator,bool> ret= _t.insert(key);//这边我们需要注意，右边是普通迭代器，左边是const迭代器，我们需要实现普通迭代器构造const迭代器 return pair<iterator,bool>(ret.first,ret.second); } 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
部分三：对map进行封装
template<class K,class V> class map { struct MapKeyOfT { const K& operator()(const pair<K,V>& kv) { return kv.first; } }; public: typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::iterator iterator; typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } pair<iterator,bool> insert(const pair<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; } private: RBTree<K,pair<const 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
遇到的问题以及解决方案
-
【问题】：由于map和set共用一颗树的结构，但是传入的数据类型并不相同，set直接插入key，而map要插入pair。在树里面全部采用统一的模版参数T。在insert的比较大小环节会出现错误，pair不能直接进行大小的比较（虽然库里面pair有进行大小比较的重载函数但是效果并不符合预期）
【解决】：在set和map的结构体里写一个仿函数，在树里面调用名称相同但是功能不同的仿函数，达到对数据的统一比较的效果。
map：
set：
红黑树：
红黑树中的SetKeyOfT可以是其他名字，不要和set中的SetKeyOfT搞混了。
-
【问题】：普通迭代器如何构造const迭代器？
由于set不能对数据进行修改，所以set的迭代器的下面使用红黑树的const迭代器实现的：
观察set对insert函数的封装：
由于set调用红黑树的insert函数而红黑树中insert函数默认返回iterator迭代器，而```pair
【解决】：在红黑树的迭代器中实现普通迭代器对const迭代器的转换：
-
【问题】：如何实现map的pair中的key不能被修改？
【解决】：
注意！以下传入红黑树的模版参数中也需要加上const：
-
留意红黑树迭代器中的iterator++中的算法：
-
在实现迭代器时，这两个运算符是一定要重载的：
-
Map中对[]的重载方法：
-
相关阅读:
dom对象和jquery对象的区别及相互转换
bootstrap样式
客户转化率太低？CRM客户管理系统来帮您
机器学习强基计划5-4：图文详解影响流动与有向分离(D-分离)(附Python实现)
likeshop外卖点餐系统【100%开源无加密】
Hive学习笔记1
刷爆力扣之公平的糖果交换
如何进行内存映射和文件映射操作？
【Python+requests+unittest+excel】实现接口自动化测试框架
spring boot整合jwt
- 原文地址：https://blog.csdn.net/m0_74215144/article/details/132985347
