红黑树模拟实现STL中的map与set——C++

目次
  
  1.红黑树的迭代器
  1.2.迭代器的界说
  1.3.operator++()
  1.4*,->,!=
  2.改造红黑树
  类模板
  构造
  赋值运算符重载
  析构函数
  查找
  begin（）/end（）
  插入
  3.map的模拟实现
  4.set的模拟实现
  总结
  

---

  1.红黑树的迭代器

  （本篇代码基于我写的红黑树的实现这篇博客）
  迭代器的利益是可以方便遍历，是数据布局的底层实现与用户透明。假如想要给红黑树增长迭代器，必要思量以下题目：
  begin()与end()： STL明白规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树举行中序遍历后， 可以得到一个有序的序列，因此：begin()可以放在红黑树中最末节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？ 能否给成nullptr呢？答案是行不通的，由于对end()位置的迭代器举行--利用，必须要能找末了一个元素，此处就不可，因此最好的方式是将end()放在头结点的位置：
  

  1.2.迭代器的界说

  

  迭代器我们采取类模板的方式来举行，Ref是T的引用，Ptr是T的指针

1. typedef __RBTreeIterator<T,const T&,const T*> ConstIterator;

复制代码

Node是我们红黑树的节点，Self是我们迭代器范例本身，构造我们也就选一个红黑树的节点举行拷贝构作育好了。
  1.3.operator++()

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

复制代码

迭代器的出现是为了我们更方便地去举行增删查改，以是我们要能有规律的查找元素，我们来分析++的逻辑，我们的遍历是按照升序的方式，以是，我们要找到比当前节点大的下一个节点，我们先来看一下当前节点是否有右子树，有的话就往右子树的最小左子树去找，谁人节点就是我们要找的下一个节点。假如我们的当前节点右子树是空，我们就要不绝往上更新，直到为左子树然后它的父亲就是下一个节点了。
  1.4*,->,!=

1. //*
2.                 Ref operator*()
3.                 {
4.                         return _node->_data;
5.                 }
6.                 //->
7.                 Ptr operator->()
8.                 {
9.                         return &_node->_data;
10.                 }
11.                 //!=
12.                 bool operator!=(const Self& s)
13.                 {
14.                         return _node != s._node;
15.                 }

复制代码

解引用就把数据返归去，->就把数据的所在返归去，！=就是判断迭代器访问的与你指定的是否相称。
  2.改造红黑树

  迭代器构建出来了，我们也要对红黑树举行一些简朴的改造，我来讲一些新参加的部门。
  类模板

1. template<class K, class T, class KeyofT>        class RBTree        {                typedef RBTreeNode<T> Node;        public:                typedef __RBTreeIterator<T, T&, T*> Iterator;                typedef __RBTreeIterator<T,const T&,const T*> ConstIterator;

复制代码

我们的类模板新增长了一个范例KeyofT，这是我们map和set要传入的一个仿函数，具体是什么我背面会讲，它的功能是取出key键值。下面，我们重定名红黑树节点，迭代器也重定名了两个，一个是const修饰的，一个是平常的。
  构造

1.                 //构造函数
2.                 RBTree() = default;
4.                 //拷贝构造函数
5.                 RBTree(const RBTree<K, T, KeyofT>& t)
6.                 {
7.                         _root = Copy(t._root);
8.                 }
9.                 Node* Copy(Node* root)
10.                 {
11.                         if (root == nullptr)
12.                         {
13.                                 return nullptr;
14.                         }
15.                         Node* newroot = new Node(root->_data);
16.                         newroot->_col = root->_col;
18.                         newroot->_left = Copy(root->_left);
19.                         if (newroot->_left)       
20.                                 newroot->_left->_parent = newroot;
21.                         newroot->_right = Copy(root->_right);
22.                         if (newroot->_right)       
23.                                 newroot->_right->_parent = newroot;
24.                        
25.                         return newroot;
26.                 }

复制代码

构造方面我们要编写拷贝构造，以是我们在无参构造背面加一个default关键字，让编译器表现默认天生。然后我们的拷贝构造采取递归的方式将每一个节点拷贝下来，我们利用前序遍历的方式将节点拷贝下来就好了。
  赋值运算符重载

1.                 //赋值运算符重载
2.                 RBTree<K, T, KeyofT>& operator=(RBTree<K, T, KeyofT> t)
3.                 {
4.                         swap(_root, t._root);
5.                         return *this;
6.                 }

复制代码

赋值运算符重载我们复用拷贝构造函数的代码，我们的参数会自动调用拷贝构造，然后我们就只要将两根节点交换就可以了。
  析构函数

1.                 //析构函数
2.                 ~RBTree()
3.                 {
4.                         Destroy(_root);
5.                         _root = nullptr;
6.                 }
7.                 void Destroy(Node* root)
8.                 {
9.                         if (root == nullptr)
10.                         {
11.                                 return;
12.                         }
13.                         Destroy(root->_left);
14.                         Destroy(root->_right);
15.                         delete(root);
16.                         root = nullptr;
17.                 }

复制代码

析构我们则是采取后序遍历的方法举行递归删除。
  查找

1.                 //Find()
2.                 Iterator Find(const T& data)
3.                 {
4.                         KeyofT kot;
5.                         Node* parent = nullptr;
6.                         Node* cur = _root;
8.                         while (cur)
9.                         {
10.                                 if (kot(data) > kot(cur->_data))
11.                                 {
12.                                         parent = cur;
13.                                         cur = cur->_right;
14.                                 }
15.                                 else if (kot(data) < kot(cur->_data))
16.                                 {
17.                                         parent = cur;
18.                                         cur = cur->_left;
19.                                 }
20.                                 else
21.                                 {
22.                                         return Iterator(cur);
23.                                 }
24.                         }
25.                         return end();
26.                 }

复制代码

查找我们就利用二叉搜索树的规则去查找就可以了（要查找的节点比当前节点小就往左，大就往右），kot是仿函数范例的变量，它的作用是返回key值，由于我们插入的时间是按key值来举行插入的。
  begin（）/end（）

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

复制代码

begin和end我们分别计划了const修饰的宁静常的两组，平常的begin我们就找最小的节点，也就是最左边，end我们就是一个空节点，我们返回的时间都是复用迭代器的拷贝构造，const修饰的版本思绪也是千篇一律的，只不外加上了const修饰。
  插入

1.                 //插入
2.                 pair<Iterator,bool> Insert(const T& data)
3.                 {
4.                         if (_root == nullptr)
5.                         {
6.                                 _root = new Node(data);
7.                                 _root->_col = BLACK;
8.                                 return make_pair(Iterator(_root),true) ;
9.                         }
11.                         KeyofT kot;
12.                         Node* parent = nullptr;
13.                         Node* cur = _root;
15.                         while (cur)
16.                         {
17.                                 if (kot(data) > kot(cur->_data))
18.                                 {
19.                                         parent = cur;
20.                                         cur = cur->_right;
21.                                 }
22.                                 else if (kot(data) < kot(cur->_data))
23.                                 {
24.                                         parent = cur;
25.                                         cur = cur->_left;
26.                                 }
27.                                 else
28.                                 {
29.                                         return make_pair(Iterator(cur), false);
30.                                 }
31.                         }
32.                         cur = new Node(data);
33.                         cur->_col = RED;
34.                         if (kot(data) < kot(parent->_data))
35.                         {
36.                                 parent->_left = cur;
37.                         }
38.                         else
39.                         {
40.                                 parent->_right = cur;
41.                         }
42.                         cur->_parent = parent;
43.                         //调整红黑树
44.                         //parent是黑的也直接结束
45.                         while (parent && parent->_col == RED)
46.                         {
47.                                 //关键看叔叔
48.                                 Node* grandf = parent->_parent;
49.                                 if (parent == grandf->_left)
50.                                 {
51.                                         Node* uncle = grandf->_right;
52.                                         //叔叔存在且为红，变色即可
53.                                         if (uncle && uncle->_col == RED)
54.                                         {
55.                                                 uncle->_col = parent->_col = BLACK;
56.                                                 grandf->_col = RED;
57.                                                 //继续往上处理
58.                                                 cur = grandf;
59.                                                 parent = cur->_parent;
60.                                         }
61.                                         else//叔叔不存在，或则存在且为黑
62.                                         {
63.                                                 //    g
64.                                                 //  p   u
65.                                                 //c
66.                                                 if (cur == parent->_left)
67.                                                 {
68.                                                         parent->_col = BLACK;
69.                                                         grandf->_col = RED;
70.                                                         RotateR(grandf);
71.                                                 }
72.                                                 //    g
73.                                                 //  p   u
74.                                                 //    c
75.                                                 else
76.                                                 {
77.                                                         RotateL(parent);
78.                                                         grandf->_col = RED;
79.                                                         cur->_col = BLACK;
80.                                                         RotateR(grandf);
81.                                                 }
82.                                                 break;
83.                                         }
84.                                 }
85.                                 else
86.                                 {
87.                                         Node* uncle = grandf->_left;
88.                                         //叔叔存在且为红，变色即可
89.                                         if (uncle && uncle->_col == RED)
90.                                         {
91.                                                 uncle->_col = parent->_col = BLACK;
92.                                                 grandf->_col = RED;
93.                                                 //继续往上处理
94.                                                 cur = grandf;
95.                                                 parent = cur->_parent;
96.                                         }
97.                                         else//叔叔不存在，或则存在且为黑
98.                                         {
99.                                                 //    g
100.                                                 //  u   p
101.                                                 //        c
102.                                                 if (cur == parent->_right)
103.                                                 {
104.                                                         parent->_col = BLACK;
105.                                                         grandf->_col = RED;
106.                                                         RotateL(grandf);
107.                                                 }
108.                                                 //    g
109.                                                 //  u   p
110.                                                 //    c
111.                                                 else
112.                                                 {
113.                                                         RotateR(parent);
114.                                                         grandf->_col = RED;
115.                                                         cur->_col = BLACK;
116.                                                         RotateL(grandf);
117.                                                 }
118.                                                 break;
119.                                         }
120.                                 }
121.                         }
122.                         _root->_col = BLACK;
123.                         return make_pair(Iterator(cur), true);
124.                 }

复制代码

插入大抵的思绪还是没有变的，我就夸大一下改变的部门。
  我们先是将插入函数的返回值范例给改变了，将它改成了pair布局体范例，这是为了我们后续对map和set举行封装，然后我们的返回都要用make_pair将数据变革成pair布局体的方式举行返回，然后我们还要创建一个KeyofYT范例的对象，它的作用我前面已经说过了，是利用仿函数来返回key值举行巨细比力。别的的代码就跟我红黑树那一篇文章的代码千篇一律了。
  红黑树方面的代码的改进就以上这些
  3.map的模拟实现

  map的底层布局就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可

1. #pragma once
2. #include"_RBtree.h"
4. namespace Mybit
5. {
6.         template<class K,class V>
7.         class map
8.         {
9.                 struct KeyofT
10.                 {
11.                         const K& operator()(const pair<K,V>& kv)
12.                         {
13.                                 return kv.first;
14.                         }
15.                 };
16.         public:
17.                 typedef typename RBTree<K, pair<const K, V>, KeyofT>::Iterator iterator;
18.                 typedef typename RBTree<K,pair<const K, V>, KeyofT>::ConstIterator const_iterator;
19.                 iterator begin()
20.                 {
21.                         return _t.begin();
22.                 }
23.                 iterator end()
24.                 {
25.                         return _t.end();
26.                 }
27.                 const_iterator begin() const
28.                 {
29.                         return _t.begin();
30.                 }
31.                 const_iterator end() const
32.                 {
33.                         return _t.end();
34.                 }
35.                 pair<iterator, bool> insert(const pair<K, V>& kv)
36.                 {
37.                         return _t.Insert(kv);
38.                 }
39.                 iterator find(const K& key)
40.                 {
41.                         return _t.Find(make_pair(key, V()));
42.                 }
43.                 V& operator[](const K& key)
44.                 {
45.                         pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
46.                         return ret.first->second;
47.                 }
48.         private:
49.                 RBTree<K, pair<const K, V>, KeyofT> _t;
50.         };

复制代码

由于map是key-value模子，以是我们的类模板设置了两个范例，分别是K，和V，在map类内里我们终于看到了KeyOfT这个布局体，这个布局体内里我们就计划了一个括号重载，这就是我们的仿函数的用法，你可以看到它返回的是我们的键值，接下来我们对红黑树的两个迭代器范例再次举行重定名，如许我们在测试主函数内里利用的时间格式就跟利用标准库的时间是千篇一律的。接下来还是我们的两组begin，end，我们直接调用红黑树的两组begin和end就可以了，接下来是insert插入，我们还是调用红黑树的插入，find也是云云，末了是我们的方括号重载。
  要弄懂方括号重载我们得先知道方括号的作用，方括号我们一样寻常都是把想要让步调员看到的数据给取出来，在map中我们想看到的大多数时间都不是key值，而是value值，value值就在我们的pair布局体中的second变量里；或则说这个地区的数据是空的，那么我们还可以把数据添加进去。因此，我们的方括号重载也是如许去计划的，先添加（假如已经存在了它就会添加失败，直接把原来的数据赋值给ret，不清晰的话，各人可以看红黑树插入的代码就会清晰了），然后我们再返回second数据就可以了。
  这就是我们map的简朴封装，我们再来总结一点，封装封装，都是封装给别的人看的，目标是让其在利用的时间可以或许更加规范，更加简朴，以是你会发现，我们这里举行封装的时间，他们的接口名称，返回值范例险些都是一样的。

1.         //利用【】简单计数
2.         void test_map2()
3.         {
4.                 string arr[] = { "字符串", "数组", "指针", "列表", "字典", "字典", "字典",
5. "字符串", "字符串", "字符串", "数组","数组","数组", "数组","数组" };
6.                 map<string, int> countMap;
7.                 for (auto& e : arr)
8.                 {
9.                         countMap[e]++;
10.                 }
12.                 for (auto& kv : countMap)
13.                 {
14.                         cout << kv.first << ":" << kv.second << endl;
15.                 }
16.                 cout << endl;
17.                 map<string, int>::iterator it = countMap.find("字符串");
18.                 cout << (*it).first << endl;
19.         }

复制代码

上述代码就是我们简朴的一个计数测试代码，都是根本的语法，而且各人会发现我们的利用跟标准库是千篇一律的。给各人看看运行效果。
  

  由于我们的计数是重零开始的以是它会比我们预想的少一个，但是假如必要的话我们可以自行将他们添加上去。
  4.set的模拟实现

  set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来(具体实现可参考map)。

1. #pragma once
2. #include"_RBtree.h"
4. namespace Mybit
5. {
6.         template<class K>
7.         class set
8.         {
9.                 struct KeyofT
10.                 {
11.                         const K& operator()(const K& key)
12.                         {
13.                                 return key;
14.                         }
15.                 };
16.         public:
17.                 typedef typename RBTree<K, const K, KeyofT>::Iterator iterator;
18.                 typedef typename RBTree<K,const K, KeyofT>::ConstIterator const_iterator;
19.                 iterator begin()
20.                 {
21.                         return _t.begin();
22.                 }
23.                 iterator end()
24.                 {
25.                         return _t.end();
26.                 }
27.                 const_iterator begin() const
28.                 {
29.                         return _t.begin();
30.                 }
31.                 const_iterator end() const
32.                 {
33.                         return _t.end();
34.                 }
35.                 pair<iterator,bool> insert(const K& key)
36.                 {
37.                         return _t.Insert(key);
38.                 }
39.                 iterator find(const K& key)
40.                 {
41.                         return _t.Find(key);
42.                 }
43.         private:
44.                 RBTree<K,const K,KeyofT> _t;
45.         };

复制代码

看完了map的封装再来看set的封装就会发现，封装思绪就是千篇一律的，唯一有几点改动是由于set的模子是key模子，以是它的仿函数返回有点不一样，由于它不必要我们的pair布局体，【】在此时也不是很必要了，我们直接测试看看。

1.         void test_set()
2.         {
3.                 set<int> s;
4.                 s.insert(2);
5.                 s.insert(5);
6.                 s.insert(3);
7.                 s.insert(4);
8.                 s.insert(1);
9.                 set<int>::iterator it = s.begin();
10.                 cout << *it << endl;
11.                 while (it != s.end())
12.                 {
13.                         cout << *it << " ";
14.                         ++it;
15.                 }
16.                 cout << endl;
17.                 set<int> copy = s;
18.                 for (auto e : copy)
19.                 {
20.                         cout << e << " ";
21.                 }
22.                 cout << endl;
23.                 cout << *(s.find(1)) << endl;
24.         }

复制代码

  总结

  我们的map和set的简朴封装到这里就竣事了，我们要弄清晰红黑树的迭代器的重要功能的实现头脑，还要红黑树的一些修改，最告急的尚有map和set的封装头脑，弄清晰这些，各人在一样平常生存中对map和set的利用就会更加得心应手。
  我们实现map和set的简朴封装并不是为了说再造一个跟库里的一样的，这没须要，我们只必要相识重要功能的实现原理就充足了，如许当你再看到map和set的时间就不会看它是一团迷雾了。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金