map、set、multimap和multiset的使用【STL】

1. 容器的类型

C++的容器分为两类，即序列式容器和关联式容器。

1.1 序列式容器

STL序列式容器，它们不会对存储的元素进行排序，元素排列的顺序取决于存储它们的顺序。

常见序列式容器有：array、vector、deque、list 和 forward_list 容器。

1.2 关联式容器

关联式容器在存储元素时会为每个元素再增加一个键key，整体以键值对的方式存储到容器中。相比前者，关联式容器可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。

也就是说，关联式容器的每个元素都是一个键值对，它们之间呈绑定关系，找到其中一个就相当于找到了另一个，而且每个元素（键值对）都是有联系的（大小关系等）。

相比其它类型容器，关联式容器查找、访问、插入和删除指定元素的效率更高。

常见关联式容器有：map、multimap、set、multiset、unordered_set和unordered_map等。

注：

STL中的容器适配器是一个封装了序列容器的类模板，它在序列式容器的基础上实现了自己的功能，提高了代码的可读性。常见容器适配器有：stack、queue、priority_queue。

2. 键值对

• 键：就是存的值的编号；

• 值：就是要存放的数据。

键值对就是一种组织元素之间的对应关系的一种结构，这种结构中一般包含两个成员变量：key（键）和value（值）。

例如英汉词典就是一种键-值关系：一个英文单词对应一个或多个中文意思。

STL专门使用一个结构体pair（配对）表示键值对，源码中的定义如下：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b) : first(a), second(b)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12

相当于一个pair对象储存了一对数据，我们可以通过成员访问符->或.分别访问key和value：

cout << e.first << endl;
cout << e.second << endl;
1
2

3. 底层实现方式

根据不同的使用场景，STL使用了不同的底层结构实现关联式容器：

• 树形结构，如红黑树（平衡搜索树）：set、map、multiset、multimap；
• 哈希结构，如哈希表（散列表）：unordered_set、unordered_map、unordered_multiset、unordered_multimap。

红黑树是一种二叉搜索树，所以它的元素的有序的，哈希结构容器中的元素是无序的。除此之外，树形结构和哈希结构在查找效率上有着本质的区别，即使如此，它们的增删查改的效率仍然是其它容器难以望其项背的。

本文主要针对树形结构的几个容器（set、map、multiset、multimap）进行介绍。

4. set

4.1 set的介绍

通过查阅官方文档，可以知道set容器的特性：

• set底层使用红黑树实现，因此：
  • 它储存的元素是有序的，默认是升序，选用std::less比较；
  • 查找元素的时间复杂度是$O(lo{g}_{2}N)$;
  • 每个元素都是唯一的，具有去重功能；
  • 任何元素都不能被修改（一旦被修改，那么它不再是二叉搜索树），但是可以删除（原因是STL使用了const修饰，如果要修改元素，可以先删除后插入）。
• set储存的键值对中，key是和value相同的，也就是，由于key和value相同，插入元素时只需要一个模版参数Value，不需要构造键值对；

关于set的键值对为什么不把相同的键值设置成一个，在了解map的使用以后便可理解。

4.2 set的使用

set的模板参数列表

头文件

#include 
1

模板参数列表

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
	> class set;
1
2
3
4
5

• Key：set储存元素的类型，实际上在底层中存储的是键值对；
• Compare：set元素默认按照小于方式比较来存储；
• Allocator：set中元素空间的管理方式，使用STL提供的空间配置器管理（暂时不作了解）。

set的构造器

示例：

void set_test1()
{
    set<int> s1;            // 构造int类型的set容器

    set<int> s2(s1);        // 用s1拷贝构造s2

    string str = "hello world";
    set<char> s3(str.begin(), str.end()); // 迭代器区间构造

    set <int, greater<int>> s4; // 构造int类型,比较方式为大于的set容器
}
1
2
3
4
5
6
7
8
9
10
11

set的常用接口

迭代器相关

示例

void set_test2()
{
    set<int> s;
    s.insert(1);
    s.insert(1);        // set去重
    s.insert(2);
    s.insert(5);
    s.insert(4);
    s.insert(3);
    cout << "使用范围for遍历set元素(有序):" << endl;
    for(auto e : s)
    {
        cout << e << endl;
    }
    cout << endl;

    cout << "删除值为1的元素,使用正向迭代器遍历set元素:" << endl;
    s.erase(1);
    set<int>::iterator it = s.begin();
    while(it != s.end())
    {
        cout << *it << " "; // 使用'*'操作符访问set元素
        ++it;
    }
    cout << endl;

    cout << "容器中4的个数:" << endl;
    cout << s.count(4) << endl;

    cout << "容器清空,判空:" << endl;

    s.clear();
    cout << s.empty() << endl;

    cout << "交换两个容器的数据" << endl;
    set<int> tmp = { 7, 8, 9, 10}; // 使用数组初始化set容器
    s.swap(tmp);

    cout << "使用反向迭代器遍历set元素:" << endl;
    set<int>::reverse_iterator rit = s.rbegin();
    while(rit != s.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    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

输出

使用范围for遍历set元素(有序):
1
2
3
4
5

删除值为1的元素,使用正向迭代器遍历set元素:
2 3 4 5
容器中4的个数:
1
容器清空,判空:
1
交换两个容器的数据
使用反向迭代器遍历set元素:
10 9 8 7

5. multiset

官方文档

multiset和set唯一的区别是它允许键值冗余，也就是元素可以被重复储存，即它没有去重功能。因此，它可以用来做单纯的排序。

5.1 成员函数的区别

由于multiset允许键值冗余，所以两种容器的find和count的意义也有所区别。

find

如果multiset中有多个3，想找到第二个3的位置则需要先用find找到第一个3，然后使用重载后的++操作符。

count

count函数的功能无非就是查找，然后遍历计数。

• 对于set而言，只要找到指定元素x，它的个数一定是1，所以可以使复用find函数进行计数；
• 对于multiset而言，find只能返回中序遍历的第一个值为x的元素的迭代器，所以只使用find函数是不足以找到所有值为x的元素的，还需要对红黑树进行其他查找操作，例如重载++操作符。

erase

实际上earse对于两者都可以被认为是删除所有元素，因为set的元素是唯一的。

5.2 示例

void set_test3()
{
    multiset<int> ms = {8, 7, 7, 6, 6, 5, 4, 3, 2};

    for(auto e : ms)
    {
        cout << e << " ";
    }
    cout << endl;

    cout << "删除7:" << endl;
    ms.erase(7);
    for(auto e : ms)
    {
        cout << e << " ";
    }
    cout << endl;

    cout << "找到6的位置:" << endl;
    multiset<int>::iterator it = ms.find(6);

    cout << "查看第一个6前面元素的值:" << endl;
    cout << *(--it) << 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

输出

2 3 4 5 6 6 7 7 8
删除7:
2 3 4 5 6 6 8
找到6的位置:
查看第一个6前面的元素的值:
5

6. map

6.1 map的介绍

通过查阅官方文档，可以知道map的特性：

• map储存的是pair对象，也就是保存键值对的结构体，map的每个元素都是pair对象，它由两部分组成：key和value。键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，并取别名为pair。

• map底层使用红黑树实现，因此：

  • 它储存的元素是有序的，默认是升序，按照key选用std::less比较；
  • 查找元素的时间复杂度是$O(lo{g}_{2}N)$;
  • 每个元素的key都是唯一的，具有去重功能；
  • 任何元素的键key都不能被修改，但是元素的值value可以被修改。原因是红黑树是由key构建的，修改value不会影响树的结构。

• map容器支持下标访问符[]，但是区分数组的[]。map通过[key]找到对应的value。

6.2 map的使用

map的模版参数列表

头文件

#include 
1

模版参数列表

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
1
2
3
4
5
6

• Key：指定键（key）的类型；
• T：指定值（value）的类型；
• Compare：指定排序规则；
• Allocator：指定分配器对象的类型（暂不作了解）。

map的构造器

示例：

void map_test1()
{
    map<int, string> m1;            // 构造键值对为的map容器

    map<int, string> m2(m1);        // 用m1拷贝构造m2

    map<int, string> m3(m2.begin(), m2.end()); // 迭代器区间构造

    map <int, string, greater<int>> m4; //比较方式为大于的map容器
}
1
2
3
4
5
6
7
8
9
10

map的常用接口

在常用的接口中，map新增了一个操作符[]，它可以根据传入的key找到对应的value。除此之外，map的insert也需要着重掌握，主要是理解pair的创建和取出pair中的键或值。

迭代器相关

insert

原型

pair<iterator,bool> insert (const value_type& val);
1

其中，value_type：

typedef pair<const Key, T> value_type;
1

那么，insert实际上也就是（下面的接口都把value_type替换成pair）：

pair<iterator,bool> insert (const pair<const Key, T>& val);
1

也就是说，我们使用insert传入的参数是一个pair结构体对象，所以在插入元素之前，需要先用key和value构造一个pair对象。

在文章的开头，介绍了pair，由于它是一个内置的类，所以可以直接传入参数构造pair对象。

构造匿名对象

void map_test2()
{
    map<int, string> m;

    m.insert(pair<int, string>(1, "一"));
    m.insert(pair<int, string>(4, "四"));
    m.insert(pair<int, string>(2, "二"));
    m.insert(pair<int, string>(3, "三"));

    for(auto e : m)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出

<1, 一>
<2, 二>
< 3, 三>
<4, 四>

但是这样每次都要构造pair对象，比较麻烦。

使用make_pair函数

make_pair是STL中的一个函数模板，使用它无需写出类型，只需要传入参数，即可构造出一个pair对象。

template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
	return (pair<T1, T2>(x, y));
}
1
2
3
4
5

示例

void map_test3()
{
    map<int, string> m;

    m.insert(make_pair(1, "一"));
    m.insert(make_pair(4, "四"));
    m.insert(make_pair(2, "二"));
    m.insert(make_pair(3, "三"));

    for(auto e : m)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出

<1, 一>
<2, 二>
< 3, 三>
<4, 四>

find

原型

iterator find (const pair<const Key, T>& k);
1

由于map是根据pair的key进行插入的，所以查找也要根据key查找。

• 成功：返回元素迭代器；
• 失败：返回end()。

示例

void map_test4()
{
    map<int, string> m;

    m.insert(make_pair(1, "一"));
    m.insert(make_pair(4, "四"));
    m.insert(make_pair(2, "二"));
    m.insert(make_pair(3, "三"));

    auto pos = m.find(3);
    if(pos != m.end())
    {
        cout << pos->second << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出

三

运算符oprator[]重载

原型

mapped_type& operator[] (const pair<const Key, T>& k);
1

返回值类型

mapped_type：

(*((this->insert(make_pair(k, mapped_type()))).first)).second
1

insert的返回值是插入元素的迭代器，那么operator[]其实就是：

mapped_type& operator[] (const key_type& k)
{
	//1、调用insert插入元素
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、取出insert函数返回的迭代器
	iterator it = ret.first;
	//3、取出迭代器对应的元素的value并返回
	return it->second;
}
1
2
3
4
5
6
7
8
9

这个this要不要都可以，因为operator[]是作为map的非静态成员函数存在的，加上this提高了代码的可读性。

使用

即使在string中，operator[]的重载也是类似对数组数据进行随机访问操作的，然而在map中[key]表示返回key对应的value的==引用==，所以我们不仅可以通过operator[]查找，还能修改key对应的value。

• 如果key不存在：operator[]会调用默认构造函数创建一个匿名对象用来构造一个pair，然后插入，接着才会返回它的引用；
• 如果key存在：返回键值为key的元素对应的pair对象的引用。

示例

void map_test5()
{
    map<int, string> m;

    m.insert(make_pair(1, "一"));
    m.insert(make_pair(4, "四"));
    m.insert(make_pair(2, "二"));
    m.insert(make_pair(3, "三"));

    cout << "找到key=1的元素的value:" << endl;
    cout << m[1] << endl;

    cout << "修改key=1的元素的value为\"one\":" << endl;
    m[1] = "one";

    for(auto e : m)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    cout << endl;
}

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

输出

找到key=1的元素的value:
一
修改key=1的元素的value为"one":
<1, one>
<2, 二>
< 3, 三>
<4, 四>

示例

void map_test6()
{
    map<int, string> m;

    m.insert(make_pair(1, "一"));
    m.insert(make_pair(4, "四"));
    m.insert(make_pair(2, "二"));
    m.insert(make_pair(3, "三"));

    for(auto e : m)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }

    cout << endl;
    cout << "删除key为1的元素:" << endl;
    m.erase(1);
    cout << "使用范围for正向遍历:" << endl;
    for(auto e : m)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    cout << endl;

    cout << "插入:<1, \"one\">" << endl;
    m.insert(make_pair(1, "one"));
    cout << "使用反向迭代器遍历:" << endl;
    map<int, string>::reverse_iterator rit = m.rbegin();
    while(rit != m.rend())
    {
        cout << "<" << rit->first << ", " << rit->second << ">" << " ";
        ++rit;
        cout << endl;
    }

    cout << "清空map,";
    m.clear();
    cout << "判空:";
    cout << m.empty() << 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

输出

<1, 一>
<2, 二>
< 3, 三>
<4, 四>

删除key为1的元素:
使用范围for正向遍历:
<2, 二>
< 3, 三>
<4, 四>

插入:<1, “one”>
使用反向迭代器遍历:
<4, 四>
< 3, 三>
<2, 二>
<1, one>
清空map,判空:1

补充

在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过 key找到与key对应的value然后返回其引用，不同的是:当key不存在时，operator[]用默认 value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。

7. multimap

multimap和map的唯一区别就是它允许键值冗余，即可以储存key值重复的元素。因此，两种容器的find和count的意义也有所区别，而且operator[]运算符重载函数也没办法确定返回值，因为同一个key值的元素的value可能有多个，因此在multimap容器中没有实现[]运算符重载函数。

7.1 成员函数的区别

find

如果multimap中有多个3，想找到第二个3的位置则需要先用find找到第一个3，然后使用重载后的++操作符。

count

count函数的功能无非就是查找，然后遍历计数。

• 对于set而言，只要找到指定元素x，它的个数一定是1，所以可以使复用find函数进行计数；
• 对于multimap而言，find只能返回中序遍历的第一个值为x的元素的迭代器，所以只使用find函数是不足以找到所有值为x的元素的，还需要对红黑树进行其他查找操作，例如重载++操作符。

erase

实际上earse对于两者都可以被认为是删除所有元素，因为set的元素是唯一的。

7.2 示例

void map_test7()
{
    multimap<int, string> mm;

    mm.insert(make_pair(1, "一"));
    mm.insert(make_pair(4, "四"));
    mm.insert(make_pair(2, "二"));
    mm.insert(make_pair(2, "二"));
    mm.insert(make_pair(2, "二"));
    mm.insert(make_pair(2, "二"));
    mm.insert(make_pair(3, "三"));

    for(auto e : mm)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    cout << endl;

    cout << "找到第一个key=2的元素的上一个元素" << endl;
    auto pos = mm.find(2);
    cout << "<" << (--pos)->first << ", " << pos->second << ">" << endl;

    cout << "删除所有key=2的元素" << endl;
    mm.erase(2);
    for(auto e : mm)
    {
        cout << "<" << e.first << ", " << e.second << ">" << endl;
    }
    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

输出

<1, 一>
<2, 二>
<2, 二>
<2, 二>
<2, 二>
< 3, 三>
<4, 四>

找到第一个key=2的元素的上一个元素
<1, 一>
删除所有key=2的元素
<1, 一>
< 3, 三>
<4, 四>