文章目录

• 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 示例

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 
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比较；
  • 查找元素的时间复杂度是O(log2N)O(log_2N)O(log2​N);
  • 每个元素都是唯一的，具有去重功能；
  • 任何元素都不能被修改（一旦被修改，那么它不再是二叉搜索树），但是可以删除（原因是STL使用了const修饰，如果要修改元素，可以先删除后插入）。
• set储存的键值对中，key是和value相同的，也就是，由于key和value相同，插入元素时只需要一个模版参数Value，不需要构造键值对；

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

4.2 set的使用

set的模板参数列表

头文件

#include 

模板参数列表

template,class Allocator = std::allocator> class set;

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

set的构造器

示例：

void set_test1()
{set s1;            // 构造int类型的set容器set s2(s1);        // 用s1拷贝构造s2string str = "hello world";set s3(str.begin(), str.end()); // 迭代器区间构造set > s4; // 构造int类型,比较方式为大于的set容器
}

set的常用接口

迭代器相关

示例

void set_test2()
{set 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::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 tmp = { 7, 8, 9, 10}; // 使用数组初始化set容器s.swap(tmp);cout << "使用反向迭代器遍历set元素:" << endl;set::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

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

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

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

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

6.2 map的使用

map的模版参数列表

头文件

#include 

模版参数列表

template,class Allocator = std::allocator>
> class map;

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

map的构造器

示例：

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

map的常用接口

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

迭代器相关

insert

原型

pair insert (const value_type& val);

其中，value_type：

typedef pair value_type;

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

pair insert (const pair& val);

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

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

构造匿名对象

void map_test2()
{map m;m.insert(pair(1, "一"));m.insert(pair(4, "四"));m.insert(pair(2, "二"));m.insert(pair(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 
pair make_pair(T1 x, T2 y)
{return (pair(x, y));
}

示例

void map_test3()
{map 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& k);

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

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

示例

void map_test4()
{map 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& k);

返回值类型

mapped_type：

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

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

mapped_type& operator[] (const key_type& k)
{//1、调用insert插入元素pair 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 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 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::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

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