【C++】STL map_set
慕雪年华

本篇博客让我们来了解一下STL库里面的map/set的使用,并尝试用自己写的红黑树封装一个类似的map/set出来

所用编译器:VS2019

[TOC]

1 set

set就是二叉搜索树中只有单个key的树,它有下面的函数可供使用

1.1 构造函数、迭代器

构造函数、迭代器什么的都很简单,在这里就提到了,和其他STL基本一致

image

image

1.2 节点计数 size

set自带节点计数,我们可以之间获取二叉树中节点的个数,或判断set是否为空

image

1.3 插入删除

插入删除等函数在这里不过多解释,使用方法和string、vector完全一致。如果大家的stl是从string一路学习过来,那么对于这些函数的使用肯定没有问题!

image

插入可以插入单个元素,其返回一个键值对包含这个元素的迭代器+一个bool标识是否插入成功。你还可以用相同类型set的迭代器区间进行插入操作

image

1
2
3
4
5
6
set<int>t1;//定义 set 对象 t1

for (int i = 0; i <= 3; ++i)
{ // 插入 1 2 3 4 5 6
t1.insert(i);
}

删除可以删除:

  • 指定迭代器位置
  • 指定元素
  • 迭代器区间

image

不过对于二叉搜索树而言,删除一直都不是高频操作+效率较低。这也是为什么在实现二叉搜索树的时候,我没有去实现删除操作。

其实主要是删除操作比较难理解,特别是在平衡二叉树中

1.4 查找find

作为搜索二叉树,查找才是最重要的一个函数。该函数会返回一个迭代器,指向元素的位置。

image

如果没有找到这个元素,则返回end迭代器

image

所以我们只需要在使用这个函数的时候,加上对于end()迭代器的判断,只要不等于end说明找到了该元素,进行访问

1
2
3
4
5
6
7
8
9
set<int> v1;
v1.insert(1);
v1.insert(3);
v1.insert(6);
set<int>::iterator it = v1.find(3);
if (it != v1.end())
{
cout << "找到了 "<< *it << endl;
}

因为set是只有key的搜素二叉树,在获取到迭代器之后,我们直接使用*it进行解引用即可得到节点的值

image

而当我们查找内部不存在的元素,也可以得知没有找到

image


1.5 count

这个函数的作用是查找二叉树中value值的个数。但由于默认的set不支持键值冗余,插入相同的键值会被忽略掉。所以这个count在这里只有0和1两个返回值,也只能用来判断该值是否存在。

image

但是因为count需要遍历所有元素,所以在set中,它的效率比find是更差的。

multiset支持键值冗余

这个函数真正起作用的地方是在multiset,人如其名,这是一个支持键值冗余的set,成员函数完全相同。

image


1.6 lower/upper_bound

image

1
2
iterator lower_bound (const value_type& val);   // 返回指向等于或大于指定键值元素的迭代器
iterator upper_bound (const value_type& val); // 返回指向大于指定键值元素的迭代器

这两个函数的作用是返回一个和我们指定的元素相同/或者比指定元素更大(第一个更大的键值)的迭代器

image

image

如果更大的键值或者它本身不存在,就会返回一个end迭代器,这一点和find一样

image

image

set基本用得到的迭代器这里都提了一嘴,接下来康康map

2 map

map同样有一个支持键值冗余的multimap,后面就不说辣

image

前面关于构造函数都暂且不提,直接来看map和set最不一样的地方,插入

2.1 插入

map是一个kvl二叉搜索树,其所有元素都是一个键值对。这就要求我们插入的时候,需要先make_pair建立一个键值关系,再插入进map中。

image

也因为迭代器获取到的是一个键值对,所以访问的时候需要指定键值对的first和second。map是用first进行排序的,所以first是不能修改的,但是second可以

2.2 下标访问/at

map相比于set,最特殊的一点就是它可以用下标直接进行访问

1
map[key]=value;

所以我们可以使用这种方式非常方便的修改value

image

和重载了下标的vector一样,map也有一个at函数(C++11新增)在之前vector的函数中,我没有提到这两个的区别。在这里说一下

image

operator[]和at的主要区别在于operator[]不做边界检查,而at会做边界检查。

  • 由于operator[]不做边界检查, 那怕越界了也会返回一个引用,当然这个引用是错误的引用,如何不小心调用了这个引用对象的方法,会直接导致应用退出
  • 而由于at会做边界检查,如果越界,会抛出异常,应用可以try/catch这个异常,进行异常管理,而应用还能继续运行。

at的使用和下标不太一样,和成员函数的使用方法一致。我们可以来试一试

image

image

在这里如果我们下标访问第11个元素,也不会出问题。因为下标访问会自动创建一个对应的key,而value会调用默认构造函数。int类型也是有默认构造的,返回一个0

image

但如果我们不用下标,直接用at访问第11个元素,就会报debug错误,这便是它们俩的区别所在

image


map和set有区别的地方主要就是上面两个函数,其余都是完全相同

我们直接快进到模式实现吧!

3.模拟实现

这里主要以KV键值对的map为例,set只需要修改keyofValue和它自己的模板参数即可

3.1 康康STL源码

利用红黑树实现map和set之前,我们需要先来思考一个问题:我们自己写的红黑树只有一个KV键值对,那么要怎么判断封装的是map还是只有key的set呢?

  • 先来看看STL库的源码吧!【链接

在map.h的第68行可以看到,实际上库函数里面的map和set都只是封装了红黑树

image

再去找红黑树的头文件,就能看到其与我们实现的不同。这里面的红黑树总共有5个模板参数,除去最后一个用来申请内存空间的alloc,其余4个都有其不同的用处

image

而其中的value是用来构造红黑树节点的参数

image

看起来好像差不多对吧?可再回头看看map,其传入的value是一个pair

image

实际上,库中的红黑树,并不是一个简单的kvl,其k并不是真正用于比较的k,而是依靠第三个模板参数keyofvalue,以及我们传入的比较函数compore来进行比较的

image

说人话就是:RBtree不会判断你是map还是set,而是在map和set的封装端,根据数据的不同类型,传入对应的比较函数,以及键值。

  • 比如set的keyofvalue就是它自己的key
  • 而map的keyofvalue是pair.first

因为库函数里面pair的比较,是会比较first之后,再比较second的。

image

这和我们搜索二叉树的需求不太符合,所以STL库里面就需要写一个比较大小的仿函数,只针对pair的first进行严格比较,以保证稳定性


3.2 模拟实现的基础框架

如果我们自己模拟实现,则可以依据下面的模板进行操作

1
2
3
4
5
// 模板参数V决定红黑树存什么数据
// set: RBTree<K, K>
// map: RBTree<K, pair<K, V>>
// KeyOfV: 取出V对象中key的仿函数
template<class K, class V, class KeyOfV>

而节点类也需要进行对应的修改,不再默认创建一个键值对。而是直接用V来创建一个基本的类型,这就和最基础的搜索二叉树相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class V>
struct RBTreeNode
{
RBTreeNode<V>* _left;
RBTreeNode<V>* _right;
RBTreeNode<V>* _parent;
V _data;

//AVL树的平衡因子,在红黑树中为颜色
Color _col;
//插入节点的时候,默认为红色
//因为这个满足性质3且不会破坏性质4
RBTreeNode(const V& data)
:_data(data),
_left(nullptr),
_right(nullptr),
_parent(nullptr),
_col(RED)
{}
};

3.3 修改插入的代码

因为新增了模板参数,所以这里我们也不能通过kv first进行键值的比较了。我们需要里利用模板参数中的KeyOfV仿函数来进行比较的操作。

在这里,先给出map和set两种KeyOfV仿函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct MapKeyOfV
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;//map是键值对,需要提供kv的first进行比较
}
};
struct SetKeyOfV
{
const K& operator()(const K& key)
{
return key;//set只有一个键值
}
};

有了这个仿函数,我们只需要实例化一个对象,然后将原有的比较替换成仿函数在进行比较即可!

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
pair<iterator,bool> Insert(const V& data)
{
//判断root为空,即空树
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//这里必须要手动给黑色
return make_pair(iterator(_root),true);
}
//kv树的操作
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//利用key来判断,寻找待插入的位置
if (kov(cur->_data)< kov(data))
{
parent = cur;
cur = cur->_right;
}
else if (kov(cur->_data) > kov(data))
{
parent = cur;
cur = cur->_left;
}
else {
return make_pair(iterator(cur), false);//构造一个迭代器返回
}
}
//找到位置后插入节点
cur = new Node(data);
Node* newnode = cur;
if (kov(parent->_data) < kov(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

//插入之后需要向上更新颜色,只有出现连续红色之后才需要更新
while (parent && parent->_col==RED)
{
Node* grandpa = parent->_parent;//祖父
assert(grandpa);//祖父为空不需要进行操作

//p是g的左
if (parent == grandpa->_left)
{
Node* uncle = grandpa->_right;
//情况1:插入后p是红,u存在且是红(不需要旋转)
if (uncle && uncle->_col == RED)
{
uncle->_col = BLACK;
parent->_col = BLACK;
grandpa->_col = RED;//祖父变成红
//继续向上调整
//cur = cur->_parent;
//parent = parent->_parent;
cur = grandpa;
parent = cur->_parent;
}
else//(uncle && uncle->_col == BLACK)
{
//情况2:插入后p为红,u存在且为黑(需要单旋)
if (cur == parent->_left)
{
RotateR(grandpa);//因为p在g的左边,所以右旋
parent->_col = BLACK;
grandpa->_col = RED;
}
else//cur == parent->_right
{
//情况3:不是在同一侧,双旋
// g
// p
// c
RotateL(parent);
RotateR(grandpa);
grandpa->_col = RED;//祖父改成红色
cur->_col = BLACK;//自己成为了这里的根,需要改成黑的
}
break;
}
}
else {
Node* uncle = grandpa->_left;
//情况1:插入后p是红,u存在且是红(不需要旋转)
if (uncle && uncle->_col == RED)
{
uncle->_col = BLACK;
parent->_col = BLACK;
grandpa->_col = RED;//祖父变成红
//继续向上调整
cur = grandpa;
parent = cur->_parent;
}
else//(uncle && uncle->_col == BLACK)
{
//情况2:插入后p为红,u存在且为黑(需要单旋)
if (cur == parent->_right)
{
RotateL(grandpa);//因为p在g的左边,所以右旋
parent->_col = BLACK;
grandpa->_col = RED;
}
else//cur == parent->_left
{
//情况3:不是在同一侧,双旋
// g
// p
// c
RotateR(parent);
RotateL(grandpa);
grandpa->_col = RED;//祖父改成红色
cur->_col = BLACK;//自己成为了这里的根,需要改成黑的
}
break;
}
}
}

//不管是什么情况,最后都把根改成黑,符合条件2
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}

这里说明一下为何要把返回值替换成键值对。因为在实际操作的时候,我们需要获取道新插入元素的迭代器(迭代器的模拟实现会在后面提及),以方便在插入后进行修改value的操作。

比如我们默认插入的是一个空字符串,在进行一些判断之后,再重新给这个键值的value进行修改(仅限于map的情况)

如果不返回一个迭代器,那么想修改这个键值,就只能通过find函数查找后再进行修改,相对有些麻烦。

3.4 迭代器✨

这一部分是比较难理解的迭代器操作,主要就是在一个二叉树中应该如何进行迭代器的++/--操作。

3.4.1 加减操作

如果你看过我之前的stl博客,那么你应该还记得,我们的模拟实现迭代器其实就是用指针来进行的。迭代器的使用方法也和指针相差无几。

在此处我们选择使用中序遍历来进行迭代器的操作。中序遍历的基本情况就是左根右,只不过我们这里不再能使用递归进行操作了,而需要使用迭代的方法。

image

上图中cur遍历到了右子树,其左右子树都为空。这时候我们需要返回到的是根节点,准确来说是祖父节点——吗?要是cur的父亲prev不是g节点的左子树,我们就不能直接返回g进行打印!而需要返回g的左子树。

总结出来的规律如下,当我们执行++操作的时候:

  • 如果右节点为空,当前节点是父亲的右侧,就需要继续往上找(我们需要找到父亲左侧的那个节点)
  • 如果右子树不为空,找右子树的最左节点。

在上图中,prev就是g的左子树,所以我们只需要找到prev就行了。然后因为我们的prev的右子树已经遍历过,所以这时候就需要往上。因为g是根节点,所以就需要返回g的右子树的最左节点,也就是下图中的位置

image

而当我们做到最右侧的节点时,再次++的时候其实已经遍历完了。这时候右子树为空,开始往上找父亲是祖父左的哪一个。这时候会一直找到根,而根的父亲为空,停止遍历

image

转换为代码如下

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
Self& operator++()
{
if (_node->_right == nullptr)
{
Node* cur = _node;
Node* parent = cur->_parent;
//只要当前节点是父亲的右侧,就需要继续往上找
//我们需要找到是父亲左侧的那个节点。
while (parent && parent->_right == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
//如果不符合while的条件,就说明
//1 父亲为空(根)
//2 如果cur是父亲的左,那就直接将node设置为父亲
_node = parent;
}
else
{
//右子树不为空,找右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
//最左节点
_node = subLeft;
}

return *this;
}

进行--操作的时候则是完全相反的情况。我们需要找到父亲是祖父节点右边的那一个。如果父亲是祖父的左,那就继续往上找。

image

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
Self& operator--()
{
if (_node->_left == nullptr)
{
Node* cur = _node;
Node* parent = cur->_parent;
//依据中序的顺序,--就是和++反过来。需要找节点是父亲的右边的哪一个
//如果是父亲的左就继续往上找
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
//指向当前的父亲
_node = parent;
}
else
{
// 左子树的最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}

_node = subRight;
}

return *this;
}

3.4.2 套上完整迭代器模板

完成了迭代器的加减操作后,我们只需要套上之前模拟实现的类似模板,再添加参数到红黑树的类中。即可配套好一个迭代器!

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
template<class V, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<V> Node;
typedef __RBTreeIterator<V, Ref, Ptr> Self;
Node* _node;//当前指向的节点

__RBTreeIterator(Node* node)
:_node(node)
{}

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

//省略++和--的代码

bool operator!=(const Self& s) const
{
return _node != s._node;
}

bool operator==(const Self& s) const
{
return _node == s->_node;
}
};

完整代码请参考我的Gitee仓库

3.4.3 添加参数到红黑树类中

我们需要把迭代器写入红黑树的类,并附上普通迭代器和const的两个版本,提供beginend函数即可。

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
//迭代器封装,const和普通版本
typedef __RBTreeIterator<V, V&, V*> iterator;
typedef __RBTreeIterator<V, const V&, const V*> const_iterator;
iterator Begin()
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}

return iterator(subLeft);
}

iterator End()
{
return iterator(nullptr);
}

const_iterator Begin() const
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}

return const_iterator(subLeft);
}

const_iterator End() const
{
return const_iterator(nullptr);
}

image

可以看到,迭代器已经可以正常使用了!

这里的测试环节最好把自己写的map套进一个命名空间中,不然就会用到stl库里面的map

迭代器写好之后,范围for也是可以用的


3.5 重载下标

map非常特殊的一点就是,可以直接用map[key]=value来修改value的内容。我们模拟实现的时候当然不能落下这个了!

其实操作起来非常简单。我们只需要直接调用插入,如果键值存在也会返回当前键值的迭代器。键值不存在就能直接插入,返回新插入元素的迭代器。这也是之前为啥insert函数没有直接用bool做插入的返回值的原因

1
2
3
4
5
6
//重载下标
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;//返回的是一个引用,所以可以直接修改
}

因为我们返回的是V的引用,所以可以直接用=进行修改!

测试一下,咩有问题 OJBK👍

image

set的模拟实现更为简单,这里就不贴出来辣!大家可以去我的gitee看源码,有啥问题可以评论提出!


4.更多操作

4.1 用set得出两组数据的重合处

假设有两个文件,我们现需要找到这两个文件的重合处

  • 设置两个set,分别插入两个文件的内容
  • 同时遍历两个set(从小到大)
    • 如果两个set的key相同,则取出这个相同值,两个set一起++
    • 如果不相同,则++那个小的key
  • 其中一个set结束遍历,即代表重合处查找完毕!

结语

最近感觉自己真的很忙,但又不知在忙什么。事情一个接着一个,虽然学校的课不算多,但事情真的没少多少。

有些事情自己又有拖延症,再加上作息不规律(指下午一睡睡3h),浪费了好多时间……

image