-
map&set的封装
前言
在STL中，map和set底层都是用红黑树实现的，在前面一篇博客模拟实现了红黑树后，这篇博客要对map和set进行封装，以了解及熟悉其底层实现。
k模型和kv模型
set只存储key值，将key值作为关键码，作为被搜索的对象，属于k模型；而map存储的是一个键值对，每一个key值对应一个value值，但底层的红黑树是k模型还是kv模型？如果是k模型，模板参数只有一个k，如果是kv模型，模板参数有两个，一个k一个v。参考了STL源码，我发现红黑树将k模型和kv模型抽象出来，即只使用一个模板参数T，set封装时传k，map封装时将k和v打包成pair传给T。
set将key作为第二个参数传给re_tree
map将用key和T打包成的键值对作为第二个参数传给rb_tree
rb_tree的第二个参数作为node的参数
总之，re_tree中存储的数据类型为value。（第一个参数有什么用？第一个参数是key的类型，第一个参数常用在搜索函数，需要用key值搜索，所以第一个参数要作为函数的参数类型存在）template <class K, class V> struct RBTreeNode { pair<K, V> _kv; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Colour _col; RBTreeNode(pair<K, V> kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
所以对之前实现的代码进行改造
template <class T> struct RBTreeNode { T _data; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Colour _col; RBTreeNode(T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
节点中存储的数据类型统一成T，那么在比较时有两种情况，一种T是key可以直接进行比较，另一种T是pair，比较时要用pair的first数据进行比较，但看文档之后，pair确实有重载比较，但比较的规则不是我们想要的：没有用first来判断pair的大小
但又不能再重载一次（函数名相同，参数相同，再重载的话跟库中重载的冲突），STL是怎么解决这个问题的？STL使用了仿函数，分别在map和set中定义仿函数，将仿函数作为第三个传给re_tree，通过这个仿函数能取出T中我们需要比较的对象，对于set比较的对象就是key，对于map比较的对象就是pair的first
（KeyOfValue在STL中的一个使用，用KeyOfValue构造匿名对象，由于KeyOfValue重载了()，将v作为参数就能得到要进行比较的对象）改造后的红黑树
#pragma once #includeusing namespace std; #include #include enum Colour { RED, BLACK }; template <class T> struct RBTreeNode { T _data; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Colour _col; RBTreeNode(T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} }; template <class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: bool Insert(const T& data); void Inorder() { _Inorder(_root); } private: void RotateL(Node* parent); void RotateR(Node* parent); void _Inorder(Node* root); private: Node* _root = nullptr; }; template <class K, class T, class KeyOfT> bool RBTree<K, T, KeyOfT>::Insert(const T& data) { KeyOfT kot; // 以搜索二叉树的规则插入 if (_root == nullptr) { _root = new Node(data); // 根节点为黑色 _root->_col = BLACK; return true; } Node* cur = _root; Node* parent = nullptr; // 找合适的插入位置 while (cur) { if (kot(data) < kot(cur->_data)) { parent = cur; cur = cur->_left; } else if (kot(data) > kot(cur->_data)) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(data); // 判断该插入parent的哪边 if (kot(data) < kot(parent->_data)) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 插入结束 // 保持平衡 while (parent && parent->_col == RED) // 出现连续的红节点 { Node* grandParent = parent->_parent; assert(grandParent); if (grandParent->_left == parent) // parent在祖父节点左边 { Node* uncle = grandParent->_right; // u为红色，一定要提前判断u是否存在 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandParent->_col = RED; if (grandParent == _root) { grandParent->_col = BLACK; return true; } else // grandParent不是根节点，但其父节点为黑色，也插入完成 { if (grandParent->_parent && grandParent->_parent->_col == BLACK) { return true; } else // grandParent的父节点为红，出现连续红节点，更新节点，继续调整 { cur = grandParent; parent = cur->_parent; } } } // end of if (uncle && uncle->_col == RED) else // u不存在或者为黑 { // cur在p的左边 if (cur == parent->_left) { RotateR(grandParent); grandParent->_col = RED; parent->_col = BLACK; } else // cur在p的右边，需要旋转成左边的情况 { RotateL(parent); RotateR(grandParent); cur->_col = BLACK; grandParent->_col = RED; } return true; } } // end of - if (grandParent->_left == parent) else // p在grandParent的右边 { Node* uncle = grandParent->_left; assert(grandParent); // u为红色 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandParent->_col = RED; if (grandParent == _root) { _root->_col = BLACK; return true; } else { if (grandParent->_parent->_col == BLACK) { return true; } // 更新继续调整 else { cur = grandParent; parent = cur->_parent; } } } // end of if (uncle && uncle->_col == RED) else // u不存在或者为黑 { // cur在p的右边 if (cur == parent->_right) { RotateL(grandParent); grandParent->_col = RED; parent->_col = BLACK; } else // cur在p的右边，需要旋转成左边的情况 { RotateR(parent); RotateL(grandParent); cur->_col = BLACK; grandParent->_col = RED; } return true; } } // end of - else }// end if - while return true; } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::RotateL(Node* parent) { KeyOfT kot; Node* subR = parent->_right; Node* subRL = subR->_left; subR->_left = parent; parent->_right = subRL; Node* pparent = parent->_parent; parent->_parent = subR; if (subRL) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else // 该子树是树的一部分 { subR->_parent = pparent; if (kot(subR)->_data < kot(pparent->_data)) { pparent->_left = subR; } else { pparent->_right = subR; } } } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::RotateR(Node* parent) { KeyOfT kot; Node* subL = parent->_left; Node* subLR = subL->_right; subL->_right = parent; parent->_left = subLR; Node* pparent = parent->_parent; parent->_parent = subL; if (subLR) subLR->_parent = parent; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { subL->_parent = pparent; if (kot(subL->_data) < kot(pparent->_data)) { pparent->_left = subL; } else { pparent->_right = subL; } } } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::_Inorder(Node* root) { KeyOfT kot; if (root == nullptr) return; _Inorder(root->_left); cout << root->kot(root->_data) << ' '; _Inorder(root->_right); } - 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
改造部分大多是将比较数据套上仿函数
迭代器的定义
红黑树迭代器的结构和链表的迭代器类似，模板参数都有三个，T为节点中存储数据的类型，Ref为节点数据的引用，Ptr为节点中数据的指针。STL库中的红黑树实现了头节点，头节点的left指向树中最小节点，right指向树中最大节点，但实现头节点要付出较大的代价，在节点有了parent指针后，可以直接模拟中序进行++，–的操作。
++就是找比当前节点大的节点，翻译一下就是当前节点右树的最左节点。如果当前节点无右树，向上找parent，如果当前节点是parent的左孩子，那么parent就是比当前节点大的节点；如果当前节点是parent的右孩子，说明当前节点大于parent，将当前节点更新为parent继续向上找，直到当前节点是parent的左孩子。
–同理
1.左孩子存在，返回左树的最大节点
2.左孩子不存在，如果当前节点是parent的右孩子，返回parent
3.左孩子不存在，当前节点是parent的左孩子，向上更新，直到当前节点是parent的右孩子template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator++() { if (_node->_right) // 右孩子存在 { _node = _node->_right; while (_node->_left) { _node = _node->_left; } } else { while (_node->_parent && _node == _node->_parent->_right) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新 { _node = _node->parent; } _node = _node->_parent; } return *this; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator++(int) { self tmp = *this; ++(*this); return tmp; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator--() { if (_node->_left) // 右孩子存在 { _node = _node->_left; while (_node->_right) { _node = _node->_right; } } else { while (_node->_parent && _node == _node->_parent->_left) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新 { _node = _node->parent; } _node = _node->_parent; } return *this; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator--(int) { self tmp = *this; --(*this); return tmp; }- 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
红黑树的封装
#pragma once #includeusing namespace std; #include #include enum Colour { RED, BLACK }; template <class T> struct RBTreeNode { T _data; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Colour _col; RBTreeNode(T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} }; template <class T, class Ref, class Ptr> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, Ref, Ptr> self; RBTreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &(_node->_data); } self& operator++(); self operator++(int); self& operator--(); self operator--(int); bool operator!=(self& s) { return s._node != _node; } Node* _node; }; template <class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, T&, T*> iterator; typedef RBTreeIterator<T, const T&, const T*> const_iterator; public: pair<iterator, bool> Insert(const T& data); iterator begin() { Node* cur = _root; while (cur->_left) { cur = cur->_left; } return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* cur = _root; while (cur->_left) { cur = cur->_left; } return const_iterator(cur); } const_iterator end() const { return const_iterator(nullptr); } void Inorder() { _Inorder(_root); } private: void RotateL(Node* parent); void RotateR(Node* parent); void _Inorder(Node* root); private: Node* _root = nullptr; }; template <class K, class T, class KeyOfT> pair<typename RBTree<K, T, KeyOfT>::iterator, bool> RBTree<K, T, KeyOfT>::Insert(const T& data) { KeyOfT kot; // 以搜索二叉树的规则插入 if (_root == nullptr) { _root = new Node(data); // 根节点为黑色 _root->_col = BLACK; return make_pair(iterator(_root), true); } Node* cur = _root; Node* parent = nullptr; // 找合适的插入位置 while (cur) { if (kot(data) < kot(cur->_data)) { parent = cur; cur = cur->_left; } else if (kot(data) > kot(cur->_data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); // 判断该插入parent的哪边 if (kot(data) < kot(parent->_data)) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 插入结束 // 保持平衡 while (parent && parent->_col == RED) // 出现连续的红节点 { Node* grandParent = parent->_parent; assert(grandParent); if (grandParent->_left == parent) // parent在祖父节点左边 { Node* uncle = grandParent->_right; // u为红色，一定要提前判断u是否存在 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandParent->_col = RED; if (grandParent == _root) { grandParent->_col = BLACK; return make_pair(iterator(cur), true); } else // grandParent不是根节点，但其父节点为黑色，也插入完成 { if (grandParent->_parent && grandParent->_parent->_col == BLACK) { return make_pair(iterator(cur), true); } else // grandParent的父节点为红，出现连续红节点，更新节点，继续调整 { cur = grandParent; parent = cur->_parent; } } } // end of if (uncle && uncle->_col == RED) else // u不存在或者为黑 { pair<iterator, bool> ret = make_pair(iterator(cur), true); // cur在p的左边 if (cur == parent->_left) { RotateR(grandParent); grandParent->_col = RED; parent->_col = BLACK; } else // cur在p的右边，需要旋转成左边的情况 { RotateL(parent); RotateR(grandParent); cur->_col = BLACK; grandParent->_col = RED; } return ret; } } // end of - if (grandParent->_left == parent) else // p在grandParent的右边 { Node* uncle = grandParent->_left; assert(grandParent); // u为红色 if (uncle && uncle->_col == RED) { uncle->_col = BLACK; parent->_col = BLACK; grandParent->_col = RED; if (grandParent == _root) { _root->_col = BLACK; return make_pair(iterator(cur), true); } else { if (grandParent->_parent->_col == BLACK) { return make_pair(iterator(cur), true); } // 更新继续调整 else { cur = grandParent; parent = cur->_parent; } } } // end of if (uncle && uncle->_col == RED) else // u不存在或者为黑 { pair<iterator, bool> ret = make_pair(iterator(cur), true); // cur在p的右边 if (cur == parent->_right) { RotateL(grandParent); grandParent->_col = RED; parent->_col = BLACK; } else // cur在p的右边，需要旋转成左边的情况 { RotateR(parent); RotateL(grandParent); cur->_col = BLACK; grandParent->_col = RED; } return ret; } } // end of - else }// end if - while return make_pair(iterator(cur), true); } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::RotateL(Node* parent) { KeyOfT kot; Node* subR = parent->_right; Node* subRL = subR->_left; subR->_left = parent; parent->_right = subRL; Node* pparent = parent->_parent; parent->_parent = subR; if (subRL) subRL->_parent = parent; if (_root == parent) { _root = subR; subR->_parent = nullptr; } else // 该子树是树的一部分 { subR->_parent = pparent; if (kot(subR->_data) < kot(pparent->_data)) { pparent->_left = subR; } else { pparent->_right = subR; } } } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::RotateR(Node* parent) { KeyOfT kot; Node* subL = parent->_left; Node* subLR = subL->_right; subL->_right = parent; parent->_left = subLR; Node* pparent = parent->_parent; parent->_parent = subL; if (subLR) subLR->_parent = parent; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { subL->_parent = pparent; if (kot(subL->_data) < kot(pparent->_data)) { pparent->_left = subL; } else { pparent->_right = subL; } } } template <class K, class T, class KeyOfT> void RBTree<K, T, KeyOfT>::_Inorder(Node* root) { KeyOfT kot; if (root == nullptr) return; _Inorder(root->_left); cout << kot(root->_data) << ' '; _Inorder(root->_right); } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator++() { if (_node->_right) // 右孩子存在 { _node = _node->_right; while (_node->_left) { _node = _node->_left; } } else { while (_node->_parent && _node == _node->_parent->_right) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新 { _node = _node->_parent; } _node = _node->_parent; } return *this; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator++(int) { self tmp = *this; ++(*this); return tmp; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self& RBTreeIterator<T, Ref, Ptr>::operator--() { if (_node->_left) // 右孩子存在 { _node = _node->_left; while (_node->_right) { _node = _node->_right; } } else { while (_node->_parent && _node == _node->_parent->_left) // 如果父节点存在并且当前节点是父节点的右孩子，要继续更新 { _node = _node->parent; } _node = _node->_parent; } return *this; } template <class T, class Ref, class Ptr> typename RBTreeIterator<T, Ref, Ptr>::self RBTreeIterator<T, Ref, Ptr>::operator--(int) { self tmp = *this; --(*this); return tmp; } - 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
set的封装
template <class K> class Set { struct KeyOfSet { const K& operator()(const K& data) { return data; } }; public: typedef RBTreeIterator<K, const K&, const K*> iterator; typedef RBTreeIterator<K, const K&, const K*> const_iterator; iterator begin() const{ return _t.begin(); } iterator end() const{ return _t.end(); } pair<iterator, bool> Insert(const K& k) { pair<RBTreeIterator<K, K&, K*>, bool> p = _t.Insert(k); return pair<iterator, bool>(iterator(p.first._node), p.second); } void Inorder() { _t.Inorder(); } private: typedef RBTree<K, K, KeyOfSet> RBTree; RBTree _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
map的封装
template <class K, class V> class Map { struct KeyOfMap { const K& operator()(const pair<K, V>& data) { return data.first; } }; public: typedef RBTreeIterator<pair<K, V>, pair<K, V>&, pair<K, V>*> iterator; typedef RBTreeIterator<const pair<K, V>, const pair<K, V>&, const pair<K, V>*> 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); } void Inorder() { _t.Inorder(); } V& operator[](const K& k) { pair<K, V> p(k, V()); pair<iterator, bool> ret = _t.Insert(p); return ret.first->second; } private: typedef RBTree<K, pair<K, V>, KeyOfMap> RBTree; RBTree _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
两者的接口大多是复用红黑树的接口，其中map要实现[]的重载：先根据key值构造一个键值对，该键值对的value值是默认值，然后将键值对插入得到返回的pair，函数最后返回插入得到的pair的first的value引用（pair的first为map的迭代器）
-
相关阅读:
Android 10.0 11.0 12.0 启动模拟器教程
Java基于SpringBoot的车辆充电桩
【.NET 深呼吸】全代码编写WPF程序
GPU服务器的多用户配置
贪心算法的高逼格应用——Huffman编码
【校招VIP】产品原型产品需求要点分析
string 类以及模拟实现
飞机机场城市标签 易语言代码
入门力扣自学笔记115 C++ （题目编号1408）
分享云安全实践，透视2022亚马逊云科技re:Inforce全球安全大会
- 原文地址：https://blog.csdn.net/weixin_61432764/article/details/126570610
