-
【数据结构】&&【C++】封装红黑树模拟实现map和set容器
【数据结构】&&【C++】封装红黑树模拟实现map和set容器
一.红黑树的完成
在上一篇红黑树的模拟实现中，已经将红黑树实现完毕，这里不再分析。
#pragma once #includeusing namespace std; //红黑树，不是红色就是黑色 enum Color { RED, BLACK }; template <class K, class V> //先定义结点 struct RBtreeNode { RBtreeNode<K, V>* _left; RBtreeNode<K, V>* _right; RBtreeNode<K, V>* _parent; Color _col; pair<K, V> _kv; RBtreeNode(const pair<K,V> kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED)//根结点是黑色,但插入的元素是红色的 ,_kv(kv) {} }; template <class K, class V> class RBTRree { typedef RBtreeNode<K, V> Node; public: bool CheckColour(Node* root, int blacknum, int benchmark) { if (root == nullptr) { if (blacknum != benchmark) return false; return true; } if (root->_col == BLACK) { ++blacknum; } if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << root->_kv.first << "出现连续红色节点" << endl; return false; } return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark); } bool IsBalance() { return IsBalance(_root); } bool IsBalance(Node* root) { if (root == nullptr) return true; if (root->_col != BLACK) { return false; } // 基准值 int benchmark = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++benchmark; cur = cur->_left; } return CheckColour(root, 0, benchmark); } void RotateL(Node* parent)//左单旋 { Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft; if (curleft) { curleft->_parent = parent; } cur->_left = parent; Node* pp = parent->_parent; parent->_parent = cur; if (parent == _root) { //那么这样cur就是根结点了 _root = cur; cur->_parent = nullptr; } else { if (pp->_left == parent) { pp->_left = cur; } else { pp->_right = cur; } cur->_parent = pp; //旋转后cur和parent bf都为0? } } void RotateR(Node* parent)//右单旋 { Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright; if (curright) { curright->_parent = parent; } Node* ppnode = parent->_parent; cur->_right = parent; parent->_parent = cur; if (ppnode == nullptr) { //说明cur就变成根节点了 _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = cur; } else { ppnode->_right = cur; } cur->_parent = ppnode; } } //插入与搜索树是一致的 bool Insert(const pair<K, V>& kv) { //红黑树的插入就是搜索树的插入 if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } //说明该二叉树不是空树，那么就进行比较找到位置 Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; //记录结点的位置 cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } //走到这里表明cur为空了，表明位置已经找到了 cur = new Node(kv); cur->_col = RED; //插入结点是红色的 if (kv.first > parent->_kv.first) { parent->_right = cur; } else { parent->_left = cur; } //注意这个是三叉链，还要注意父指针 cur->_parent = parent; //插入结点是红色的！然后如果父节点是黑色的那么就没有事，但如果父节点是红色那么就需要讨论！ //可能parent不存在 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; //先记录下祖父位置 if (parent==grandfather->_left) { //说明叔叔在右边 Node* uncle = grandfather->_right; //uncle存在且为红色 if(uncle && uncle->_col == RED) { //解决方法：变色+向上调整 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者uncle存在为黑色 解决方法：旋转+变色 旋转完后作为根结点就需要变黑色 { if (cur == parent->_left) { //右旋 RotateR(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //双旋 //先左旋 RotateL(parent); RotateR(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } else//parent==grandfather->_right { Node* uncle = grandfather->_left; //uncle存在且为红色 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者存在且为黑色 { if (cur == parent->_right) { //左旋 RotateL(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //先右旋再左旋 RotateR(parent); RotateL(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } } //当最后调整到根节点时，父节点不存在，如果这时根结点要是红色的那么就是要变色红色 _root->_col = BLACK; return true; } private: Node* _root=nullptr; }; - 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
二.改造红黑树(泛型适配)
我们要对红黑树进行改造，因为map和set底层用的都是红黑树，虽然不是同一个树，但是是同一个模板实例化出来的红黑树。我们要让红黑树可以适配不同的数据类型，因为set里面存的是K类型，而map里面存的是pair
所以我们一开始并不知道树里存的数据是什么类型，那么就用T表示。当传的模板参数是K类型，树里存的就是K类型，当传的模板参数是pair
所以我们改造红黑树里的数据都改成T类型，T类型我们不知道是什么数据类型，根据传的模板参数决定。enum Color { RED, BLACK }; template <class T> //先定义结点 struct RBtreeNode { //我们也不知道数据是什么？ 是T类型，根据传的模板参数确定 RBtreeNode<T>* _left; RBtreeNode<T>* _right; RBtreeNode<T>* _parent; Color _col; T _data; RBtreeNode(const T& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED)//根结点是黑色,但插入的元素是红色的 , _data(data) {} }; template <class K, class T> //我们不知道数据类型，为什么还要传K类型呢？ //这里的K是find查找 key值 struct RBTree { public: typedef RBtreeNode<T> Node; private: bool Insert(const T& data) { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_data < data) { parent = cur; //记录结点的位置 cur = cur->_right; } else if (cur->_data > data) { parent = cur; cur = cur->_left; } else { return false; } } //走到这里表明cur为空了，表明位置已经找到了 cur = new Node(kv); cur->_col = RED; //插入结点是红色的 if (data > parent->_data) { parent->_right = cur; } else { parent->_left = cur; } //注意这个是三叉链，还要注意父指针 cur->_parent = parent; //插入结点是红色的！然后如果父节点是黑色的那么就没有事，但如果父节点是红色那么就需要讨论！ //可能parent不存在 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; //先记录下祖父位置 if (parent==grandfather->_left) { //说明叔叔在右边 Node* uncle = grandfather->_right; //uncle存在且为红色 if(uncle && uncle->_col == RED) { //解决方法：变色+向上调整 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者uncle存在为黑色 解决方法：旋转+变色 旋转完后作为根结点就需要变黑色 { if (cur == parent->_left) { //右旋 RotateR(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //双旋 //先左旋 RotateL(parent); RotateR(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } else//parent==grandfather->_right { Node* uncle = grandfather->_left; //uncle存在且为红色 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者存在且为黑色 { if (cur == parent->_right) { //左旋 RotateL(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //先右旋再左旋 RotateR(parent); RotateL(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } } //当最后调整到根节点时，父节点不存在，如果这时根结点要是红色的那么就是要变色红色 _root->_col = BLACK; return true; } } //K用来查找数据中的key Node* find(const K& key) { keyofT kof; Node* cur = _root; while (cur) { if (kof(cur->_data) < key) { cur = cur->_right; } else if (kof(cur->_data) > key) { cur = cur->_left; } else { return cur; } } return nullptr; } Node* _root = nullptr; };- 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
存在问题：
红黑树里的比较逻辑都是按照K值进行比较的，这里的红黑树存储的数据是T类型，当插入一个T类型的数据时，我们也不知道这个数据是K类型还是pair
解决方法：
我们可以利用一个仿函数，这个仿函数的功能是可以将数据里的K类型数据取出来。那么我们可以给红黑树增加一个模板参数，给仿函数用。一旦遇到要比较的逻辑时，我们就可以将数据里的K值取出来进行比较。
仿函数实现的原理：当T类型是K类型数据时，直接返回K值即可，当T类型是pairtemplate <class K, class T,class keyofT> //这里的K是find查找 key值，ketofT是仿函数用来获取data数据里的K值 struct RBTree { public: //插入与搜索树是一致的 bool Insert(const T& data)//现在红黑树里存的数据我们不确定，就只是T类型 { //红黑树的插入就是搜索树的插入 if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; keyofT kof; while (cur) { //这里因为树里存的数据到底是什么类型的，所以无法这样比较 //我们想要根据K值来进行比较，但最终的数据可能是pair类型的 //所以我们需要一个仿函数keyofT来获取K类型和pair类型的里的K值 if (kof(cur->_data) < kof(data) { parent = cur; //记录结点的位置 cur = cur->_right; } else if (kof(cur->_data) > kof(data)) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur), false); //插入失败，返回的是已经存在结点的迭代器 } } //走到这里表明cur为空了，表明位置已经找到了 cur = new Node(data); Node* newnode = cur; //下面cur可能会往上走，先记录一下 cur->_col = RED; //插入结点是红色的 if (kof(data) > kof(parent->_data)) { parent->_right = cur; } else { parent->_left = cur; } //注意这个是三叉链，还要注意父指针 cur->_parent = parent; //插入结点是红色的！然后如果父节点是黑色的那么就没有事，但如果父节点是红色那么就需要讨论！ //可能parent不存在 while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; //先记录下祖父位置 if (parent == grandfather->_left) { //说明叔叔在右边 Node* uncle = grandfather->_right; //uncle存在且为红色 if (uncle && uncle->_col == RED) { //解决方法：变色+向上调整 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者uncle存在为黑色 解决方法：旋转+变色 旋转完后作为根结点就需要变黑色 { if (cur == parent->_left) { //右旋 RotateR(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //双旋 //先左旋 RotateL(parent); RotateR(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; } else//uncle不存在或者存在且为黑色 { if (cur == parent->_right) { //左旋 RotateL(grandfather); //变色 parent->_col = BLACK; grandfather->_col = RED; } else { //先右旋再左旋 RotateR(parent); RotateL(grandfather); //变色 cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }- 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
三.封装map和set的接口
封装set,内部实现仿函数，然后底层封装的是存储K值的红黑树。
namespace tao { template <class K>//根据传给模板参数T不同的参数，让红黑树来存不同的数据 class set { //仿函数：set_keyoft用来获取数据里的K值 struct set_keyoft { const K& operator()(const K& kv) { return kv; } }; // public: bool insert(const K& key) { return _rb.insert(key); } private: //根据模板参数来实例化不同的红黑树 //这里的红黑树被实例化成存储K类型的 RBTree<K, K, set_keyoft> _rb; }; }- 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
封装map，实现仿函数，底层存储的是pair
namespace tao { //根据模板参数来实例化不同的红黑树 template <class K,class V> class map { //仿函数：map_keyoft用来获取数据中的K值。 struct map_keyoft { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: bool insert(const pair<K,V>& kv)//插入的数据类型是由红黑树存的数据类型有关 //直接调用红黑树的接口 { return _rb.Insert(kv); //因为map底层红黑树里存的是pair类型数据 } private: RBTree<K, pair<const K,V>, map_keyoft> _rb; //这里红黑树被实例化为存储pair- 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
四.实现红黑树迭代器(泛型适配)
红黑树的迭代器和链表的迭代器类似，都是自定义类型，因为原生指针不能满足需要，所以需要自定义，底层封装着原生指针，也就是指向结点的指针，通过对原生指针一些操作来达到红黑树迭代器的需要。
1.迭代器有普通迭代器和const迭代器，普通迭代很好实现，那么const迭代器如何实现呢？
与链表的const迭代器实现原理一样，我们通过三个模板参数(template)来控制函数的返回值，从而控制返回的是普通类型的迭代器还是const类型的迭代器。这里也就是泛型适配，适配多种类型 。 Ref控制解引用函数的返回值，当Ref为T&时，返回的就是普通迭代器，当Ref为const T&时，返回的就是const迭代器。
Ptr控制的->重载函数的返回值，当Ptr为T时，返回的就是普通迭代器，当Ptr为const T时，返回的就是const迭代器。2.红黑树迭代器的++实现原理：
1.首先begin的位置肯定是在最左边，也就是最小值。
2.++就是下一个位置，++到下一个比它大的位置。我们就要讨论当前结点的右边是否有结点。
3.当右边有结点时，那么就找右边的最小值，也就是右边的最左结点。
4.当右边没有结点时，我们就要往上找父亲结点为左结点的那个祖先。因为当右边没有结点时，说明右边已经访问完了，那么往上找凡是父亲结点是祖先右边时就直接跳过，当父亲结点是祖先左边时，那么这个祖先结点就是下一次要访问的结点。
3.红黑树迭代器的–实现原理:
1.跟加加倒着来就可以了。
2.–就是前面的位置，–到上一个比它小的位置。我们要讨论的是当前结点的左边是否有结点。
3.当左边有结点时，我们就找左边的最大值，也就是左边的最右结点。
4.当左边没有结点时，我们就找父亲结点为右结点的那个祖先。//只有把树里的迭代器搞完，才能搞map和set的迭代器 //迭代器提供三个模板参数，第一个控制数据类型，第二个控制解引用返回值类型，第三个控制->返回值类型 template <class T,class Ref,class Ptr> //泛型适配 struct _treeIterator { typedef _treeIterator<T,Ref,Ptr> Self; typedef RBtreeNode<T> Node; //底层封装一个原生指针 _treeIterator( Node * node)//迭代器的构造 :_node(node) {} Ref& operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator--() { //找孩子是父亲右的那个 //我们要讨论当前结点的左边是否右结点 if (_node->_left)//如果左边存在，那么就找最大值 { Node* curleft = _node->_left; while (curleft->_right) { curleft = curleft->_right; } _node = curleft; } else//左边不存在，就找孩子是父亲右的那个 { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = cur->_parent; } //走到这里说明找到孩子是右边的了 _node = parent; } return *this; } Self& operator++() { //如果右边存在，那么就找最小结点 if (_node->_right) { Node* curright = _node->_right; while (curright->_left) { curright = curright->_left; } _node = curright; } else//右边不存在，就找孩子是父亲左边的那个祖先 { Node* cur = _node; Node* parent = cur->_parent; while (parent&&cur==parent->_right) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } bool operator!=(const Self& n) { return _node != n._node; } //迭代器底层封装着结点指针 Node* _node; };- 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
迭代器完成之后，我们就要在红黑树里，来实现迭代器的begin()和end()了。
1.首先我们需要给迭代器重命名，因为带有模板后，名字太长了。
2.我们可以通过传不同的模板参数，来是实例化出我们想要的迭代器:普通迭代器和const迭代器。
3.红黑树的迭代器begin()是要求在最小结点那个位置的迭代器，即最左结点，找到最左结点后，我们就用该结点的指针构造迭代器即可。
4.红黑树的迭代器end()可以看作是nullptr的位置，当找不到父亲时，就说明到尽头了。 直接用空来构造迭代器。
5.const迭代器的begin()和end()与普通迭代器的begin()和end()是一样的，就是构造时用const迭代器构造，和返回const迭代器。template <class K, class T,class keyofT> //这里的K是find查找 key值 struct RBTree { public: //红黑树的迭代器和链表的迭代器很相似都是自定义类型，里面封装着指针，因为原生指针不满足要求！ typedef RBtreeNode<T> Node; typedef _treeIterator<T,T&,T*> iterator;//普通迭代器 //两个是相同的类模板，通过传不同的模板参数，实例化出不同的迭代器 typedef _treeIterator<T, const T&, const T*> const_iterator;//const迭代器 //通过控制传模板参数来选择是普通迭代器还是const迭代器 iterator begin()//最左边的结点 { Node* curleft = _root; while (curleft && curleft->_left)//还要判断一下curleft是否为空，因为root头可能为空 { curleft = curleft->_left; } return iterator(curleft); } iterator end()//为空的位置 { return iterator(nullptr);//用空表示end(); } const_iterator begin()const { Node* curleft = _root; while (curleft && curleft->_left)//还要判断一下curleft是否为空，因为root头可能为空 { curleft = curleft->_left; } return const_iterator(curleft); } const_iterator end()const { return const_iterator(nullptr);//用空表示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
五.封装map和set的迭代器
只有红黑树里的迭代器完成了，才可以封装map和set里的迭代器。
封装set的迭代器，本质就是调用红黑树里的迭代器接口。1.不过要注意的是，在重命名红黑树里的迭代器时，需要在类名前面加上typename，如果不加上typename是不行的，因为这时类模板还没有实例化出对象出来，就算实例化了，也有部分类型没有实例，因为编译器也不知道这个是内置类型还是静态变量，加上是告诉编译器这个是类型，这个类型在类模板里定义，等类模板实例化后再找。
2.定义好普通迭代和const迭代器后，就可以实现begin()和end()了。namespace tao { //根据模板参数来实例化不同的红黑树 template <class K>//根据传给模板参数T不同的参数，让红黑树来存不同的数据 class set { //这里的红黑树被实例化成存储K类型的 struct set_keyoft { const K& operator()(const K& kv) { return kv; } }; public: //typedef RBTree- 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的迭代器，本质就是调用红黑树里的迭代器接口。
namespace tao { //根据模板参数来实例化不同的红黑树 template <class K,class V> class map { struct map_keyoft { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: //map和set的迭代器就是树里的迭代器 typedef typename RBTree<K, pair<K, V>, map_keyoft>::iterator iterator; typedef typename RBTree<K, pair<K, V>, map_keyoft>::const_iterator const_iterator; //编译器不知道这个是内嵌类型还是自定义类型还是静态变量，所以需要显式表明这个是什么 iterator begin() { return _rb.begin(); } iterator end() { return _rb.end(); } const_iterator begin()const { return _rb.begin(); } const_iterator end()const { return _rb.end(); } private: //这里红黑树被实例化为存储pair- 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
六.解决key不能修改问题
set里面存储的Key值是不能被修改的，map里的存储的K值也是不能被修改，但是Value值是可以被修改！
如果解决这个问题呢？问题：set里的key值不能被修改。map里的key值不能被修改，value值可以被修改。
set解决原理：
1.set里存储的值就只有Key值，索性我们直接让这个存储的数据无法被修改，只能访问读取，无法修改。即使用const修饰。而我们是通过迭代器来访问到这个数据的，所以我们让普通迭代器变成const迭代器即可。所以在set里，普通迭代器和const迭代器最终都是const迭代器。
2.那么迭代器都是const的了，最终都只会调用const修饰的begin()和end()函数了，普通的begin()和end()就不需要写了。
3.不过这样处理又会出现一个很难搞的问题，这个就是set的insert的返回值问题，我们后面要实现map的[]运算符重载就会讲到。set的解决方法： public: typedef typename RBTree<K, K, set_keyoft>::const_iterator iterator;//将普通迭代器也变成const迭代器,这样存储的数据Key就无法被修改了 typedef typename RBTree<K, K, set_keyoft>::const_iterator const_iterator; /*iterator begin() { return _rb.begin(); } iterator end() { return _rb.end(); }*/ //最后只会调用这两个函数。 const_iterator begin()const { return _rb.begin(); } const_iterator end()const { return _rb.end(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
map的解决原理
1.在存储的时候就让K值无法修改。
2.因为我们知道map里存储的数据是pair
3.pair是可以修改的，但是里面的K是无法被修改的！map的解决方法： public: typedef typename RBTree<K, pair<const K, V>, map_keyoft>::iterator iterator; //map的普通迭代器就是普通的，const的就是const的 typedef typename RBTree<K, pair<const K, V>, map_keyoft>::const_iterator const_iterator; //通过存储时，就将K设置为const类型的 iterator begin() { return _rb.begin(); } iterator end() { return _rb.end(); } const_iterator begin()const { return _rb.begin(); } const_iterator end()const { return _rb.end(); } private: RBTree<K, pair<const K,V>, map_keyoft> _rb; //pair是可以修改的，但是里面的K是无法被修改的！ } }- 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
七.实现map[]运算符重载
map的[ ]运算符重载，底层实现本质是调用了insert函数。然后通过insert函数返回的pair
所以在实现[ ]运算符重载时，我们需要对红黑树里的insert进行改造，因为原来的insert的返回值是布尔值，我们需要pair类型返回值。
//改造insert，返回值变成pair- 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
红黑树的insert改造后，那么set和map里的insert都需要修改，因为底层用的就是红黑树的insert。
这样修改是对的吗？有没有什么问题呢？
但是这时会出现一个问题，set里面的insert报错。这是为什么呢？
问题在于，我们之前让普通迭代变成const迭代器，而这里的pair
是pair
那么如何解决这个问题呢？
不知道你有没有见过这个的代码list<int>::iteartor it= l.begin(); list<int>::const_iterator cit =l.begin();- 1
- 2
STL库里是支持将普通迭代器转换成const迭代器。那么库里是如何实现的呢？
1.迭代器的拷贝函数是浅拷贝，我们不需要写，编译器自动生成的拷贝就可以用，编译器自动生成的拷贝函数只能实现普通迭代器拷贝给普通迭代器，const迭代器拷贝给const迭代器。(原理就是拷贝函数的对象类型就是调用这个函数的类型，当普通迭代器调用拷贝时，那么拷贝对象就是普通类型，当const迭代器调用拷贝时，那么拷贝对象就是const类型)
2.而我们需要的是让普通迭代器能够拷贝给const迭代器。所以我们需要自己增加拷贝函数。
3.库里的设计很妙，库里重新定义了一个iterator，作为拷贝对象，而这个iterator固定了就是普通的迭代器，不会随着调用对象而改变类型。所以当普通迭代器调用时，就会将普通iterator拷贝给它。当const迭代器调用时，就会将普通迭代器iterator拷贝给它。
4.所以我们需要对红黑树的迭代器添加拷贝构造。用普通迭代器iteartor作为拷贝对象。template <class T,class Ref,class Ptr> struct _treeIterator { typedef _treeIterator<T,Ref,Ptr> Self; typedef RBtreeNode<T> Node; typedef _treeIterator<T, T&, T*> Iterator;//重新定义一个迭代器，这个迭代器完全是普通迭代器。 _treeIterator(const Iterator& it)//相当于迭代器的拷贝构造,但不完全是 :_node(it._node) {} //当为普通迭代器时，普通迭代器构造普通迭代器，是拷贝构造 //当为const迭代器时，普通迭代器构造const迭代器，是构造 _treeIterator( Node * node)//迭代器的构造 :_node(node) {} …………………… ……………………- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
这样处理后，我们再利用pair
1.先将insert返回类型利用ret接收
2.利用pair//这里的iterator是const_iterator pair<iterator,bool> insert(const K& kv) { //这里insert返回的是树里的普通迭代器_treeIterator- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
最后insert的改造到这里就结束了，insert改造完后，就可以实现[ ]运算符重载了。
V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); //已经存在就就不插入，不存在就插入，默认给V的缺省参数 //如果key在树里已经存在那么就返回已经存在结点的迭代器 //如果key不在树里，那么就将该结点插入进去，返回该结点的迭代器 return ret.first->second; //first先访问里面的迭代器，迭代器的second才是Value值。 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
-
相关阅读:
WPS的excel表格设置了编辑权限，要怎么取消？
Blazor 国际化多语言界面 (I18nText )
Cocos Creator 3.6 新特性详解 3/3：性能篇
原型模式
【JavaScript 进阶教程】汽车商城根据价格区间筛选车辆案例
用友移动管理系统任意文件上传漏洞
RabbitMQ基于Nginx的集群搭建
运用selenium爬取京东商品数据储存到MySQL数据库中
力扣106 补9.11
亿级异构任务调度框架设计与实践
- 原文地址：https://blog.csdn.net/Extreme_wei/article/details/132989914
