【C++】封装红黑树实现的map和set

1.源码及框架分析

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件

中。

map和set的实现结构框架核⼼部分截取出来如下：

1 // set 2 # ifndef __SGI_STL_INTERNAL_TREE_H 3 # include <stl_tree.h> 4 # endif 5 # include <stl_set.h> 6 # include <stl_multiset.h> 7 8 // map 9 # ifndef __SGI_STL_INTERNAL_TREE_H 10 # include <stl_tree.h> 11 # endif 12 # include <stl_map.h> 13 # include <stl_multimap.h> 14 15 // stl_set.h 16 template < class Key , class Compare = less<Key>, class Alloc = alloc> 17 class set { 18 public : 19 // typedefs: 20 typedef Key key_type; 21 typedef Key value_type; 22 private : 23 typedef rb_tree<key_type, value_type, 24 identity<value_type>, key_compare, Alloc> rep_type; 25 rep_type t; // red-black tree representing set 26 }; 27 28 // stl_map.h 29 template < class Key , class T , class Compare = less<Key>, class Alloc = alloc> 30 class map { 31 public : 32 // typedefs: 33 typedef Key key_type; 34 typedef T mapped_type; 35 typedef pair< const Key, T> value_type; 36 private : 37 typedef rb_tree<key_type, value_type, 38 select1st<value_type>, key_compare, Alloc> rep_type; 39 rep_type t; // red-black tree representing map 40 }; 41 42 // stl_tree.h 43 struct __rb_tree_node_base 44 { 45 typedef __rb_tree_color_type color_type; 46 typedef __rb_tree_node_base* base_ptr; 47 48 color_type color; 49 base_ptr parent; 50 base_ptr left; 51 base_ptr right; 52 }; 53 54 // stl_tree.h 55 template < class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc> 56 class rb_tree { 57 protected : 58 typedef void * void_pointer; 59 typedef __rb_tree_node_base* base_ptr; 60 typedef __rb_tree_node<Value> rb_tree_node; 61 typedef rb_tree_node* link_type; 62 typedef Key key_type; 63 typedef Value value_type; 64 public : 65 // insert ⽤的是第⼆个模板参数左形参 66 pair<iterator, bool > insert_unique ( const value_type& x); 67 68 // erase 和 find ⽤第⼀个模板参数做形参 69 size_type erase ( const key_type& x); 70 iterator find ( const key_type& x); 71 protected : 72 size_type node_count; // keeps track of size of tree 73 link_type header; 74 }; 75 76 template < class Value > 77 struct __rb_tree_node : public __rb_tree_node_base 78 { 79 typedef __rb_tree_node<Value>* link_type; 80 Value value_field; 81 };

通过下图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree是实

现key的搜索场景，还是key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定

_rb_tree_node中存储的数据类型。

set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是

pair<const key, T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场

景的map。

要注意⼀下，源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常

key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。

rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板

参数Key呢？尤其是set，两个模板参数是⼀样的，要注意的是对于 map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和ease的是Key对象。

吐槽⼀下，这⾥源码命名⻛格⽐较乱，set模板参数⽤的Key命名，map⽤的是Key和T命名，⽽

rb_tree⽤的⼜是Key和Value，可⻅⼤佬有时写代码也不规范，乱弹琴。

2.模拟实现map和set

2.1实现出复⽤红⿊树的框架，并⽀持insert

参考源码框架，map和set复⽤之前我们实现的红⿊树。

我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的数据类型，我们使⽤

T。

其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊逻辑

⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任

何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给

RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较，具体

细节参考如下代码实现。

// 源码中 pair ⽀持的 < 重载实现 1template < class T1 , class T2 > 2bool operator < ( const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) 3{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); } 4 5// Mymap.h 6namespace zkf 7{ 7template < class K , class V > 8class map 9{ 10struct MapKeyOfT 11{ 12const K& operator ()( const pair<K, V>& kv) 13{ 14return kv.first; 15} 16}; 17public : 18bool insert ( const pair<K, V>& kv) 19{ 20return _t . Insert (kv); 21} 22private : 23RBTree<K, pair<K, V>, MapKeyOfT> _t ; 24}; 25} 26// Myset.h 27namespace zkf 28{ 29template < class K > 33 class set 34 { 35 struct SetKeyOfT 36 { 37 const K& operator ()( const K& key) 38 { 39 return key; 40 } 41 }; 42 public : 43 bool insert ( const K& key) 44 { 45 return _t . Insert (key); 46 } 47 private : 48 RBTree<K, K, SetKeyOfT> _t ; 49 }; 50 } 51 52 // RBTree.h 53 enum Colour 54 { 55 RED, 56 BLACK 57 }; 58 59 template < class T > 60 struct RBTreeNode 61 { 62 T _data; 63 64 RBTreeNode<T>* _left; 65 RBTreeNode<T>* _right; 66 RBTreeNode<T>* _parent; 67 Colour _col; 68 69 RBTreeNode ( const T& data) 70 : _data(data) 71 , _left( nullptr ) 72 , _right( nullptr ) 73 , _parent( nullptr ) 74 {} 75 }; 76 77 // 实现步骤： 78 // 1 、实现红⿊树 79 // 2 、封装 map 和 set 框架，解决 KeyOfT 80 // 3 、 iterator 81 // 4 、 const_iterator 82 // 5 、 key 不⽀持修改的问题 83 // 6 、 operator[] 84 template < class K , class T , class KeyOfT > 85 class RBTree 86 { 87 private : 88 typedef RBTreeNode<T> Node; 89 Node* _root = nullptr ; 90 91 public : 92 bool Insert ( const T& data) 93 { 94 if (_root == nullptr ) 95 { 96 _root = new Node (data); 97 _root->_col = BLACK; 98 return true ; 99 } 100 101 KeyOfT kot; 102 Node* parent = nullptr ; 103 Node* cur = _root; 104 while (cur) 105 { 106 if ( kot (cur->_data) < kot (data)) 107 { 108 parent = cur; 109 cur = cur->_right; 110 } 111 else if ( kot (cur->_data) > kot (data)) 112 { 113 parent = cur; 114 cur = cur->_left; 115 } 116 else 117 { 118 return false ; 119 } 120 } 121 122 cur = new Node (data); 123 Node* newnode = cur; 124 125 // 新增结点。颜⾊给红⾊ 126 cur->_col = RED; 127 if ( kot (parent->_data) < kot (data)) 128 { 129 parent->_right = cur; 130 } 131 else 132 { 133 parent->_left = cur; 134 } 135 cur->_parent = parent; 136 137 //... 138 139 return true ; 140 } 141 }

2.2支持iterator实现

iterator核⼼源代码

1 struct __rb_tree_base_iterator 2 { 3 typedef __rb_tree_node_base::base_ptr base_ptr; 4 base_ptr node; 5 6 void increment () 7 { 8 if (node->right != 0 ) { 9 node = node->right; 10 while (node->left != 0 ) 11 node = node->left; 12 } 13 else { 14 base_ptr y = node->parent; 15 while (node == y->right) { 16 node = y; 17 y = y->parent; 18 } 19 if (node->right != y) 20 node = y; 21 } 22 } 23 24 void decrement () 25 { 26 if (node->color == __rb_tree_red && 27 node->parent->parent == node) 28 node = node->right; 29 else if (node->left != 0 ) { 30 base_ptr y = node->left; 31 while (y->right != 0 ) 32 y = y->right; 33 node = y; 34 } 35 else { 36 base_ptr y = node->parent; 37 while (node == y->left) { 38 node = y; 39 y = y->parent; 40 } 41 node = y; 42 } 43 } 44 }; 45 46 template < class Value , class Ref , class Ptr > 47 struct __rb_tree_iterator : public __rb_tree_base_iterator 48 { 49 typedef Value value_type; 50 typedef Ref reference; 51 typedef Ptr pointer; 52 typedef __rb_tree_iterator<Value, Value&, Value*> iterator; 53 __rb_tree_iterator() {} 54 __rb_tree_iterator(link_type x) { node = x; } 55 __rb_tree_iterator( const iterator& it) { node = it.node; } 56 57 reference operator *() const { return link_type (node)->value_field; } 58 # ifndef __SGI_STL_NO_ARROW_OPERATOR 59 pointer operator ->() const { return &( operator *()); } 60 # endif /* __SGI_STL_NO_ARROW_OPERATOR */ 61 62 self& operator ++() { increment (); return * this ; } 63 self& operator --() { decrement (); return * this ; } 64 65 inline bool operator ==( const __rb_tree_base_iterator& x, 66 const __rb_tree_base_iterator& y) { 67 return x.node == y.node; 68 } 69 70 inline bool operator !=( const __rb_tree_base_iterator& x, 71 const __rb_tree_base_iterator& y) { 72 return x.node != y.node; 73 }

iterator实现思路分析

iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算

符实现，迭代器像指针⼀样访问的⾏为。

这⾥的难点是operator++和operator--的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛

的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10

所在结点的迭代器。

迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点

是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。

迭代器++时，如果it指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也

访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上

找。

如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结

点的⽗亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。

如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完

了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找

到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：it指向15，15右为空，15是10

的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个

访问的结点就是18。

end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18

到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针

置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码空，红⿊树增加了⼀个哨兵位头结点

做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤

nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是--end()判断到结点时空，特殊处

理⼀下，让迭代器结点指向最右结点。具体参考迭代器--实现。

迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->

左⼦树，具体参考下⾯代码实现。

set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree<K,

const K , SetKeyOfT> _t;

map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参

数改成const K即可， RBTree<K, pair<const K, V> , MapKeyOfT> _t;

⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码。

2.3map⽀持[]

map要⽀持[]主要需要修改insert返回值⽀持，修改RBtree中的insert返回值为

pair<Iterator, bool> Insert(const T& data)

有了insert⽀持[]实现就很简单了，具体参考下⾯代码实现

bit::map和bit::set代码实现

// Myset.h # include "RBTree.h" namespace bit { template < class K > class set { struct SetKeyOfT { const K& operator ()( const K& key) { return key; } }; public : typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator; typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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) { 42 return _t . Insert (key); 43 } 44 45 iterator find ( const K& key) 46 { 47 return _t . Find (key); 48 } 49 50 private : 51 RBTree<K, const K, SetKeyOfT> _t ; 52 }; 53 54 void Print ( const set< int >& s) 55 { 56 set< int >::const_iterator it = s. end (); 57 while (it != s. begin ()) 58 { 59 --it; 60 // 不⽀持修改 61 //*it += 2; 62 63 cout << *it << " " ; 64 } 65 cout << endl; 66 } 67 68 void test_set () 69 { 70 set< int > s; 71 int a[] = { 4 , 2 , 6 , 1 , 3 , 5 , 15 , 7 , 16 , 14 }; 72 for ( auto e : a) 73 { 74 s. insert (e); 75 } 76 77 for ( auto e : s) 78 { 79 cout << e << " " ; 80 } 81 cout << endl; 82 83 Print (s); 84 } 85 } 86 87 // Mymap.h 88 # include "RBTree.h" 89 namespace bit 90 { 91 template < class K , class V > 92 class map 93 { 94 struct MapKeyOfT 95 { 96 const K& operator ()( const pair<K, V>& kv) 97 { 98 return kv.first; 99 } 100 }; 101 public : 102 typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::Iterator iterator; 103 typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::ConstIterator const_iterator; 104 105 iterator begin () 106 { 107 return _t . Begin (); 108 } 109 110 iterator end () 111 { 112 return _t . End (); 113 } 114 115 const_iterator begin () const 116 { 117 return _t . Begin (); 118 } 119 120 const_iterator end () const 121 { 122 return _t . End (); 123 } 124 125 pair<iterator, bool > insert ( const pair<K, V>& kv) 126 { 127 return _t . Insert (kv); 128 } 129 130 iterator find ( const K& key) 131 { 132 return _t . Find (key); 133 } 134 135 V& operator []( const K& key) 136 { 137 pair<iterator, bool > ret = insert ( make_pair (key, V ())); 138 return ret.first->second; 139 } 140 141 private : 142 RBTree<K, pair< const K, V>, MapKeyOfT> _t ; 143 }; 144 145 void test_map () 146 { 147 map<string, string> dict; 148 dict. insert ({ "sort" , " 排序 " }); 149 dict. insert ({ "left" , " 左边 " }); 150 dict. insert ({ "right" , " 右边 " }); 151 152 dict[ "left" ] = " 左边，剩余 " ; 153 dict[ "insert" ] = " 插⼊ " ; 154 dict[ "string" ]; 155 156 map<string, string>::iterator it = dict. begin (); 157 while (it != dict. end ()) 158 { 159 // 不能修改 first ，可以修改 second 160 //it->first += 'x'; 161 it->second += 'x' ; 162 163 cout << it->first << ":" << it->second << endl; 164 ++it; 165 } 166 cout << endl; 167 } 168 } 169 170 // RBtree.h 171 enum Colour 172 { 173 RED, 174 BLACK 175 }; 176 177 template < class T > 178 struct RBTreeNode 179 { 180 T _data; 181 182 RBTreeNode<T>* _left; 183 RBTreeNode<T>* _right; 184 RBTreeNode<T>* _parent; 185 Colour _col; 186 187 RBTreeNode ( const T& data) 188 : _data(data) 189 , _left( nullptr ) 190 , _right( nullptr ) 191 , _parent( nullptr ) 192 {} 193 }; 194 195 template < class T , class Ref , class Ptr > 196 struct RBTreeIterator 197 { 198 typedef RBTreeNode<T> Node; 199 typedef RBTreeIterator<T, Ref, Ptr> Self; 200 201 Node* _node; 202 Node* _root; 203 204 RBTreeIterator (Node* node, Node* root) 205 :_node(node) 206 ,_root(root) 207 {} 208 209 Self& operator ++() 210 { 211 if (_node->_right) 212 { 213 // 右不为空，右⼦树最左结点就是中序第⼀个 214 Node* leftMost = _node->_right; 215 while (leftMost->_left) 216 { 217 leftMost = leftMost->_left; 218 } 219 220 _node = leftMost; 221 } 222 else 223 { 224 // 孩⼦是⽗亲左的那个祖先 225 Node* cur = _node; 226 Node* parent = cur->_parent; 227 while (parent && cur == parent->_right) 228 { 229 cur = parent; 230 parent = cur->_parent; 231 } 232 233 _node = parent; 234 } 235 236 return * this ; 237 } 238 239 Self& operator --() 240 { 241 if (_node == nullptr ) // end() 242 { 243 // --end() ，特殊处理，⾛到中序最后⼀个结点，整棵树的最右结点 244 Node* rightMost = _root; 245 while (rightMost && rightMost->_right) 246 { 247 rightMost = rightMost->_right; 248 } 249 250 _node = rightMost; 251 } 252 else if (_node->_left) 253 { 254 // 左⼦树不为空，中序左⼦树最后⼀个 255 Node* rightMost = _node->_left; 256 while (rightMost->_right) 257 { 258 rightMost = rightMost->_right; 259 } 260 261 _node = rightMost; 262 } 263 else 264 { 265 // 孩⼦是⽗亲右的那个祖先 266 Node* cur = _node; 267 Node* parent = cur->_parent; 268 while (parent && cur == parent->_left) 269 { 270 cur = parent; 271 parent = cur->_parent; 272 } 273 274 _node = parent; 275 276 } 277 278 return * this ; 279 } 280 281 Ref operator *() 282 { 283 return _node->_data; 284 } 285 286 Ptr operator ->() 287 { 288 return &_node->_data; 289 } 290 291 bool operator != ( const Self& s) const 292 { 293 return _node != s._node; 294 } 295 296 bool operator == ( const Self& s) const 297 { 298 return _node == s._node; 299 } 300 }; 301 302 template < class K , class T , class KeyOfT > 303 class RBTree 304 { 305 typedef RBTreeNode<T> Node; 306 public : 307 typedef RBTreeIterator<T, T&, T*> Iterator; 308 typedef RBTreeIterator<T, const T&, const T*> ConstIterator; 309 310 Iterator Begin () 311 { 312 Node* leftMost = _root; 313 while (leftMost && leftMost->_left) 314 { 315 leftMost = leftMost->_left; 316 } 317 318 return Iterator (leftMost, _root); 319 } 320 321 Iterator End () 322 { 323 return Iterator ( nullptr , _root); 324 } 325 326 ConstIterator Begin () const 327 { 328 Node* leftMost = _root; 329 while (leftMost && leftMost->_left) 330 { 331 leftMost = leftMost->_left; 332 } 333 334 return ConstIterator (leftMost, _root); 335 } 336 337 ConstIterator End () const 338 { 339 return ConstIterator ( nullptr , _root); 340 } 341 342 RBTree () = default ; 343 344 RBTree ( const RBTree& t) 345 { 346 _root = Copy (t._root); 347 } 348 349 RBTree& operator =(RBTree t) 350 { 351 swap (_root, t._root); 352 return * this ; 353 } 354 355 ~ RBTree () 356 { 357 Destroy (_root); 358 _root = nullptr ; 359 } 360 361 pair<Iterator, bool > Insert ( const T& data) 362 { 363 if (_root == nullptr ) 364 { 365 _root = new Node (data); 366 _root->_col = BLACK; 367 return make_pair ( Iterator (_root, _root), true ); 368 } 369 370 KeyOfT kot; 371 Node* parent = nullptr ; 372 Node* cur = _root; 373 while (cur) 374 { 375 if ( kot (cur->_data) < kot (data)) 376 { 377 parent = cur; 378 cur = cur->_right; 379 } 380 else if ( kot (cur->_data) > kot (data)) 381 { 382 parent = cur; 383 cur = cur->_left; 384 } 385 else 386 { 387 return make_pair ( Iterator (cur, _root), false ); 388 } 389 } 390 391 cur = new Node (data); 392 Node* newnode = cur; 393 394 // 新增结点。颜⾊红⾊给红⾊ 395 cur->_col = RED; 396 if ( kot (parent->_data) < kot (data)) 397 { 398 parent->_right = cur; 399 } 400 else 401 { 402 parent->_left = cur; 403 } 404 cur->_parent = parent; 405 406 while (parent && parent->_col == RED) 407 { 408 Node* grandfather = parent->_parent; 409 // g 410 // p u 411 if (parent == grandfather->_left) 412 { 413 Node* uncle = grandfather->_right; 414 if (uncle && uncle->_col == RED) 415 { 416 // u 存在且为红 - 》变⾊再继续往上处理 417 parent->_col = uncle->_col = BLACK; 418 grandfather->_col = RED; 419 420 cur = grandfather; 421 parent = cur->_parent; 422 } 423 else 424 { 425 // u 存在且为⿊或不存在 - 》旋转 + 变⾊ 426 if (cur == parent->_left) 427 { 428 // g 429 // p u 430 //c 431 // 单旋 432 RotateR (grandfather); 433 parent->_col = BLACK; 434 grandfather->_col = RED; 435 } 436 else 437 { 438 // g 439 // p u 440 // c 441 // 双旋 442 RotateL (parent); 443 RotateR (grandfather); 444 445 cur->_col = BLACK; 446 grandfather->_col = RED; 447 } 448 449 break ; 450 } 451 } 452 else 453 { 454 // g 455 // u p 456 Node* uncle = grandfather->_left; 457 // 叔叔存在且为红， - 》变⾊即可 458 if (uncle && uncle->_col == RED) 459 { 460 parent->_col = uncle->_col = BLACK; 461 grandfather->_col = RED; 462 463 // 继续往上处理 464 cur = grandfather; 465 parent = cur->_parent; 466 } 467 else // 叔叔不存在，或者存在且为⿊ 468 { 469 // 情况⼆：叔叔不存在或者存在且为⿊ 470 // 旋转 + 变⾊ 471 // g 472 // u p 473 // c 474 if (cur == parent->_right) 475 { 476 RotateL (grandfather); 477 parent->_col = BLACK; 478 grandfather->_col = RED; 479 } 480 else 481 { 482 // g 483 // u p 484 // c 485 RotateR (parent); 486 RotateL (grandfather); 487 cur->_col = BLACK; 488 grandfather->_col = RED; 489 } 490 break ; 491 } 492 } 493 } 494 495 _root->_col = BLACK; 496 497 return make_pair ( Iterator (newnode, _root), true ); 498 } 499 500 Iterator Find ( const K& key) 501 { 502 Node* cur = _root; 503 while (cur) 504 { 505 if (cur->_kv.first < key) 506 { 507 cur = cur->_right; 508 } 509 else if (cur->_kv.first > key) 510 { 511 cur = cur->_left; 512 } 513 else 514 { 515 return Iterator (cur, _root); 516 } 517 } 518 519 return End (); 520 } 521 522 private : 523 void RotateL (Node* parent) 524 { 525 Node* subR = parent->_right; 526 Node* subRL = subR->_left; 527 528 parent->_right = subRL; 529 if (subRL) 530 subRL->_parent = parent; 531 532 Node* parentParent = parent->_parent; 533 534 subR->_left = parent; 535 parent->_parent = subR; 536 537 if (parentParent == nullptr ) 538 { 539 _root = subR; 540 subR->_parent = nullptr ; 541 } 542 else 543 { 544 if (parent == parentParent->_left) 545 { 546 parentParent->_left = subR; 547 } 548 else 549 { 550 parentParent->_right = subR; 551 } 552 553 subR->_parent = parentParent; 554 } 555 } 556 557 void RotateR (Node* parent) 558 { 559 Node* subL = parent->_left; 560 Node* subLR = subL->_right; 561 562 parent->_left = subLR; 563 if (subLR) 564 subLR->_parent = parent; 565 566 Node* parentParent = parent->_parent; 567 568 subL->_right = parent; 569 parent->_parent = subL; 570 571 if (parentParent == nullptr ) 572 { 573 _root = subL; 574 subL->_parent = nullptr ; 575 } 576 else 577 { 578 if (parent == parentParent->_left) 579 { 580 parentParent->_left = subL; 581 } 582 else 583 { 584 parentParent->_right = subL; 585 } 586 587 subL->_parent = parentParent; 588 } 589 590 } 591 592 void Destroy (Node* root) 593 { 594 if (root == nullptr ) 595 return ; 596 597 Destroy (root->_left); 598 Destroy (root->_right); 599 delete root; 600 } 601 602 Node* Copy (Node* root) 603 { 604 if (root == nullptr ) 605 return nullptr ; 606 607 Node* newRoot = new Node (root->_kv); 608 newRoot->_left = Copy (root->_left); 609 newRoot->_right = Copy (root->_right); 610 611 return newRoot; 612 } 613 614 private : 615 Node* _root = nullptr ; 616 };

结束语 map和set详细知识这几篇博客算是总结完了，下片博客看看unordered_set和unordered_map. 本篇博客结束，感谢观看。