map、set、multimap和multiset的使用【STL】-阿里云开发者社区

1. 容器的类型

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

1.1 序列式容器

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

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

1.2 关联式容器

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

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

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

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

注：

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

2. 键值对

键：就是存的值的编号；
值：就是要存放的数据。

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

例如英汉词典就是一种键-值<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)
  {}
};

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

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

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<T>比较；
查找元素的时间复杂度是O ( l o g 2 N ) O(log_2N)O(log2N);
每个元素都是唯一的，具有去重功能；
任何元素都不能被修改（一旦被修改，那么它不再是二叉搜索树），但是可以删除（原因是STL使用了const修饰，如果要修改元素，可以先删除后插入）。

set储存的键值对<key, value>中，key是和value相同的，也就是<Value, Value>，由于key和value相同，插入元素时只需要一个模版参数Value，不需要构造键值对；

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

4.2 set的使用

set的模板参数列表

头文件

#include <set>

模板参数列表

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
  > class set;

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

set的构造器

函数声明	功能
`set (const Compare& comp = Compare(), const Allocator& = Allocator());`	构造空的set
`set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );`	用[first, last)区间中的元素构造 set
`set (const set<Key,Compare,Allocator>& x);`	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容器
}

set的常用接口

成员函数	功能
`pair<iterator,bool> insert (const value_type& x)`	插入指定元素x。成功返回<位置,true>，失败说明x已存在，返回<x的位置,false>
`void erase (iterator first, iterator last)`	删除区间[first, last)内的所有元素
`void erase (iterator position)`	删除position位置上的元素
`size_type erase (const key_type& x)`	删除指定值x的元素，返回删除元素的个数
`iterator find (const key_type& x) const`	查找指定元素
`size_type size() const`	获取容器中有效元素的个数
`bool empty () const`	判断容器是否为空
`void clear ()`	清空容器
`void swap (set<Key,Compare,Allocator>& st);`	交换两个容器中的元素
`size_type count (const key_type& x) const`	获取容器中指定元素值的元素个数

迭代器相关

成员函数	功能
`iterator begin()`	获取容器中第一个元素的正向迭代器
`iterator end()`	获取容器中最后一个元素下一个位置的正向迭代器
`const_iterator rbegin()`	同上，但是不能修改迭代器对应的元素
`const_iterator rend()`	同上，但是不能修改迭代器对应的元素
`reverse_iterator rbegin()`	获取容器中最后一个元素的反向迭代器
`reverse_iterator rend()`	获取容器中第一个元素前一个位置的反向迭代器

示例

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;
}

输出

使用范围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

find	功能
set	返回值为x的元素的迭代器
multiset	通过对红黑树中序遍历，返回第一个值为x的元素的迭代器

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

count

count	功能
set	值为x的元素存在则返回1，不存在则返回0
multiset	返回值为x的元素个数

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

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

erase

erase	功能
set	删除值为x的元素
multiset	删除值为x的所有元素

实际上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;
}

输出

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对象，也就是保存键值对<key, value>的结构体，map的每个元素都是pair对象，它由两部分组成：key和value。键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，并取别名为pair。
map底层使用红黑树实现，因此：

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

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

6.2 map的使用

map的模版参数列表

头文件

#include <map>

模版参数列表

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

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

map的构造器

函数声明	功能介绍
`map (const Compare& comp = Compare(), const Allocator& = Allocator());`	构造空的map
`map (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );`	用[first, last)区间中的元素构造 map
`map (const map<Key,Compare,Allocator>& x);`	map的拷贝构造

示例：

void map_test1()
{
    map<int, string> m1;            // 构造键值对为<int, string>的map容器
    map<int, string> m2(m1);        // 用m1拷贝构造m2
    map<int, string> m3(m2.begin(), m2.end()); // 迭代器区间构造
    map <int, string, greater<int>> m4; //比较方式为大于的map容器
}

map的常用接口

函数声明	功能
`pair<iterator,bool> insert ( const value_type& x )`	在map中插入键值对x，注意x是一个键值对，返回值也是键值对。iterator代表新插入元素的位置，bool代表插入成功。
`void erase ( iterator position )`	删除position位置的元素
`size_type erase ( const key_type& x )`	删除键值key为x的元素，返回删除元素的个数
`void erase ( iterator first, iterator last )`	删除[first, last)之间所有元素
`iterator find ( const key_type& x )`	查找键值key为x的元素，找到则返回该元素的迭代器，否则返回end()
`const_iterator find ( const key_type& x ) const`	查找键值key为x的元素，找到则返回该元素的const迭代器，否则返回cend()
`size_type size() const`	返回map容器中有效元素的个数
`bool empty ( ) const`	判断map容器是否为空
`void clear ( )`	清空map容器
`void swap ( map<Key,T,Compare,Allocator>& mp )`	交换两个map容器的数据
`size_type count ( const key_type& x ) const`	返回键值key为x的元素的个数
`mapped_type& operator[] (const key_type& k)`	返回键值key为x对应的value

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

迭代器相关

成员函数	功能
`iterator begin()`	获取容器中第一个元素的正向迭代器
`iterator end()`	获取容器中最后一个元素下一个位置的正向迭代器
`const_iterator cbegin()`	同上，但是不能修改迭代器对应的元素
`const_iterator cend()`	同上，但是不能修改迭代器对应的元素
`reverse_iterator rbegin()`	获取容器中最后一个元素的反向迭代器
`reverse_iterator rend()`	获取容器中第一个元素前一个位置的反向迭代器

insert

原型

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

其中，value_type：

typedef pair<const Key, T> value_type;

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

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

也就是说，我们使用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, 四>

但是这样每次都要构造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));
}

示例

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, 四>

find

原型

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

由于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;
    }
}

输出

三

运算符oprator[]重载

原型

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

返回值类型

mapped_type：

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

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;
}

这个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;
}

输出

找到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, 四>

删除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

find	功能
map	返回key值为x的元素的迭代器
multimap	通过对红黑树中序遍历，返回第一个key值为x的元素的迭代器

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

count

count	功能
map	key值为x的元素存在则返回1，不存在则返回0
multimap	返回key值为x的元素个数

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

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

erase

erase	功能
set	删除值为x的元素
multiset	删除值为x的所有元素

实际上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, 二>

<2, 二>

<2, 二>

<2, 二>

< 3, 三>

<4, 四>

找到第一个key=2的元素的上一个元素

<1, 一>

删除所有key=2的元素

<1, 一>

< 3, 三>

<4, 四>

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

1. 容器的类型

1.1 序列式容器

1.2 关联式容器

2. 键值对

3. 底层实现方式

4. set

4.1 set的介绍

4.2 set的使用

set的模板参数列表

set的构造器

set的常用接口

迭代器相关

示例

5. multiset

5.1 成员函数的区别

find

count

erase

5.2 示例

6. map

6.1 map的介绍

6.2 map的使用

map的模版参数列表

map的构造器

map的常用接口

迭代器相关

insert

原型

构造匿名对象

使用make_pair函数

find

原型

运算符oprator[]重载

原型

返回值类型

使用

示例

补充

7. multimap

7.1 成员函数的区别

find

count

erase

7.2 示例

热门文章

最新文章

相关课程

相关电子书