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

目录

前言：
一，库中map和set的大致结构
二，模仿实现
2.1，大致框架
2.2，复用红黑树实现insert接口
 2.3，迭代器iterator的实现
operator++()的实现：
operator--()的实现：
对insert返回值的更改：
2.4，map支持[ ]
2.5，团体代码 
2.6，代码测试

---

前言：

本篇基于上篇【红黑树的实现】，代码也是基于红黑树的代码实现map和set的封装。
一，库中map和set的大致结构

库中部分源代码如下：
   //set
  class set {   
public:
  // typedefs:
    typedef Key key_type;
  typedef Key value_type;
     //...
  private:
  typedef rb_tree<key_type, value_type, 
                  identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing set
  };
  
    //map
  class map {   
public:
    //typedefs:
    typedef Key key_type;
    typedef pair<const Key, T> value_type;
    //...
  private:
  typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing map
  };
  
    //rb_tree红黑树 
  template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{   
  typedef __rb_tree_node<Value>* link_type;
  Value value_field;
};
  
  template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {   
     typedef __rb_tree_node<Value> rb_tree_node;
     typedef rb_tree_node* link_type;
  }；
          通过上面的源码可以分析出，map和set的实现采取了泛型头脑实现。本来map和set各需要一颗红黑树rb_tree来实现的，如许的话两份代码相似部分极多。而采取泛型的头脑，让rb_tree成为一个泛型模板，通过传参的差异决定是 map还是set,如许只需一份rb_tree即可。
        rb_tree是实现key的搜刮场景，还是实现key/value的搜刮场景，是通过第二个模板参数Value决定的，Value的类型确定了，__rb_tree的存储数据的类型就确定了。
        对于set，它的底层封装了rb_tree，第二个模板参数传的是key,实例化出的rb_tree，就是支持key的搜刮场景。
        对于map，它的底层也封装了rb_tree，第二个参数传的是pair<const k,v>,实例化出的rb_tree,就是支持key/value的搜刮场景。
           尚有一点，对于map和set，我们可以知道关键在于底层rb_tree的第二个模板参数，那为什么还要再传第一个模板参数？        
          对于set类型，通过源码可以发现，底层rb_tree的第一个模板参数和第二个模板参数其实是一样的，都是key。但对于map来说，底层rb_tree的第一个模板参数是key，第二个模板参数是pair<k,v>。由于我们在利用rb_tree的查找（find）接口时，是根据key值来查找的，以是需要传第一个模板参数key。可以认为对于set来说时多余的，而对于map来说是必不可少的。为了实今世码的统一，以是set也要传。
  

 

二，模仿实现

2.1，大致框架

set.h

1. #include "RBTree.h"
3. //xg
4. //key
5. namespace xg
6. {
7.         template<class k>
8.         class set
9.         {
10.         public:
11.         //...
12.         private:
13.                 //底层调用红黑树
14.         //k键值是不能修改的，所以 加上const
15.                 RBTree<k, const k> _t;
16.         };
17. }

复制代码

 map.h

1. #include "RBTree.h"
3. //map
4. //pair<k,v>
5. namespace xg
6. {
7.         template<class k,class v>
8.         class map
9.         {
10.         public:
11.         //...
12.         private:
13.                 //底层调用红黑树
14.         //key值不能修改
15.                 RBTree<k, pair<const k, v>> _t;
16.         };
17. }

复制代码

同时，我们也采取库中的方法，对rb_tree进行修改，使其成为一个泛型结构。
rb_tree.h

1. #include <iostream>
2. using namespace std;
5. enum color
6. {
7.         Red,
8.         Black
9. };
10. //由类型T决定红黑树为key还是pair类型
11. template<class T>
12. struct RBTreeNode
13. {
14.         RBTreeNode(const T& data)
15.                 :_left(nullptr)
16.                 ,_right(nullptr)
17.                 ,_parent(nullptr)
18.                 ,_data(data)
19.         {}
20.         RBTreeNode<T>* _left;
21.         RBTreeNode<T>* _right;
22.         RBTreeNode<T>* _parent;
23.         T _data;
24.         color _col;      
25. };
27. //T决定是k还是pair
28. template<class k,class T>
29. class RBTree
30. {
31. public:
32.         typedef RBTreeNode<T> Node;
33.     //...
34. private:
35.         Node* _root=nullptr;
36. }；

复制代码

2.2，复用红黑树实现insert接口

对于set和map，底层直接调用红黑树rb_tree的insert接口。
   //set
  bool insert(const k& key)
{   
    return _t.Insert(key);
}
  //map
  bool insert(const pair<k, v>& kv)
{   
    return _t.Insert(kv);
}
  我们看看rb_tree中的insert接口（部分代码）：

这里需要将参数类型改为T类型，由map和set决定它的类型是key还是pair。
   在插入逻辑中，我们需要比较插入元素的key值，从而找到插入位置。
  对于set，比较的就是key值。但是对于map，比较的就是kv.fist。
  为了满足两种不同的比较，我们可以通过仿函数的方式实现。map和set各实现一个仿函数，用来获取各自的key值。
  通过分析源码可知，map和set的第三个模板参数就是为了解决这个题目。
   set.h

1. #include "RBTree.h"
3. //xg
4. //key
5. namespace xg
6. {
7.         template<class k>
8.         class set
9.         {
10.         public:
11.                 struct SetOfk
12.                 {
13.                         const k& operator()(const k& key)
14.                         {
15.                                 return key;
16.                         }
17.                 };
18.     bool insert(const k& key)
19.     {
20.             return _t.Insert(key);
21.     }
22.         private:
23.                 //底层调用红黑树
24.                 RBTree<k, const k,SetOfk> _t;
25.         };
26. }

复制代码

map.h

1. #include "RBTree.h"
3. //map
4. //pair<k,v>
5. namespace xg
6. {
7.         template<class k,class v>
8.         class map
9.         {
10.         public:
11.                 struct MapOfk
12.                 {
13.                         const k& operator()(const pair<k, v>& kv)
14.                         {
15.                                 return kv.first;
16.                         }
17.                 };
18.         bool insert(const pair<k, v>& kv)
19.         {
20.                 return _t.Insert(kv);
21.         }
22.         private:
23.                 //底层调用红黑树
24.                 RBTree<k, pair<const k, v>,MapOfk> _t;
25.         };
26. }

复制代码

rb_tree的insert部分：
   template<class k,class T,class ValueOfk>
class RBTree{   
  //插入k或者pair类型
bool  Insert(const T& data)
{   
    if (_root == nullptr)
    {   
        _root = new Node(data);
        _root->_col = Black;
        //return pair<Iterator,bool>({_root,_root},true);
        return {Iterator(_root,_root),true};
    }
    ValueOfk kot;
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {   
        //用键值k比较
        if (kot(cur->_data)< kot(data))
        {   
            parent = cur;
            cur = cur->_right;
        }
        else if (kot(cur->_data) >kot(data))
        {   
            parent = cur;
            cur =cur->_left;
        }
        else
        {   
            return false;
        }
    }
        //......旋转+变色
          //......
          //......
  }
  };
   2.3，迭代器iterator的实现

迭代器本质上是对红黑树节点的封装。我们需要实现对*，->的重载，以及对++，--的实现。

1. template<class T,class Ref,class ptr>
2. class RBTreeIterator
3. {
4. public:
5.         typedef RBTreeNode<T> Node;
6.         typedef RBTreeIterator<T, Ref, ptr> Self;
8.         RBTreeIterator(Node* node)
9.                 :_node(node)
10.         {}
11.     //......
12.     //......
13. private:
14.                 //当前节点
15.                 Node* _node;
16. };

复制代码

这里的迭代器实现与list的迭代器实现思绪大致雷同，通过传Ref和ptr两个参数，从而通过一份模板，实现出iterator和const_iterator.
一些操纵符的重载：
   Ref operator*()
{   
    return _node->_data;
}
ptr operator->()
{   
    return &_node->_data;
}
bool operator!=(const Self& s) const
{   
    return s._node != _node;
}
bool operator==(const Self& s) const 
{   
    return s._node == _node;
}
  operator++()的实现：

    （1）起首，我们要知道map和set的迭代器遍历走的是中序遍历，左子树->根节点->右子树，那么begin()应该返回 中序第一个节点，也就是红黑树的最左节点。而对于end(),我们可以让它是空节点。
  （2）迭代器++时，如果it指向的节点的右子树不为空时，说明当前节点已经访问完，下一个节点访问是右子树的中序第一个，也就是右子树的最左节点。
  （3）迭代器++时，如果it指向的节点的右子树为空，说明当前节点已经当前节点所在的子树已经访问完了，要访问的下一个节点在当前节点的祖先里面，要沿着当前节点到根的路径找。并且该节点一定满足孩子是父亲的左子树。
  

 

1. Self operator++()
2. {
3.         //左根右
4.         //当前节点的右子树不为空，继续找右子树的最左节点
5.         if (_node->_right)
6.         {
7.                 Node* cur = _node->_right;
8.                 while ( cur->_left)
9.                 {
10.                         cur = cur->_left;
11.                 }
12.                 _node = cur;
13.         }
14.         else
15.         {
16.                 //当前节点的右子树为空，说明当前子树已经访问完
17.                 //找孩子为祖先左的祖先
18.                 Node* cur = _node;
19.                 Node* parent = cur->_parent;
20.                 while (parent && cur == parent->_right)
21.                 {
22.                         cur = parent;
23.                         parent = cur->_parent;
24.                 }
25.                 _node = parent;
26.         }
27.         return *this;
28. }

复制代码

operator--()的实现：

实现思绪与operator++()相反
   （1）迭代器--时，如果it指向的节点的左子树不为空时，说明当前节点已经访问完，下一个节点访问是左子树的最右节点。
  （2）迭代器--时，如果it指向的节点的左子树为空，说明当前节点已经当前节点所在的子树已经访问完了，要访问的下一个节点在当前节点的祖先里面，要沿着当前节点到根的路径找。并且该节点一定满足孩子是父亲的右子树。
  （3）需要注意的是，大概会遇到end()--的环境，而end()是空节点，会报错。我们可以进行特殊处置惩罚，当it==end()时，让 它等于中序遍历的末了一个节点，也就是红黑树的最右节点。
  而在最右节点的时候，需要根节点，以是需要在iterator中再加入根节点。

1. Self operator--()
2. {
3.         //右根左
4.         if (_node == nullptr) //end()--
5.         {
6.                 Node* cur = _root;
7.                 while (cur->_right)
8.                 {
9.                         cur = cur->_right;
10.                 }
11.                 _node = cur;
12.         }
13.         //当前节点的左子树不为空，继续找左子树的最右节点
14.         else if (_node->_left)
15.         {
16.                 Node* cur = _node->_left;
17.                 while (cur)
18.                 {
19.                         cur = cur->_right;
20.                 }
21.                 _node = cur;
22.         }
23.         else
24.         {
25.                 //左子树为空，当前子树已访问完
26.                 //找孩子为祖先右的节点
27.                 Node* cur = _node;
28.                 Node* parent = cur->_parent;
29.                 while (parent && cur == parent->_left)
30.                 {
31.                         cur = parent;
32.                         parent = cur->_parent;
33.                 }
34.                 _node = parent;
35.         }
36.         return *this;
37. }

复制代码

对insert返回值的更改：

 

库中的insert方法实现了返回pair<iterator,bool>类型，iterator表示 插入节点的迭代器，bool值表示是否插入乐成。 我们只需在返回值处修改，返回iterator迭代器和bool构成的pair类型。
   //插入k或者pair类型
pair<Iterator,bool> Insert(const T& data)
{   
    if (_root == nullptr)
    {   
        _root = new Node(data);
        _root->_col = Black;
        //return pair<Iterator,bool>({_root,_root},true);
        return {Iterator(_root,_root),true};
    }
    ValueOfk kot;
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {   
        //用键值k比较
        if (kot(cur->_data)< kot(data))
        {   
            parent = cur;
            cur = cur->_right;
        }
        else if (kot(cur->_data) >kot(data))
        {   
            parent = cur;
            cur =cur->_left;
        }
        else
        {   
            //return pair<Iterator,bool>({cur,_root},false);
            return { Iterator(cur, _root), false };
        }
    }
      //插入
    cur = new Node(data);
       //cur在下述调解过程中会向上更新变革，需要提前生存下来
    Node* newnode = cur;
    cur->_col = Red;
    if (kot(parent->_data) <kot(data))
        parent->_right = cur;
    else
        parent->_left = cur;
    cur->_parent = parent;
      //颜色处置惩罚+旋转
    while (parent&& parent->_col == Red)
    {   
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left)
        {   
            //    g
            //  p   u
            Node* uncle = grandfather->_right;
            //叔叔存在且为红
            if (uncle && uncle->_col == Red)
            {   
                //变色
                parent->_col = Black;
                uncle->_col = Black;
                grandfather->_col = Red;
                //继续向上处置惩罚
                cur = grandfather;
                parent = cur->_parent;
            }
            else
            {   
                //叔叔不存在或者叔叔为黑
                //    g
                //  p   u
               // c
                //u为黑，则c是之前是黑的
                //u不存在，则c是新插入的
                if (cur == parent->_left)
                {   
                    RotateR(grandfather);
                    parent->_col = Black;
                    grandfather->_col = Red;
                }
                else
                {   
                    //    g
                    //  p   u
                   //     c
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = Black;
                    grandfather->_col = Red;
                }
                break;
            }
        }
        else
        {   
            //   g
            // u   p
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == Red)
            {   
                //变色
                parent->_col = Black;
                uncle->_col = Black;
                grandfather->_col = Red;
                  cur = grandfather;
                parent = cur->_parent;
            }
            else
            {   
                //   g
                // u   p
                //       c
                if (cur == parent->_right)
                {   
                    RotateL(grandfather);
                    parent->_col = Black;
                    grandfather->_col = Red;
                }
                else
                {   
                    //   g
                    // u   p
                    //   c
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = Black;
                    grandfather->_col = Red;
                }
                break;
            }
        }
    }
    _root->_col = Black;
    return pair<Iterator,bool>({newnode,_root},true);
}
  2.4，map支持[ ]

map需要支持operator[ ]来实现对value值的访问及修改。
我们在上述实现了insert接口返回pair<iterator,bool>类型，就可以直接复用。
    v& operator[](const k& key)   
{   
       //key不存在就插入该值和value的缺省值，并返回
       //key存在就得到key位置的iterator
    pair<iterator, bool> ret = insert({ key,v() });
    return ret.first->second;
}
  2.5，团体代码 

rb_tree.h

1. #include <iostream>
2. using namespace std;
5. enum color
6. {
7.         Red,
8.         Black
9. };
10. //由类型T决定红黑树为key还是pair类型
11. template<class T>
12. struct RBTreeNode
13. {
14.         RBTreeNode(const T& data)
15.                 :_left(nullptr)
16.                 ,_right(nullptr)
17.                 ,_parent(nullptr)
18.                 ,_data(data)
19.         {}
20.         RBTreeNode<T>* _left;
21.         RBTreeNode<T>* _right;
22.         RBTreeNode<T>* _parent;
23.         T _data;
24.         color _col;      
25. };
27. template<class T,class Ref,class ptr>
28. class RBTreeIterator
29. {
30. public:
31.         typedef RBTreeNode<T> Node;
32.         typedef RBTreeIterator<T, Ref, ptr> Self;
34.         RBTreeIterator(Node* node,Node* root)
35.                 :_node(node)
36.                 ,_root(root)
37.         {}
38.         Self operator++()
39.         {
40.                 //左根右
41.                 //当前节点的右子树不为空，继续找右子树的最左节点
42.                 if (_node->_right)
43.                 {
44.                         Node* cur = _node->_right;
45.                         while ( cur->_left)
46.                         {
47.                                 cur = cur->_left;
48.                         }
49.                         _node = cur;
50.                 }
51.                 else
52.                 {
53.                         //当前节点的右子树为空，说明当前子树已经访问完
54.                         //找孩子为祖先左的祖先
55.                         Node* cur = _node;
56.                         Node* parent = cur->_parent;
57.                         while (parent && cur == parent->_right)
58.                         {
59.                                 cur = parent;
60.                                 parent = cur->_parent;
61.                         }
62.                         _node = parent;
63.                 }
64.                 return *this;
65.         }
66.         Self operator--()
67.         {
68.                 //右根左
69.                 if (_node == nullptr) //end()--
70.                 {
71.                         Node* cur = _root;
72.                         while (cur->_right)
73.                         {
74.                                 cur = cur->_right;
75.                         }
76.                         _node = cur;
77.                 }
78.                 //当前节点的左子树不为空，继续找左子树的最右节点
79.                 else if (_node->_left)
80.                 {
81.                         Node* cur = _node->_left;
82.                         while (cur)
83.                         {
84.                                 cur = cur->_right;
85.                         }
86.                         _node = cur;
87.                 }
88.                 else
89.                 {
90.                         //左子树为空，当前子树已访问完
91.                         //找孩子为祖先右的节点
92.                         Node* cur = _node;
93.                         Node* parent = cur->_parent;
94.                         while (parent && cur == parent->_left)
95.                         {
96.                                 cur = parent;
97.                                 parent = cur->_parent;
98.                         }
99.                         _node = parent;
100.                 }
101.                 return *this;
102.         }
103.         Ref operator*()
104.         {
105.                 return _node->_data;
106.         }
107.         ptr operator->()
108.         {
109.                 return &_node->_data;
110.         }
111.         bool operator!=(const Self& s) const//请const吃一顿
112.         {
113.                 return s._node != _node;
114.         }
115.         bool operator==(const Self& s) const //请coonst吃一顿
116.         {
117.                 return s._node == _node;
118.         }
119. private:
120.                 //当前节点
121.                 Node* _node;
122.                 Node* _root;//根节点
123. };
125. //T决定是k还是pair
126. template<class k,class T,class ValueOfk>
127. class RBTree
128. {
129. public:
130.         typedef RBTreeNode<T> Node;
131.         typedef RBTreeIterator<T, T&, T*>  Iterator;
132.         typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
133.         //迭代器为中序遍历
134.         Iterator Begin()
135.         {
136.                 //找最左节点
137.                 Node* cur = _root;
138.                 while (cur&&cur->_left)
139.                 {
140.                         cur = cur->_left;
141.                 }
142.                 return Iterator(cur,_root);
143.         }
144.         Iterator End()
145.         {
146.                 return Iterator(nullptr,_root);
147.         }
148.         ConstIterator Begin() const
149.         {
150.                 Node* cur = _root;
151.                 while (cur && cur->_left)
152.                 {
153.                         cur = cur->_left;
154.                 }
155.                 return ConstIterator(cur,_root);
156.         }
157.         ConstIterator End() const
158.         {
159.                 return ConstIterator(nullptr,_root);
160.         }
161.         //插入k或者pair类型
162.         pair<Iterator,bool> Insert(const T& data)
163.         {
164.                 if (_root == nullptr)
165.                 {
166.                         _root = new Node(data);
167.                         _root->_col = Black;
168.                         //return pair<Iterator,bool>({_root,_root},true);
169.                         return {Iterator(_root,_root),true};
170.                 }
171.                 ValueOfk kot;
172.                 Node* cur = _root;
173.                 Node* parent = nullptr;
174.                 while (cur)
175.                 {
176.                         //用键值k比较
177.                         if (kot(cur->_data)< kot(data))
178.                         {
179.                                 parent = cur;
180.                                 cur = cur->_right;
181.                         }
182.                         else if (kot(cur->_data) >kot(data))
183.                         {
184.                                 parent = cur;
185.                                 cur =cur->_left;
186.                         }
187.                         else
188.                         {
189.                                 //return pair<Iterator,bool>({cur,_root},false);
190.                                 return { Iterator(cur, _root), false };
191.                         }
192.                 }
194.                 //插入
195.                 cur = new Node(data);
196.                 Node* newnode = cur;
197.                 cur->_col = Red;
198.                 if (kot(parent->_data) <kot(data))
199.                         parent->_right = cur;
200.                 else
201.                         parent->_left = cur;
202.                 cur->_parent = parent;
204.                 //颜色处理+旋转
205.                 while (parent&& parent->_col == Red)
206.                 {
207.                         Node* grandfather = parent->_parent;
208.                         if (parent == grandfather->_left)
209.                         {
210.                                 //    g
211.                                 //  p   u
212.                                 Node* uncle = grandfather->_right;
213.                                 //叔叔存在且为红
214.                                 if (uncle && uncle->_col == Red)
215.                                 {
216.                                         //变色
217.                                         parent->_col = Black;
218.                                         uncle->_col = Black;
219.                                         grandfather->_col = Red;
220.                                         //继续向上处理
221.                                         cur = grandfather;
222.                                         parent = cur->_parent;
223.                                 }
224.                                 else
225.                                 {
226.                                         //叔叔不存在或者叔叔为黑
227.                                         //    g
228.                                     //  p   u
229.                                    // c
230.                                         //u为黑，则c是之前是黑的
231.                                         //u不存在，则c是新插入的
232.                                         if (cur == parent->_left)
233.                                         {
234.                                                 RotateR(grandfather);
235.                                                 parent->_col = Black;
236.                                                 grandfather->_col = Red;
237.                                         }
238.                                         else
239.                                         {
240.                                                 //    g
241.                                                 //  p   u
242.                                            //     c
243.                                                 RotateL(parent);
244.                                                 RotateR(grandfather);
245.                                                 cur->_col = Black;
246.                                                 grandfather->_col = Red;
247.                                         }
248.                                         break;
249.                                 }
250.                         }
251.                         else
252.                         {
253.                                 //   g
254.                                 // u   p
255.                                 Node* uncle = grandfather->_left;
256.                                 if (uncle && uncle->_col == Red)
257.                                 {
258.                                         //变色
259.                                         parent->_col = Black;
260.                                         uncle->_col = Black;
261.                                         grandfather->_col = Red;
263.                                         cur = grandfather;
264.                                         parent = cur->_parent;
265.                                 }
266.                                 else
267.                                 {
268.                                         //   g
269.                                     // u   p
270.                                         //       c
271.                                         if (cur == parent->_right)
272.                                         {
273.                                                 RotateL(grandfather);
274.                                                 parent->_col = Black;
275.                                                 grandfather->_col = Red;
276.                                         }
277.                                         else
278.                                         {
279.                                                 //   g
280.                                             // u   p
281.                                             //   c
282.                                                 RotateR(parent);
283.                                                 RotateL(grandfather);
284.                                                 cur->_col = Black;
285.                                                 grandfather->_col = Red;
286.                                         }
287.                                         break;
288.                                 }
289.                         }
290.                 }
291.                 _root->_col = Black;
292.                 return pair<Iterator,bool>({newnode,_root},true);
293.         }
294.         void RotateR(Node* parent)
295.         {
296.                 Node* subL = parent->_left;
297.                 Node* subLR = subL->_right;
298.                 Node* pparent = parent->_parent;
300.                 if (subLR)
301.                         subLR->_parent = parent;
302.                 parent->_left = subLR;
303.                 subL->_right = parent;
304.                 parent->_parent = subL;
305.                 if (parent == _root)
306.                 {
307.                         _root = subL;
308.                         _root->_parent = nullptr;
309.                 }
310.                 else
311.                 {
312.                         if (pparent->_left == parent)
313.                                 pparent->_left = subL;
314.                         else
315.                                 pparent->_right = subL;
316.                         subL->_parent = pparent;
317.                 }
318.         }
319.         void RotateL(Node* parent)
320.         {
321.                 Node* subR = parent->_right;
322.                 Node* subRL = subR->_left;
323.                 Node* pparent = parent->_parent;
325.                 parent->_right = subRL;
326.                 if (subRL)
327.                         subRL->_parent = parent;
328.                 parent->_parent = subR;
329.                 subR->_left = parent;
330.                 if (parent == _root)
331.                 {
332.                         _root = subR;
333.                         _root->_parent = nullptr;
334.                 }
335.                 else
336.                 {
337.                         if (pparent->_left == parent)
338.                                 pparent->_left = subR;
339.                         else
340.                                 pparent->_right = subR;
341.                         subR->_parent = pparent;
342.                 }
343.         }
344.         void Inorder()
345.         {
346.                 _Inorder(_root);
347.         }
348.         int Height()
349.         {
350.                 return _Height(_root);
351.         }
352.         int size()
353.         {
354.                 return _size(_root);
355.         }
356.         int _size(Node* root)
357.         {
358.                 if (root == nullptr)
359.                         return 0;
360.                 return _size(root->_left) + _size(root->_right) + 1;
361.         }
362.         int _Height(Node* root)
363.         {
364.                 if (root == nullptr)
365.                         return 0;
366.                 int leftHeight = _Height(root->_left);
367.                 int rightHeight = _Height(root->_right);
368.                 return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
369.         }
370.         void _Inorder(Node* root)
371.         {
372.                 if (root == nullptr)
373.                         return;
374.                 _Inorder(root->_left);
375.                 cout << root->_kv.first << ":" << root->_kv.second << endl;
376.                 _Inorder(root->_right);
377.         }
378. private:
379.         Node* _root=nullptr;
380. };

复制代码

set.h

1. #include "RBTree.h"
3. //xg
4. //key
5. namespace xg
6. {
7.         template<class k>
8.         class set
9.         {
10.         public:
11.                 struct SetOfk
12.                 {
13.                         const k& operator()(const k& key)
14.                         {
15.                                 return key;
16.                         }
17.                 };
18.                 typedef typename RBTree<k, const k, SetOfk>::Iterator iterator;
19.                 typedef typename RBTree<k, const k, SetOfk>::ConstIterator const_iterator;
20.                 iterator begin()
21.                 {
22.                         return _t.Begin();
23.                 }
24.                 iterator end()
25.                 {
26.                         return _t.End();
27.                 }
28.                 const_iterator begin()const
29.                 {
30.                         return _t.Begin();
31.                 }
32.                 const_iterator end() const
33.                 {
34.                         return _t.End();
35.                 }
36.                 pair<iterator,bool> insert(const k& key)
37.                 {
38.                         return _t.Insert(key);
39.                 }
40.         private:
41.                 //底层调用红黑树
42.                 RBTree<k, const k,SetOfk> _t;
43.         };
44. }

复制代码

map.h

1. include "RBTree.h"
3. //map
4. //pair<k,v>
5. namespace xg
6. {
7.         template<class k,class v>
8.         class map
9.         {
10.         public:
11.                 struct MapOfk
12.                 {
13.                         const k& operator()(const pair<k, v>& kv)
14.                         {
15.                                 return kv.first;
16.                         }
17.                 };
18.                 typedef typename RBTree<k, pair<const k, v>, MapOfk>::Iterator iterator;
19.                 typedef typename RBTree<k, pair<const k, v>, MapOfk>::ConstIterator const_iterator;
20.                 iterator begin()
21.                 {
22.                         return _t.Begin();
23.                 }
24.                 iterator end()
25.                 {
26.                         return _t.End();
27.                 }
28.                 const_iterator begin() const
29.                 {
30.                         return _t.Begin();
31.                 }
32.                 const_iterator end() const
33.                 {
34.                         return _t.End();
35.                 }
36.                 pair<iterator,bool> insert(const pair<k, v>& kv)
37.                 {
38.                         return _t.Insert(kv);
39.                 }
40.                  v& operator[](const k& key)  
41.                 {
42.                         pair<iterator, bool> ret = insert({ key,v() });
43.                         return ret.first->second;
44.                 }
45.         private:
46.                 //底层调用红黑树
47.                 RBTree<k, pair<const k, v>,MapOfk> _t;
48.         };
49. }

复制代码

2.6，代码测试

   #include "map.h"
#include "set.h"
#include <string>
  int main()
{   
    xg::set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(3);
    s.insert(2);
    s.insert(6);
      xg::set<int>::iterator sit = s.begin();
    
    while (sit != s.end())
    {   
        cout << *sit << " ";
        ++sit;
    }
    cout << endl;
      for (auto& e : s)
    {   
        cout << e << " ";
    }
    cout << endl;
      xg::map<string, string> dict;
    dict.insert({ "sort", "排序" });
    dict.insert({ "left", "左边" });
    dict.insert({ "right", "右边" });
      dict["left"] = "左边，剩余";
    dict["insert"] = "插入";
    dict["string"];
      xg::map<string, string>::iterator it = dict.begin();
    while (it!=dict.end())
    {   
        // 不能修改first，可以修改second
        //it->first += 'x';
        it->second += 'x';
          cout << it->first << ":" << it->second << endl;
        ++it;
    }
    cout << endl;
      for (auto& kv : dict)
    {   
        cout << kv.first << ":" << kv.second << endl;
    }
      return 0;
}
  

 

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