用一颗红黑树封装出map和set

一、前言

我们都知道set是K模型的容器，而map是KV模型的容器，但是它俩的底层都是用红黑树实现的，上篇博文中我们模拟实现了一颗红黑树，接下来将对其进行改造，继而用一颗红黑树封装出map和set。本质上map和set其内部的主要功能都是套用了红黑树现成的接口，只是稍作改动即可。

---

二、红黑树模板参数的控制

既然set是K模型，map是KV模型，正如stl库里的map和set，如图所示：

我们发现map和set都是复用的同一颗红黑树，并且实现的都是Key_value模型。

优势：两个容器都可以复用同一颗红黑树，体现泛型编程的好处。

通过这里就能够很清晰的看出库里的节点的存储类型是根据set和map的第二个模板参数决定的，第二个参数存的是什么，节点存的就是什么类型，继而可以满足set和map的需求，而现在又可能引发一个新的问题：

• 既然数据类型看第二个模板参数，那第一个模板参数有何用处？

因为在红黑树中，无可避免会要求实现find等对K有需求的函数，因为find函数主要是通过Key进行查找的，如若省略第一个模板参数，那么map就无法进行find查找操作。

接下来，我们按照库里红黑树的样子对我们自己写的进行一个调整：

//节点类
template <class T>
struct RBTreeNode
{
//三叉链结构
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
    //存储的数据
T _data;
//节点的颜色
Colour _col;
//构造函数
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(Red)
{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

对红黑树的模板参数修改好了，那么我map（KV模型）和set（K模型）自然而然就能够适配了：

• set：

template<class K>
class set
{
public:
//...
private:
RBTree<K, K> _t;
};
1
2
3
4
5
6
7
8

• map：

template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};
1
2
3
4
5
6
7
8

三、模板参数中仿函数的增加

由于现在红黑树的节点类型是T，当容器为set时，T就是键值Key，可以直接进行比较，当容器是map时，T就是pair<Key, Value>，此时不能直接比较，而需要从此键值对中取出Key，再拿Key进行大小比较。但是库里面pair比较大小的方式并不是我们想要的，并且map和set想要比较的数据是不同的。有的同学可能会说，这里我们再写一个比较函数，这是不行的，会和库里面函数冲突。

为了解决这一点，我们可以在红黑树的模板参数上再加一层仿函数，此参数专门用于获得Key类型，而这个仿函数的实现是在map和set内部封装的，通过仿函数，直接从红黑树的节点中取出想要的Key。

注意：map和set需要比较的数据为Key值，但是map和set的结构不同，所以需要在map和set类中实现不同的仿函数。

仿函数，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

具体操作如下：

• map：

template<class K, class V>
class map
{
  struct MapKeyOfT
 {
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
 };
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• set：

template<class K>
class set
{
struct SetKeyOfT
{
  const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
  };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

下面画图演示具体的调用情况：

四、红黑树正向迭代器的实现

红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node; //结点的类型
typedef __TreeIterator<T, Ref, Ptr> Self; //正向迭代器的类型

Node* _node; //正向迭代器所封装结点的指针
};
1
2
3
4
5
6
7
8
9

而在其内部，我们要完成如下操作：

• 1、构造函数
• 2、*和->运算符重载
• 3、!=和==运算符重载
• 4、++运算符重载
• 5、–运算符重载

接下来具体展开演示：

• 1、构造函数

构造函数我们直接通过一个节点的指针从而构造一个正向迭代器即可。

//构造函数
__TreeIterator(Node* node)
:_node(node) //根据所给结点指针构造一个正向迭代器
{}
1
2
3
4

• 2、*和->运算符重载

*运算符就是解引用，直接返回对应节点数据的引用即可；而->运算符返回的是对应节点数据的指针。

Ref operator*()
{
return _node->_data; //返回结点数据的引用
}

Ptr operator->()
{
return &_node->_data; //返回结点数据的指针
}
1
2
3
4
5
6
7
8
9

注意：这里operator->和list中实现是一样的，返回的是地址的原因是连续访问，编译器会把连续的operator->->优化成operator->.

• 3、!=和==运算符重载

!=运算符直接返回两个节点是否不同，而==运算符直接返回两个节点是否相同即可。

//判断两个正向迭代器是否不同
bool operator!=(const Self& s) const
{
return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个
}
//判断两个正向迭代器是否相同
bool operator==(const Self& s) const
{
return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个
}
1
2
3
4
5
6
7
8
9
10

• 4、++运算符重载

++运算符又分前置++和后置++

• 前置++：

首先，这里红黑树迭代器里的++后的值应该是按此位置开始往后中序遍历的下一个。而这个下一个节点的值理应比原先的大，想要找到这个位置，结合二叉搜索树的性质，理应在右子树当中去寻找，而这又要看右子树是否为空，具体操作如下：

• 1、右子树非空：直接遍历找到右子树的最左节点即可
• 2、右子树为空：找祖先里面孩子是父亲左的那个祖先节点，否则继续往上找，直到为空(nullptr)
• 3、当parent遍历到空时，++结束
• 4、注意前置++返回的是++后的值

//前置++
Self& operator++()
{
if (_node->_right) // 右子树不为空
{
// 找右子树的最左节点，使得_node指向此节点
Node* rightmin = _node->_right;
while (rightmin != nullptr)
{
rightmin = rightmin->_left;
}
// 最左节点为空
_node = rightmin;
}
else  //_node->_right == nullptr
{
// 找祖先中，孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
// cur为父亲的左或者父亲为空停止
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• 后置++：

后置++和前置++的唯一区别就在于后置++是返回++前的值，这里只需要在前置++的基础上在一开始把当前节点保存起来，直接调用前置++，最后返回保存的那个节点值即可。

//后置++
Self operator++(int)
{
Self tmp(*this);
return tmp;
}
1
2
3
4
5
6

找孩子是祖先的左的那个祖先节点，这样就实现了非递归，这种非递归的前提是必须为三叉链结构。

• 5、–运算符重载

–运算符又分为前置–和后置–，下面分别讨论：

• 前置–：

–运算符和++运算符相反，–运算符是找比当前位置次小的节点而这个节点，而这又要优先去左子树里寻找，而左子树又分为如下两种情况：

• 左子树为空：找祖先里面孩子是父亲右的那个节点
• 左子树非空：找左子树里最右的节点

//前置--
Self& operator--()
{
if (_node->_left) // 左子树不为空
{
// 找左子树的最右节点，使得_node指向此节点
Node* leftmax = _node->_left;
while (leftmax != nullptr)
{
leftmax = leftmax->_right;
}

_node = leftmax;
}
else // 左子树为空
{
//找祖先中，孩子是父亲右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (cur && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}

return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• 后置–：

注意后置–返回的是–前的值，所以先定义tmp把*this保存起来，再套用前置–函数进行自减，最后返回tmp。

//后置--
Self operator--(int)
{
Self tmp(*this);
return tmp;
}
1
2
3
4
5
6

五、红黑树的反向迭代器的实现

红黑树的反向迭代器实际上就是正向迭代器的一个封装，因此红黑树的反向迭代器就是一个迭代器适配器。

在反向迭代器当中只有一个成员变量，那就是反向迭代器封装的正向迭代器。反向迭代器的中成员函数，都是通过调用正向迭代器对应的函数来完成相应功能的。

//反向迭代器---迭代器适配器
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //反向迭代器的类型
typedef typename Iterator::reference Ref; //结点指针的引用
typedef typename Iterator::pointer Ptr; //结点指针

Iterator _it; //反向迭代器所封装的正向迭代器

//构造函数
ReverseIterator(Iterator it)
:_it(it) //根据所给正向迭代器构造一个反向迭代器
{}

Ref operator*()
{
return *_it; //通过调用正向迭代器的operator*返回结点数据的引用
}
Ptr operator->()
{
return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针
}

//前置++
Self& operator++()
{
--_it; //调用正向迭代器的前置--
return *this;
}
//前置--
Self& operator--()
{
++_it; //调用正向迭代器的前置++
return *this;
}

bool operator!=(const Self& s) const
{
return _it != s._it; //调用正向迭代器的operator!=
}
bool operator==(const Self& s) const
{
return _it == s._it; //调用正向迭代器的operator==
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

需要注意的是，反向迭代器只接收了一个模板参数，即正向迭代器的类型，也就是说，反向迭代器不知道结点的引用类型和结点的指针类型，因此我们需要在正向迭代器当中对这两个类型进行typedef，这样反向迭代器才能通过正向迭代器获取结点的引用类型和结点的指针类型。

//正向迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef Ref reference; //结点指针的引用
typedef Ptr pointer; //结点指针
};
1
2
3
4
5
6
7

六、红黑树的begin()和end()

迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在红黑树的public区域进行typedef。

template <class K, class T, class KeyOfT>
class RBTree
{    
public:
typedef __RBTreeIterator<T, T&, T*> iterator;//普通迭代器
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;//const迭代器
}
1
2
3
4
5
6
7

其实，STL中的红黑树的底层是有一个哨兵位头结点的，如下所示：

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置。

虽说库里的红黑树实现的是带哨兵位头节点的，但毕竟咱这是模拟（但求大概），综上begin()和end()的指向如下总结：

• begin()：指向红黑树中最小节点(即最左侧节点)的位置
• end()：指向红黑树中最大节点(最右侧节点)的下一个位置，即nullptr

//begin()
iterator begin()//找最左节点
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);//调用迭代器的构造函数
}
//end()
iterator end()//返回最右节点的下一个
{
return iterator(nullptr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当然这里最好再实现一个const版本的begin()和end()，为的是普通迭代器和const迭代器都能够使用，其实主要还是set的迭代器不能被修改，无论是普通迭代器还是const迭代器，其内部都是用const迭代器封装的，因此必须实现一个const版本的begin()和end()。

//begin() 
const_iterator begin() const//找最左节点
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);//调用迭代器的构造函数
}
//end()
const_iterator end() const//返回最右节点的下一个
{
return const_iterator(nullptr);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如果 map/set 中想使用红黑树中的迭代器，我们需要在 map/set 中进行声明。

声明如下：

如果想取一个类模板中的一个类型，要使用 typedname 进行声明，告诉编译器这是一个类型，并不是一个静态变量

//如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
//告诉编译器这是一个类型，并不是一个静态变量
typedef typename RBTree<K, pair<K, V>, MapKeyOfvalue>::iterator iterator;
1
2
3

注意：typename受限定符限制，尽量放在public下

七、红黑树的rbegin()和rend()

• rbegin函数返回中序序列当中最后一个结点的反向迭代器，即最右结点。
• rend函数返回中序序列当中第一个结点前一个位置的反向迭代器，这里直接用空指针构造一个反向迭代器。

template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //结点的类型
public:
typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器

reverse_iterator rbegin()
{
//寻找最右结点
Node* right = _root;
while (right&&right->_right)
{
right = right->_right;
}
//返回最右结点的反向迭代器
return reverse_iterator(iterator(right));
}
reverse_iterator rend()
{
//返回由nullptr构造得到的反向迭代器（不严谨）
return reverse_iterator(iterator(nullptr));
}
private:
Node* _root; //红黑树的根结点
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

八、[ ]下标访问运算符重载

我们来看 map 的 [ ] 下标访问操作符，其中 [ ]返回的是mapped_type(pair) 类型。

我们便要对 map 中 insert 的返回值做出修改：

注意，set 中的 insert 也是返回 pair，虽然很反常，但是STL库中确实是这样书写的。

因为只有 set 没有 [ ] 运算符重载，所以我们 set 中不必提供该函数，只用在 map 中提供即可。

首先，我们向 map 中 insert 数据 pair；pair的第一个参数为用户传入的 key 值，第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int，则调用 int的构造函数，如果是 string ，则默认构造 string)。

pair<iterator, bool> result = insert(make_pair(key, V()));
1

然后我们返回迭代器指向的 pair 数据中的second。

//result.first取出迭代器，使用->运算符重载取出data地址，访问second并返回
return result.first->second;
1
2

完整函数如下：

V& operator[](const K& key)
{
pair<iterator, bool> result = insert(make_pair(key, V()));
//如果存在，则插入失败
//如果不存在，则插入数据
//无论是否存在,都返回 second;
return result.first->second;
}
1
2
3
4
5
6
7
8

接下来我们要对红黑树的 Insert 的返回值处进行改动，进而契合 map 的 pair 数据类型。改动有三处，这里贴图大家观察即可。

九、红黑树的Find查找函数

查找的规则很简单，只需要遍历节点即可，具体规则如下：

1. 如果查询的值 > 当前节点值，遍历到右子树查询
2. 如果查询的值 < 当前节点值，遍历到左子树查询
3. 如果查询的值 = 当前节点值，返回当前位置的迭代器
4. 如果循环结束，说明未查询到，返回End()

//Find查找函数
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;//查询的值 > 节点值，-》右子树
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;//查询的值 < 节点值，-》左子树
}
else
{
return iterator(cur);
}
}
return End();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

十、红黑树(修改版)源码链接

链接：RBTree.h · wei/cplusplus - 码云 - 开源中国 (gitee.com)

实现好了红黑树，接下来就可以套用红黑树继而实现map和set的相关功能函数。

十一、set、map模拟实现代码

1.set的代码

namespace set_realize
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator 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)
{
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};

void test_set()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
set<int> s;
for (auto e : a)
{
s.insert(e);
}

set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;

for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

2.map的代码

namespace map_realize
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};

public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator 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 pair<const K, V>& kv)
{
return _t.Insert(kv);
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

void test_map()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map<int, int> m;
for (auto e : a)
{
m.insert(make_pair(e, e));
}
cout << endl;

map<int, int>::iterator it = m.begin();
while (it != m.end())
{
//it->first++;
it->second++;
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;

map<string, int> countMap;
string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
for (auto& e : arr)
{
            // 1、e不在countMap中，插入pair(e, int()),然后返回次数++
// 2、e在countMap中，返回value(次数）的引用，次数++
countMap[e]++;
}

for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86