目录

1 .源码及框架分析

2.模拟实现map和set

2.1 实现出复用红黑树的框架，并支持insert

2.2 ⽀持iterator的实现

2.3map支持[]

2.4 实现

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 };

2.模拟实现map和set

2.1 实现出复用红黑树的框架，并支持insert

• 其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊逻辑 ⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任 何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较，具体 细节参考如下代码实现。

template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) &&
lhs.second<rhs.second); }
// Mymap.h
namespace bit
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}
// Myset.h
namespace bit
{
template<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支持[]

2.4 实现

// 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)
{
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"
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 }
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)
{
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;
}
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()
{
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()
345 {
346 Destroy(_root);
347 _root = nullptr;
348 }
349
350 pair<Iterator, bool> Insert(const T& data)
351 {
352 if (_root == nullptr)
353 {
354 _root = new Node(data);
355 _root->_col = BLACK;
356 return make_pair(Iterator(_root, _root), true);
357 }
358
359 KeyOfT kot;
360 Node* parent = nullptr;
361 Node* cur = _root;
362 while (cur)
363 {
364 if (kot(cur->_data) < kot(data))
365 {
366 parent = cur;
367 cur = cur->_right;
368 }
else if (kot(cur->_data) > kot(data))
370 {
371 parent = cur;
372 cur = cur->_left;
373 }
374 else
375 {
376 return make_pair(Iterator(cur, _root), false);
377 }
378 }
379
380 cur = new Node(data);
381 Node* newnode = cur;
382
383 // 新增结点。颜⾊红⾊给红⾊
384 cur->_col = RED;
385 if (kot(parent->_data) < kot(data))
386 {
387 parent->_right = cur;
388 }
389 else
390 {
391 parent->_left = cur;
392 }
393 cur->_parent = parent;
394
395 while (parent && parent->_col == RED)
396 {
397 Node* grandfather = parent->_parent;
398 // g
399 // p u
400 if (parent == grandfather->_left)
401 {
402 Node* uncle = grandfather->_right;
403 if (uncle && uncle->_col == RED)
404 {
405 // u存在且为红 -》变⾊再继续往上处理
406 parent->_col = uncle->_col = BLACK;
407 grandfather->_col = RED;
408
409 cur = grandfather;
410 parent = cur->_parent;
411 }
412 else
413 {
414 // u存在且为⿊或不存在 -》旋转+变⾊
415 if (cur == parent->_left)
{
417 // g
418 // p u
419 //c
420 //单旋
421 RotateR(grandfather);
422 parent->_col = BLACK;
423 grandfather->_col = RED;
424 }
425 else
426 {
427 // g
428 // p u
429 // c
430 //双旋
431 RotateL(parent);
432 RotateR(grandfather);
433
434 cur->_col = BLACK;
435 grandfather->_col = RED;
436 }
437
438 break;
439 }
440 }
441 else
442 {
443 // g
444 // u p
445 Node* uncle = grandfather->_left;
446 // 叔叔存在且为红，-》变⾊即可
447 if (uncle && uncle->_col == RED)
448 {
449 parent->_col = uncle->_col = BLACK;
450 grandfather->_col = RED;
451
452 // 继续往上处理
453 cur = grandfather;
454 parent = cur->_parent;
455 }
456 else // 叔叔不存在，或者存在且为⿊
457 {
458 // 情况⼆：叔叔不存在或者存在且为⿊
459 // 旋转+变⾊
460 // g
461 // u p
462 // c
if (cur == parent->_right)
464 {
465 RotateL(grandfather);
466 parent->_col = BLACK;
467 grandfather->_col = RED;
468 }
469 else
470 {
471 // g
472 // u p
473 // c
474 RotateR(parent);
475 RotateL(grandfather);
476 cur->_col = BLACK;
477 grandfather->_col = RED;
478 }
479 break;
480 }
481 }
482 }
483
484 _root->_col = BLACK;
485
486 return make_pair(Iterator(newnode, _root), true);
487 }
488
489 Iterator Find(const K& key)
490 {
491 Node* cur = _root;
492 while (cur)
493 {
494 if (cur->_kv.first < key)
495 {
496 cur = cur->_right;
497 }
498 else if (cur->_kv.first > key)
499 {
500 cur = cur->_left;
501 }
502 else
503 {
504 return Iterator(cur, _root);
505 }
506 }
507
508 return End();
509 }
private:
512 void RotateL(Node* parent)
513 {
514 Node* subR = parent->_right;
515 Node* subRL = subR->_left;
516
517 parent->_right = subRL;
518 if (subRL)
519 subRL->_parent = parent;
520
521 Node* parentParent = parent->_parent;
522
523 subR->_left = parent;
524 parent->_parent = subR;
525
526 if (parentParent == nullptr)
527 {
528 _root = subR;
529 subR->_parent = nullptr;
530 }
531 else
532 {
533 if (parent == parentParent->_left)
534 {
535 parentParent->_left = subR;
536 }
537 else
538 {
539 parentParent->_right = subR;
540 }
541
542 subR->_parent = parentParent;
543 }
544 }
545
546 void RotateR(Node* parent)
547 {
548 Node* subL = parent->_left;
549 Node* subLR = subL->_right;
550
551 parent->_left = subLR;
552 if (subLR)
553 subLR->_parent = parent;
554
555 Node* parentParent = parent->_parent;
subL->_right = parent;
558 parent->_parent = subL;
559
560 if (parentParent == nullptr)
561 {
562 _root = subL;
563 subL->_parent = nullptr;
564 }
565 else
566 {
567 if (parent == parentParent->_left)
568 {
569 parentParent->_left = subL;
570 }
571 else
572 {
573 parentParent->_right = subL;
574 }
575
576 subL->_parent = parentParent;
577 }
578
579 }
580
581 void Destroy(Node* root)
582 {
583 if (root == nullptr)
584 return;
585
586 Destroy(root->_left);
587 Destroy(root->_right);
588 delete root;
589 }
590
591 private:
592 Node* _root = nullptr;
593 };