【红黑树封装map和set】—— 我与C++的不解之缘（二十六） ...

一、相识源码

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

复制代码

部分源码如上，我们通过源码可以看到源码中rb_tree使用了泛型头脑实现；此中rb_tree是实现key搜刮场景还是实现key/value的搜刮场景不是写死的，而是通过了第二个模版参数来决定的。
上面意思呢？
   

• set在实例化时第二个模版参数给的是key，而map实例化时第二个模版参数给的是pair<const K, T>，如许我们一颗红黑树就可以实现两种效果，既可以实现key搜刮场景的set也可以实现key/value搜刮场景map。
  
• 这里源码当中，模版参数用T来取代了value，而此中value_type并不是我们之前key/value场景中的value；源码当中value_type反而是红黑树节点中存储的数据范例。（如许set存储的数据就是K，而map中存储的数据就是pair<K , V>）。
  
• 这里第二个模版参数Value已经控制了红黑树节点中存储的数据范例，那为什么还需要第一个模版参数呢？，就比如set模版参数传的是K,K；这里主要缘故原由还是因为map和set中find和erase函数的参数都是Key,所以需要第一个模版参数传给find和erase。
  
• 对于set而言两个参数都是key，而对于map而言，map的insert是pair对象，但是find和erase的是Key对象。
  

  二、 封装实现map和set

我们复用之前实现的红黑树来实现set和map；我们需要举行一系列的修改，让我们实现的红黑树可以完成复用，让我们实现出来set和map。
要复用整个框架，我们首先要举行一些修改；这里对比源码当中实现方法举行一系列修改和完善：
   

• 模版参数：红黑树的模版参数要用三个<class K , class T , class KeyOfT>，可以或许举行insert操作。
  
• 迭代器：RBTree要实现出迭代器，可以或许举行遍历。
  
• map中的[]： 对于map，我们要实现[]运算符重载；那个实现其完整的[]操作。
  

  1. 复用红黑树框架，实现insert

首先来看如何去封装，实现map和set的框架。
模版参数：
对于三个模版参数K , T , KeyOfT，各有什么用呢？
   key和T就不多表明了，在相识源码时已经知道了它们的作用。
  KeyOfT的作用是什么？

   首先我们知道，红黑树我们修改成K , T布局之后，我们在insert的时间函数参数是T，我们并不知道T是K还是pair<K , V>；那我们如何去举行巨细比较呢？
  这里我们要看一下pair<K , V>的比较方法是什么

可以看到库里面pair的比较方法是先比较first，first大就大，first小就小；假如相称那就比较second。
我们不想要如许的比较方法，我们就想要单纯的比较K也就是first。（这里我们想要的比较方法，关键我们需要拿到K）
现在，KeyOfT的作用就体现出来了：
   KeyOfT是一个仿函数，它重载了operator()方法，它的作用就是返回T中的K；
  假如T是K那就直接返回，假如T是pair<K , V>就返回此中的K。
  那我们在RBTree怎么知道T要返回的是什么呢？（显然是无法知道的，但是上层复用的肯定知道；所以我们就在set和map中写好SetKeyOfT和MapKeyOfT，将其放在第三个模版参数的位置；如许我们在下层RBTree中就可以或许拿到T中的K了。
支持insert实现

现在就对于上述来修改我们之前实现好的RBTree代码。
RBTree.h:

1. enum Color
2. {
3.         RED,
4.         BLACK,
5. };
6. //RBTree节点
7. template<class T>
8. struct RBTreeNode
9. {
10.         RBTreeNode* _left;
11.         RBTreeNode* _right;
12.         RBTreeNode* _parent;
13.         T _data;
14.         Color _col;
15.         RBTreeNode(const T& data)
16.                 :_data(data)
17.                 , _left(nullptr)
18.                 , _right(nullptr)
19.                 , _parent(nullptr)
20.                 ,_col(RED)
21.         {}
22. };
23. template<class K, class T,class KOT>
24. class RBTree
25. {
26.         typedef RBTreeNode<T> Node;
27. public:
28.         bool insert(const T& data)
29.         {
30.                 if (_root == nullptr)//空树插入
31.                 {
32.                         _root = new Node(data);
33.                         _root->_col = BLACK;
34.                         return true;
35.                 }
36.                 //非空树插入
37.                 Node* tail = _root;
38.                 Node* parent = nullptr;
39.                 KOT kot;
40.                 while (tail)
41.                 {
42.                         if (kot(data) > kot(tail->_data))
43.                         {
44.                                 parent = tail;
45.                                 tail = tail->_right;
46.                         }
47.                         else if (kot(data) < kot(tail->_data))
48.                         {
49.                                 parent = tail;
50.                                 tail = tail->_left;
51.                         }
52.                         else
53.                         {
54.                                 return false;
55.                         }
56.                 }
57.                 Node* cur = new Node(data);
58.                 cur->_col = RED;//新插入节点一定是红色
59.                 cur->_parent = parent;
60.                 if (kot(cur->_data) > kot(parent->_data))
61.                 {
62.                         parent->_right = cur;
63.                 }
64.                 else if (kot(cur->_data) < kot(parent->_data))
65.                 {
66.                         parent->_left = cur;
67.                 }
68.                 //这里当父节点存在且为红色时就一直循环
69.                 //直到父节点不存在或者父节点的颜色为黑色
70.                 while (parent && parent->_col == RED)
71.                 {
72.                         Node* grandfather = parent->_parent;
73.                         if (parent == grandfather->_left)
74.                         {
75.                                 //
76.                                 Node* uncle = grandfather->_right;
77.                                 if (uncle && uncle->_col == RED) //变色
78.                                 {
79.                                         uncle->_col = parent->_col = BLACK;
80.                                         grandfather->_col = RED;
81.                                         cur = grandfather;
82.                                         parent = cur->_parent;
83.                                 }
84.                                 else
85.                                 {
86.                                         if (cur == parent->_left)//右单旋+变色
87.                                         {
88.                                                 RevoleR(grandfather);
89.                                                 parent->_col = BLACK;
90.                                                 grandfather->_col = RED;
91.                                                 break;
92.                                         }
93.                                         else//左右双旋+变色
94.                                         {
95.                                                 RevoleL(parent);
96.                                                 RevoleR(grandfather);
97.                                                 cur->_col = BLACK;
98.                                                 grandfather->_col = RED;
99.                                                 break;
100.                                         }
101.                                 }
102.                         }
103.                         else
104.                         {
105.                                 Node* uncle = grandfather->_left;
106.                                 if (uncle && uncle->_col == RED)//变色
107.                                 {
108.                                         uncle->_col = parent->_col = BLACK;
109.                                         grandfather->_col = RED;
110.                                         cur = grandfather;
111.                                         parent = cur->_parent;
112.                                 }
113.                                 else
114.                                 {
115.                                         if (cur == parent->_right)//左单旋+变色
116.                                         {
117.                                                 RevoleL(grandfather);
118.                                                 parent->_col = BLACK;
119.                                                 grandfather->_col = RED;
120.                                                 break;
121.                                         }
122.                                         else //右左双旋+变色
123.                                         {
124.                                                 RevoleR(parent);
125.                                                 RevoleL(grandfather);
126.                                                 cur->_col = BLACK;
127.                                                 grandfather->_col = RED;
128.                                                 break;
129.                                         }
130.                                 }
131.                         }
132.                 }
133.                 _root->_col = BLACK;
134.                 return true;
135.         }
136. private:
137.         void RevoleR(Node* parent) //右单旋
138.         {
139.                 Node* subl = parent->_left;
140.                 Node* sublr = parent->_left->_right;
142.                 parent->_left = sublr;
143.                 if (sublr)
144.                         sublr->_parent = parent;
145.                 Node* ppNode = parent->_parent;
146.                 parent->_parent = subl;
147.                 subl->_parent = ppNode;
148.                 if (ppNode == nullptr)
149.                 {
150.                         _root = subl;
151.                 }
152.                 else
153.                 {
154.                         if (parent == ppNode->_left)
155.                         {
156.                                 ppNode->_left = subl;
157.                         }
158.                         else if (parent->_right)
159.                         {
160.                                 ppNode->_right = subl;
161.                         }
162.                 }
163.         }
164.         void RevoleL(Node* parent)//左单旋
165.         {
166.                 Node* subr = parent->_right;
167.                 Node* subrl = parent->_right->_left;
169.                 parent->_right = subrl;
170.                 if (subrl)
171.                         subrl->_parent = parent;
173.                 Node* ppNode = parent->_parent;
174.                 parent->_parent = subr;
175.                 subr->_left = parent;
176.                 subr->_parent = ppNode;
177.                 if (ppNode == nullptr)
178.                 {
179.                         _root = subr;
180.                 }
181.                 else
182.                 {
183.                         if (parent == ppNode->_left)
184.                         {
185.                                 ppNode->_left = subr;
186.                         }
187.                         else if (parent == ppNode->_right)
188.                         {
189.                                 ppNode->_right = subr;
190.                         }
191.                 }
192.         }
193.         Node* _root = nullptr;
194. };

复制代码

myset.h：

1. namespace HL
2. {
3.         template<class K>
4.         class set
5.         {
6.                 struct SetKeyOfT
7.                 {
8.                         const K& operator()(const K& key)
9.                         {
10.                                 return key;
11.                         }
12.                 };
13.         public:
14.                 set() {}
15.                 bool insert(const K& k)
16.                 {
17.                         return _rb.insert(k);
18.                 }
19.         private:
20.                 RBTree<K,const K, SetKeyOfT> _rb;
21.         };
22. }

复制代码

mymap.h：

1. namespace HL
2. {
3.         template<class K,class V>
4.         class map
5.         {
6.                 struct MapKeyOfT
7.                 {
8.                         const K& operator()(const pair<const K,V>& kv)
9.                         {
10.                                 return kv.first;
11.                         }
12.                 };
13.         public:
14.                 map() {}
15.                 bool insert(const pair<const K, V>& kv)
16.                 {
17.                         return _rb.insert(kv);
18.                 }
19.         private:
20.                 RBTree<K, pair<const K, V>, MapKeyOfT> _rb;
21.         };
22. }

复制代码

2. 实现iterator，完成set和map的迭代器遍历

对于RBTree的迭代器，它和list的迭代器好坏常相似的，都是对于节点的指针举行封装来实现的；通过实现运算符重载来让迭代器可以或许像指针那样一样的访问举动。
运算符重载

这里先简单来实现operator==、operator!=、operator*、operator->等这些简单一些的运算符重载

1. template<class T,class Ref, class Ptr>
2. struct RBTreeIterator
3. {
4.         typedef RBTreeNode<T> Node;
5.         typedef RBTreeIterator<T, Ref, Ptr> Self;
6.         Node* _node;
7.         RBTreeIterator(Node* node,Node* root)
8.                 :_node(node)
9.         {}
10.         Ref operator* ()
11.         {
12.                 return _node->_data;
13.         }
14.         Ptr operator->()
15.         {
16.                 return &_node->_data;
17.         }
18.         bool operator==(const Self& it)
19.         {
20.                 return _node == it._node;
21.         }
22.         bool operator!=(const Self& it)
23.         {
24.                 return _node != it._node;
25.         }
26. };

复制代码

operator++重载实现

这里operator++和operator--是重点也是难点；我们知道map和set的迭代器走的都是中序遍历因为中序遍历是有序的。
而中序遍历（左子树->根节点->右子树），那我们begin()返回的就是中序遍历的第一个节点位置的迭代器。
**迭代器++**的核心逻辑就是，遍历完当前位置，应该遍历哪一个位置？
所以我们就只需要考虑下一个节点位置在哪即可。
   中序遍历的顺序：左子树->根节点->右子树
  我们优先考虑该节点的右子树，（因为遍历到当前节点时，就说明左子树和当前节点已经遍历完了）；
  

• **假如当前节点的右子树不为空：**那就找到其右子树中的最左节点，该节点就是当前节点中序遍历的下一个节点。
  
• 假如当前节点的右子树为空： 假如当前节点的右子树为空，就代表当前节点所在子树已经访问完了；要访问下一个节点在当前节点的祖先当中，我们就需要沿着当前节点到根节点的路径中寻找下一个节点。
  
• 那如何去找呢？实在很简单，我们根据左子树->根节点->右子树这个顺序可以发现：假如当前节点等于其父亲节点的左子树，就说明父节点的左子树访问完了，要接着访问父节点；假如当前节点等于其父节点的右子树，就说明父节点的右子树已经访问完了，也说明以父节点为根节点的子树也访问完了，就要继续向上在祖先中寻找下一个节点。
  

  这里当前节点的右子树不为空很好理解，当前节点的右子树为空可能不太好理解，现在就来推理一个树来辅助理解一下。
现在有如许一个红黑树：

现在就从begin()位置（中序第一个）开始遍历：

所以迭代器++的过程如上图所示，现在就来实现operator++()代码：

1.         Self& operator++()
2.         {
3.                 if (_node->_right)
4.                 {
5.                         Node* cur = _node->_right;
6.                         while (cur && cur->_left)
7.                         {
8.                                 cur = cur->_left;
9.                         }
10.                         _node = cur;
11.                 }
12.                 else
13.                 {
14.                         Node* parent = _node->_parent;
15.                         Node* cur = _node;
16.                         while (parent && cur == parent->_right)
17.                         {
18.                                 cur = parent;
19.                                 parent = cur->_parent;
20.                         }
21.                         _node = parent;
22.                 }
23.                 return *this;
24.         }

复制代码

operator--重载实现

对于operator--的实现，大致思绪和operator++是一样的；只是我们要对特别情况举行处置惩罚
   

• 在上述operator++过程中，我们end()返回的是nullptr的迭代器，所以我们在实现operator--时就要对这一特别情况举行处置惩罚：假如当前位置是nullptr，我们就要让当前迭代器执行末了一个位置。
  
• 那末了一个位置在哪？首先，begin()是中序遍历（左子树->根节点->右子树）的第一个（也是该树的最左节点），那中序遍历末了一个节点就是该树的最右节点，所以我们按照(右子树->根节点->左子树)的顺序去找该树的最右节点，也就是中序遍历的末了一个节点。
  
• 那这里题目就又出来了，我们当前迭代器位置是nullptr，我们该如何找到该树的最右节点呢？（这里源码当中是使用了一个哨兵位来充当end()的位置，我们并没有去实现这个哨兵位）；那如何找到该树的最右节点呢？
  
• 实在很简单，我们这里让迭代器多了一个成员_root表示当前树的根节点，如许我们在对end()位置--的时间，就可以通过根节点找到该树的最右节点。
  
• 其他的思绪都和operator++一样，这里就不举行分析了。
  

  直接来看operator--的代码实现：

1.         Self& operator--()
2.         {
3.                 if (_node == nullptr)
4.                 {
5.                         Node* cur = _root;
6.                         while (cur && cur->_right)
7.                         {
8.                                 cur = cur->_right;
9.                         }
10.                         _node = cur;
11.                 }
12.                 else
13.                 {
14.                         if (_node->_left)
15.                         {
16.                                 Node* cur = _node->_left;
17.                                 while (cur->_left)
18.                                 {
19.                                         cur = cur->_right;
20.                                 }
21.                                 _node = cur;
22.                         }
23.                         else
24.                         {
25.                                 Node* parent = _node->_parent;
26.                                 Node* cur = _node;
27.                                 while (parent && cur == parent->_left)
28.                                 {
29.                                         cur = parent;
30.                                         parent = cur->_parent;
31.                                 }
32.                                 _node = parent;
33.                         }
34.                 }
35.                 return *this;
36.         }

复制代码

  这里迭代器相比于上面写的多了一个成员变量root，所以终极实现的简易迭代器代码如下：

1. template<class T, class Ref, class Ptr>struct RBTreeIterator{        typedef RBTreeNode<T> Node;        typedef RBTreeIterator<T, Ref, Ptr> Self;        Node* _node;        Node* _root;        RBTreeIterator(Node* node, Node* root)                :_node(node)                , _root(root)        {}        Ref operator* ()        {                return _node->_data;        }        Ptr operator->()        {                return &_node->_data;        }        bool operator==(const Self& it)        {                return _node == it._node;        }        bool operator!=(const Self& it)        {                return _node != it._node;        }        Self& operator++()
2.         {
3.                 if (_node->_right)
4.                 {
5.                         Node* cur = _node->_right;
6.                         while (cur && cur->_left)
7.                         {
8.                                 cur = cur->_left;
9.                         }
10.                         _node = cur;
11.                 }
12.                 else
13.                 {
14.                         Node* parent = _node->_parent;
15.                         Node* cur = _node;
16.                         while (parent && cur == parent->_right)
17.                         {
18.                                 cur = parent;
19.                                 parent = cur->_parent;
20.                         }
21.                         _node = parent;
22.                 }
23.                 return *this;
24.         }
25.         Self& operator--()
26.         {
27.                 if (_node == nullptr)
28.                 {
29.                         Node* cur = _root;
30.                         while (cur && cur->_right)
31.                         {
32.                                 cur = cur->_right;
33.                         }
34.                         _node = cur;
35.                 }
36.                 else
37.                 {
38.                         if (_node->_left)
39.                         {
40.                                 Node* cur = _node->_left;
41.                                 while (cur->_left)
42.                                 {
43.                                         cur = cur->_right;
44.                                 }
45.                                 _node = cur;
46.                         }
47.                         else
48.                         {
49.                                 Node* parent = _node->_parent;
50.                                 Node* cur = _node;
51.                                 while (parent && cur == parent->_left)
52.                                 {
53.                                         cur = parent;
54.                                         parent = cur->_parent;
55.                                 }
56.                                 _node = parent;
57.                         }
58.                 }
59.                 return *this;
60.         }
61. };

复制代码

RBTree、set和map的迭代器实现

RBTree
这里begin()返回的是中序遍历的第一个位置，也就是红黑树的最左节点；而end()返回的则是nullptr位置

1.         typedef RBTreeIterator<T, T&, T*> Iterator;
2.         typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
3.         Iterator begin()
4.         {
5.                 Node* cur = _root;
6.                 while (cur && cur->_left)
7.                 {
8.                         cur = cur->_left;
9.                 }
10.                 return Iterator(cur,_root);
11.         }
12.         Iterator end()
13.         {
14.                 return Iterator(nullptr,_root);
15.         }
16.         ConstIterator begin() const
17.         {
18.                 Node* cur = _root;
19.                 while (cur && cur->_left)
20.                 {
21.                         cur = cur->_left;
22.                 }
23.                 return Iterator(cur, _root);
24.         }
25.         ConstIterator end() const
26.         {
27.                 return Iterator(nullptr, _root);
28.         }

复制代码

set和map
   这里set和map迭代器实现起来就简单很多了，直接对RBTree的迭代器举行复用即可，而begin()和end()就直接举行调用即可。
  set

1.                 typedef typename RBTree<K,const K, SetKeyOfT>::Iterator iterator;
2.                 typedef typename RBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator;
3.                 iterator begin()
4.                 {
5.                         return _rb.begin();
6.                 }
7.                 iterator end()
8.                 {
9.                         return _rb.end();
10.                 }
11.                 const_iterator begin() const
12.                 {
13.                         return _rb.begin();
14.                 }
15.                 const_iterator end() const
16.                 {
17.                         return _rb.end();
18.                 }

复制代码

  这里typedef typename RBTree<K, K, SetKeyOfT>::Iterator iterator;中typename是告诉编译器这是个范例，让编译器在类模版实例化之后去取此中的范例名（因为编译器是按需实例化的，不加可能会报错）C++语法是运行如许的。
  map

1.                 typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::Iterator iterator;
2.                 typedef typename RBTree<K,pair<const K,V>,MapKeyOfT>::ConstIterator const_iterator;
3.                 iterator begin()
4.                 {
5.                         return _rb.begin();
6.                 }
7.                 iterator end()
8.                 {
9.                         return _rb.end();
10.                 }
11.                 const_iterator begin() const
12.                 {
13.                         return _rb.begin();
14.                 }
15.                 const_iterator end() const
16.                 {
17.                         return _rb.end();
18.                 }

复制代码

测试set和map

这里来测试一下实现的set和map的迭代器

1. void test_map()
2. {
3.         HL::map<int, int> mp;
4.         mp.insert({ 1,1 });
5.         mp.insert({ 2,2 });
6.         mp.insert({ 3,3 });
7.         mp.insert({ 4,4 });
8.         mp.insert({ 5,5 });
9.         auto it = mp.begin();
10.         while (it != mp.end())
11.         {
12.                 cout << it->first << ": " << it->second<< endl;
13.                 ++it;
14.         }
15.         cout << endl;
16.         it = mp.end();
17.         while (it != mp.begin())
18.         {
19.                 --it;
20.                 cout << it->first << ": " << it->second << endl;
21.         }
22.         cout << endl;
23. }
24. void test_set()
25. {
26.         HL::set<int> st;
27.         st.insert(1);
28.         st.insert(2);
29.         st.insert(3);
30.         st.insert(4);
31.         st.insert(5);
32.         st.insert(6);
33.         st.insert(7);
34.         st.insert(8);
35.         auto it = st.begin();
36.         while (it != st.end())
37.         {
38.                 cout << *it << " ";
39.                 ++it;
40.         }
41.         cout << endl;
42.         it = st.end();
43.         while (it != st.begin())
44.         {
45.                 --it;
46.                 cout << *it << " ";
47.         }
48.         cout << endl;
49. }
50. int main()
51. {
52.         test_set();
53.         test_map();
54.         return 0;
55. }

复制代码

运行效果：

可以看到我们已经完成set和map的迭代器遍历。
三、map的operator[]的实现

   对于map的operator[]，我们知道它有两种功能：
  一是key存在，通过key查找value，返回value的引用；
  二是假如key不存在进插入key，其对应的value是缺省值，然后返回value的引用；
  所以这里不管key是否存在，我们都要返回对应的value的引用；
我们在实现时就肯定需要调用insert函数，先来看一下库里面map的insert函数

可以看到，相比于我们现在实现的insert，库里面返回的是pair<iterator , bool>范例，如许我们就能拿到插入位置的迭代器。
所以我们在实现的时间也需要如许去设计；（再结合一下insert的逻辑，假如插入值存在，我们就可以返回当前位置迭代器和false，如许就达到了我们想要的效果）
修改后的RBTreeinsert：

1.         pair<Iterator, bool> insert(const T& data)
2.         {
3.                 if (_root == nullptr)//空树插入
4.                 {
5.                         _root = new Node(data);
6.                         _root->_col = BLACK;
7.                         //return true;
8.                         return make_pair(Iterator(_root,_root), true);
9.                 }
10.                 //非空树插入
11.                 Node* tail = _root;
12.                 Node* parent = nullptr;
13.                 KOT kot;
14.                 while (tail)
15.                 {
16.                         if (kot(data) > kot(tail->_data))
17.                         {
18.                                 parent = tail;
19.                                 tail = tail->_right;
20.                         }
21.                         else if (kot(data) < kot(tail->_data))
22.                         {
23.                                 parent = tail;
24.                                 tail = tail->_left;
25.                         }
26.                         else
27.                         {
28.                                 //return false;
29.                                 return make_pair(Iterator(tail, _root), false);
30.                         }
31.                 }
32.                 Node* cur = new Node(data);
33.                 Node* newnode = cur;
34.                 cur->_col = RED;//新插入节点一定是红色
35.                 cur->_parent = parent;
36.                 if (kot(cur->_data) > kot(parent->_data))
37.                 {
38.                         parent->_right = cur;
39.                 }
40.                 else if (kot(cur->_data) < kot(parent->_data))
41.                 {
42.                         parent->_left = cur;
43.                 }
44.                 //这里当父节点存在且为红色时就一直循环
45.                 //直到父节点不存在或者父节点的颜色为黑色
46.                 while (parent && parent->_col == RED)
47.                 {
48.                         Node* grandfather = parent->_parent;
49.                         if (parent == grandfather->_left)
50.                         {
51.                                 //
52.                                 Node* uncle = grandfather->_right;
53.                                 if (uncle && uncle->_col == RED) //变色
54.                                 {
55.                                         uncle->_col = parent->_col = BLACK;
56.                                         grandfather->_col = RED;
57.                                         cur = grandfather;
58.                                         parent = cur->_parent;
59.                                 }
60.                                 else
61.                                 {
62.                                         if (cur == parent->_left)//右单旋+变色
63.                                         {
64.                                                 RevoleR(grandfather);
65.                                                 parent->_col = BLACK;
66.                                                 grandfather->_col = RED;
67.                                                 break;
68.                                         }
69.                                         else//左右双旋+变色
70.                                         {
71.                                                 RevoleL(parent);
72.                                                 RevoleR(grandfather);
73.                                                 cur->_col = BLACK;
74.                                                 grandfather->_col = RED;
75.                                                 break;
76.                                         }
77.                                 }
78.                         }
79.                         else
80.                         {
81.                                 Node* uncle = grandfather->_left;
82.                                 if (uncle && uncle->_col == RED)//变色
83.                                 {
84.                                         uncle->_col = parent->_col = BLACK;
85.                                         grandfather->_col = RED;
86.                                         cur = grandfather;
87.                                         parent = cur->_parent;
88.                                 }
89.                                 else
90.                                 {
91.                                         if (cur == parent->_right)//左单旋+变色
92.                                         {
93.                                                 RevoleL(grandfather);
94.                                                 parent->_col = BLACK;
95.                                                 grandfather->_col = RED;
96.                                                 break;
97.                                         }
98.                                         else //右左双旋+变色
99.                                         {
100.                                                 RevoleR(parent);
101.                                                 RevoleL(grandfather);
102.                                                 cur->_col = BLACK;
103.                                                 grandfather->_col = RED;
104.                                                 break;
105.                                         }
106.                                 }
107.                         }
108.                 }
109.                 _root->_col = BLACK;
110.                 //return true;
111.                 return make_pair(Iterator(newnode, _root), true);
112.         }

复制代码

map中实现的operator[]：

1.                 pair<iterator, bool> insert(const pair<const K, V>& kv)
2.                 {
3.                         return _rb.insert(kv);
4.                 }
5.                 V& operator[](const K& key)
6.                 {
7.                         pair<iterator, bool> ret = insert({ key, V() });
8.                         return ret.first->second;
9.                 }

复制代码

  到这里我们实现的map就可以使用[]去访问了。
  测试
这里来测试一下我们实现的是否到达了我们预期的效果：

1. void test_map()
2. {
3.         HL::map<string, string> mp;
4.         mp.insert({ "sort", "排序" });
5.         mp.insert({ "left", "左边" });
6.         mp.insert({ "right", "右边" });
7.         mp["left"] = "左边，剩余";
8.         mp["insert"] = "插入";
9.         mp["string"];
10.         HL::map<string,string>::iterator it = mp.begin();
11.         while (it != mp.end())
12.         {
13.                 it->second += 'x';
14.                 cout << it->first << ":" << it->second << endl;
15.                 ++it;
16.         }
17.         cout << endl;
18. }

复制代码

  这里简单使用map中[]，是可以到达我们的预期效果的。
  

四、map和set的构造函数与析构函数

   对于构造函数和析构函数，相对来说就非常简单了。
  

对于构造函数，我们直接举行复用insert即可。

1.                 set() {}
2.                 template<class InputIterator>
3.                 set(InputIterator first, InputIterator last)
4.                 {
5.                         while (first != last)
6.                         {
7.                                 _rb.insert(*first);
8.                                 first++;
9.                         }
10.                 }
11.                 set(const set& x)
12.                 {
13.                         for (const auto& e : x)
14.                         {
15.                                 _rb.insert(e);
16.                         }
17.                 }

复制代码

map和set一样直接调用RBTree中的insert即可。

1.                 map() {}
2.                 template<class InputIterator>
3.                 map(InputIterator first, InputIterator last)
4.                 {
5.                         while (first != last)
6.                         {
7.                                 _rb.insert(*first);
8.                                 first++;
9.                         }
10.                 }
11.                 map(const set& x)
12.                 {
13.                         for (const auto& e : x)
14.                         {
15.                                 _rb.insert(e);
16.                         }
17.                 }

复制代码

  对于析构函数，我们就要实现RBTree的析构函数，然后在map和set中举行调用；这里就使用递归来释放每一个节点。
  RBTree.h

1.         ~RBTree()
2.         {
3.                 Destroy(_root);
4.         }
5.         void Destroy(Node* root)
6.         {
7.                 if (root == nullptr)
8.                         return;
9.                 Destrot(root->_left);
10.                 Destrot(root->_right);
11.                 delete root;
12.         }

复制代码

  而map和set就直接delete即可，编译器会主动调用RBTree的析构函数。
  五、总结

这里并没有去实现erase删除功能，只是简单模拟了map和set的实现。
这里简单总结几个点：
   

• 首先就是一个红黑树框架来封装实现map和set
  
• 其次就是模拟迭代器的实现，整个思绪（重点：operator++和operator--）
  
• 然后就是map中operator[]的特别功能。
  
• 末了就是构造函数、析构函数等这些简单的复用。
  

  这里并没有实现像size、find、empty、count等函数，这些就比较简单。
到这里本篇内容就结束了，盼望对你有所资助。
制作不易，感谢大佬的支持。
我的博客即将同步至腾讯云开辟者社区，约请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。