C++STL标准手册： https://cplusplus.com/reference/stl/

https://cplusplus.com/reference/vector/vector/at/

1、STL基础

1.1、STL基本组成(6大组件+13个头文件)

通常认为，STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的含义如表 1 所示。

表 1 STL 组成结构

STL的组成	含义
容器	一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。
算法	STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 <algorithm> 中，少部分位于头文件 <numeric> 中。
迭代器	在 C++ STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。
函数对象	如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。
适配器	可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。
内存分配器	为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。

另外，在惠普实验室最初发行的版本中，STL 被组织成 48 个头文件；但在 C++ 标准中，它们被重新组织为 13 个头文件，如表 2 所示。

表 2 C++ STL头文件

<iterator>	<functional>	<vector>	<deque>
<list>	<queue>	<stack>	<set>
<map>	<algorithm>	<numeric>	<memory>
<utility>

按照 C++ 标准库的规定，所有标准头文件都不再有扩展名。以 <vector> 为例，此为无扩展名的形式，而 <vector.h> 为有扩展名的形式。

但是，或许是为了向下兼容，或许是为了内部组织规划，某些 STL 版本同时存储具备扩展名和无扩展名的两份文件（例如 Visual C++ 支持的 Dinkumware 版本同时具备 <vector.h> 和 <vector>）；甚至有些 STL 版本同时拥有 3 种形式的头文件（例如 SGI 版本同时拥有 <vector>、<vector.h> 和 <stl_vector.h>）；但也有个别的 STL 版本只存在包含扩展名的头文件（例如 C++ Builder 的 RaugeWare 版本只有 <vector.h>）。

建议读者养成良好的习惯，遵照 C++ 规范，使用无扩展名的头文件(即使用<vector>)。

1.2、容器

简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法(也就是数据结构)。
STL 提供有 3 类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器。它们各自的含义如表 1 所示。
 

容器种类	功能
序列容器	主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置，元素就会位于什么位置。
排序容器	包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的，即便是插入元素，元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。
哈希容器	C++ 11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同，哈希容器中的元素是未排序的，元素的位置由哈希函数确定。

注意，由于哈希容器直到 C++ 11 才被正式纳入 C++ 标准程序库，而在此之前，“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本，不过该版本只能在某些支持 C++ 11 的编译器下使用（如 VS），有些编译器（如 gcc/g++）是不支持的。

另外，以上 3 类容器的存储方式完全不同，因此使用不同容器完成相同操作的效率也大不相同。所以在实际使用时，要善于根据想实现的功能，选择合适的容器。有关这些容器的具体用法，本章后续会逐个进行介绍。

1.3、 迭代器是什么？C++STL迭代器(iterator)

注： 不想记的话这些类型可以直接用auto代替！！！！！！！

1.3.1、 迭代器是什么？

无论是序列容器还是关联容器，最常做的操作无疑是遍历容器中存储的元素，而实现此操作，多数情况会选用“迭代器（iterator）”来实现。那么，迭代器到底是什么呢？

我们知道，尽管不同容器的内部结构各异，但它们本质上都是用来存储大量数据的，换句话说，都是一串能存储多个数据的存储单元。因此，诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。

既然类似，完全可以利用泛型技术，将它们设计成适用所有容器的通用算法，从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置，它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。这就是迭代器了。

这是泛型思维发展的必然结果，于是迭代器就产生了。简单来讲，迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

1.3.2、迭代器类别

STL标准库为每一种标准容器定义了一种迭代器类型。这意味着不同容器的迭代器也不同。

1) 前向迭代器（forward iterator）
假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。

2) 双向迭代器（bidirectional iterator）
双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。

    双向迭代器不支持"<"、">"比较；

    双向迭代器不支持用下标随机访问元素;

3) 随机访问迭代器（random access iterator）
随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
    p+=i：使得 p 往后移动 i 个元素。
    p-=i：使得 p 往前移动 i 个元素。
    p+i：返回 p 后面第 i 个元素的迭代器。
    p-i：返回 p 前面第 i 个元素的迭代器。
    p[i]：返回 p 后面第 i 个元素的引用。

此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。
 

表 1 所示，是 C++ 11 标准中不同容器指定使用的迭代器类型。
 

表 1 不同容器的迭代器

容器	对应的迭代器类型
array	随机访问迭代器
vector	随机访问迭代器
deque	随机访问迭代器
list	双向迭代器
set / multiset	双向迭代器
map / multimap	双向迭代器
forward_list	前向迭代器
unordered_map / unordered_multimap	前向迭代器
unordered_set / unordered_multiset	前向迭代器
stack	不支持迭代器
queue	不支持迭代器

1.3.3、迭代器的定义方式

尽管不同容器对应着不同类别的迭代器，但这些迭代器有着较为统一的定义方式，具体分为 4 种，如表 1 所示。

表 2 迭代器的 4 种定义方式

迭代器定义方式	具体格式
正向迭代器	容器类名::iterator  迭代器名;
常量正向迭代器	容器类名::const_iterator  迭代器名;
反向迭代器	容器类名::reverse_iterator  迭代器名;
常量反向迭代器	容器类名::const_reverse_iterator  迭代器名;

通过定义以上几张迭代器，就可以读取它指向的元素， *迭代器名 就表示迭代器指向的元素。其中，常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。另外，反向迭代器和正向迭代器的区别在于：
对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

注意，以上 4 种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上 4 种方式，比如 array、deque、vector；而有些容器只支持其中部分的定义方式，例如 forward_list 容器只支持定义正向迭代器，不支持定义反向迭代器。

 

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> vec1{1,2,3,4,5,6,7,8,9,10};
    //size的方式遍历
    for (int i = 0; i < vec1.size(); i++){
        cout << vec1[i] << " ";
    }
    cout << endl;
    //创建一个正向迭代器
    vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i=vec1.begin(); i != vec1.end(); ++i){  
        cout << *i << " ";
    }
    cout << endl;

    //用 < 比较两个迭代器
    for (i=vec1.begin(); i < vec1.end(); ++i ){  
        cout << *i << " ";
    }
    cout << endl;

    //迭代器支持 "+=整数" 操作
    i = vec1.begin();
    while(i < vec1.end()){
        cout << *i << " ";
        i += 2; //间隔输出
    }
    cout << endl;
}

在举个例子：

//创建一个 v list容器
list<int> v;
//创建一个常量正向迭代器，同样，list也支持其他三种定义迭代器的方式。
list<int>::const_iterator i;


#以下代码是合法的
for(i = v.begin(); i != v.end(); ++i)
    cout << *i;


#以下代码不合法 因为双向迭代器不支持用“<”进行比较：
for(i = v.begin(); i < v.end(); ++i)
    cout << *i;


#以下代码也不合法，因为双向迭代器不支持用下标随机访问元素：
for(int i=0; i<v.size(); ++i)
    cout << v[i];

2、 string

不属于STL,但是此处也整理出来便于后续查阅。

3、 STL序列式容器

3.0、什么是序列式容器

• STL标准库中的序列式容器包括 array、vector、deque、list 和 foward_list 容器。
• 所谓STL序列式容器，即以线性排列(类似数组的存储方式)来存储某一指定类型的数据；显然它不会对存储的元素进行排序，元素排列的顺序只取决于存储时放置他们的顺序。

• array<T,N>（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
• vector<T>（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
• deque<T>（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
• list<T>（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list<T> 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
• forward_list<T>（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

如下图所示的操作都可以快速执行：

3.1、array

array容器是C++11标准中新增的序列式容器。简单理解，就是在C++普通数据的基础上添加了一些成员函数和全局函数。在使用上比普通数据更安全些，且效率没有因此变差。

#include <array>

表 1 array容器成员函数汇总

成员函数	功能
begin()	返回指向容器中第一个元素的随机访问迭代器。
end()	返回指向容器最后一个元素之后一个位置的随机访问迭代器，通常和 begin() 结合使用。
rbegin()	返回指向最后一个元素的随机访问迭代器。
rend()	返回指向第一个元素之前一个位置的随机访问迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size()	返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N。
max_size()	返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N。
empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快。
at(n)	返回容器中 n 位置处元素的引用，该函数自动检查 n 是否在有效的范围内，如果不是则抛出 out_of_range 异常。
front()	返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器。
back()	返回容器中最后一个元素的直接应用，该函数同样不适用于空的 array 容器。
data()	返回一个指向容器首个元素的指针。利用该指针，可实现复制容器中所有元素等类似功能。
fill(val)	将 val 这个值赋值给容器中的每个元素。
array1.swap(array2)	交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型。

正是由于 array 容器中包含了 at() 这样的成员函数，使得操作元素时比普通数组更安全。

 array使用方式如下：

#include <iostream>
#include <array>

using namespace std;

int main()
{
    array<int, 6> values{};
    //初始化value容器为{0,1,2,3,4,5}
    for (int i=0; i< values.size(); i++){
        values.at(i) = i;
    }

    //使用get() 重载函数输出指定位置的元素
    cout << get<3>(values) << endl;

    //使用迭代器输出容器所有元素
    if (!values.empty()){
        for (auto i = values.begin(); i != values.end(); i++){
            cout << *i << " ";
        }
        cout << endl;
    }
}

3.2、 vector

#include<vector>

3.2.1、向量容器简介

vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++ 普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

需要注意的是，如果调用 reserve() 来增加容器容量，之前创建好的任何迭代器（例如开始迭代器和结束迭代器）都可能会失效，这是因为，为了增加容器的容量，vector<T> 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时，最好重新生成一下。

3.2.2、vector容器的初始化

#创建一个存储double类型元素的vector容器
vector<double> values;

#创建vector容器，创建时指定初始值
vector<int> num {1,2,3,4,5,6,7};

#创建vector容器时指定元素个数;此时容器开始就有20个元素，默认初始值都是0
vector<int> values(20);

#如果不想用0作为默认值,也可以指定其他(此处指定20个元素的值都是1.0)
vector<double> value(20, 1.0);

#上述圆括号的2个参数，既可以是常量也可以用变量表示，例如:
int num = 20;
double value = 1.0;
vector<double> values(num, value);

//注意，圆括号 () 和大括号 {} 是有区别的，前者（例如 (20) ）表示元素的个数，而后者（例如 {20} ） 则表示 vector 容器中只有一个元素 20。

#也可以通过其他vector容器创建新的vector容器，例如:
std::vector<char>value1(5, 'c');
std::vector<char>value2(value1);

#如果不想赋值其他容器的所有元素也可以用迭代器或指针来指定范围
int array[] = {1, 2, 3};
std::vector<int>values(array, array+2);  //values将保存{1, 2}
std::vector<int>value1{1,2,3,4,5};
std::vector<int>value2(std::begin(value1),std::begin(value1)+3 ); //values将保存{1, 2, 3} 

3.2.3、vector容器的成员函数

https://cplusplus.com/reference/vector/vector/

相比 array 容器，vector 提供了更多了成员函数供我们使用，它们各自的功能如表 1 所示。
 

表 1 vector 容器的成员函数

函数成员	函数功能
begin()	返回指向容器中第一个元素的迭代器。
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin()	返回指向最后一个元素的迭代器。
rend()	返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size()	返回实际元素个数。
max_size()	返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
resize()	改变实际元素的个数。
capacity()	返回当前容量。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
reserve()	增加容器的容量。
shrink _to_fit()	将内存减少到等于当前元素实际所使用的大小。
operator[ ]	重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素。
at()	使用经过边界检查的索引访问元素。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
data()	返回指向容器中第一个元素的指针。
assign()	用新元素替换原有内容。
push_back()	在序列的尾部添加一个元素。
pop_back()	移出序列尾部的元素。
insert()	在指定的位置插入一个或多个元素。
erase()	移出一个元素或一段元素。
clear()	移出所有的元素，容器大小变为 0。
swap()	交换两个容器的所有元素。
emplace()	在指定的位置直接生成一个元素。
emplace_back()	在序列尾部生成一个元素。

push_back 与 emplace_back：emplace_back更快(减少一次构造、一次析构)。

底层实现机制不同。push_back()首先创建这个元素，然后将元素拷贝或者移动到容器中(拷贝时自行销毁先前创建的元素); emplace_back直接在容器尾部创建元素，省掉拷贝或移动的过程。

#对于push_back:

vector<string> testVec;
testVec.push_back(string(16, 'a'));


底层实现：
首先，string(16, ‘a’)会创建一个string类型的临时对象，这涉及到一次string构造过程。
其次，vector内会创建一个新的string对象，这是第二次构造。
最后在push_back结束时，最开始的临时对象会被析构。


#对于emplace_back

vector<stirng> testVec;
testVec.emplace_back(string(16, 'a'));

emplace_back可以直接在vector中构建一个对象，而非创建一个临时对象，再放进vector，再销毁。
emplace_back可以省略一次构建和一次析构，从而达到优化的目的。

除此之外，C++ 11 标准库还新增加了 begin() 和 end() 这 2 个函数，和 vector 容器包含的 begin() 和 end() 成员函数不同，标准库提供的这 2 个函数的操作对象，既可以是容器，还可以是普通数组。当操作对象是容器时，它和容器包含的 begin() 和 end() 成员函数的功能完全相同；如果操作对象是普通数组，则 begin() 函数返回的是指向数组第一个元素的指针，同样 end() 返回指向数组中最后一个元素之后一个位置的指针（注意不是最后一个元素）。

vector 容器还有一个 std::swap(x , y) 非成员函数（其中 x 和 y 是存储相同类型元素的  vector 容器），它和 swap() 成员函数的功能完全相同，仅使用语法上有差异。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<char> value;
    value.emplace_back('S');
    value.emplace_back('T');
    value.emplace_back('L');

    cout << "value.size() = " << value.size() << endl;

    //使用迭代器遍历
    cout << "循环输出: ";
    for (vector<char>::iterator iter = value.begin(); iter != value.end(); iter++){
        cout << *iter << " " ;
    }
    cout << endl;

    //向容器开头插入字符
    value.insert(value.begin(), 'C');
    cout << "value首个元素为:" << value.at(0) << endl;

    //第二个位置插入字符'P'
    value.insert(value.begin()+1, 'P');
    cout << "向第2个位置插入P"<< endl;
    //第三个位置插入字符'P'
    value.insert(value.begin()+1, 'P');
    cout << "向第3个位置插入P"<< endl;

    //范围for语句输出(需要修改就加引用)
    cout << "范围for语句输出: ";
    for (auto elem: value){
        cout << elem << " ";
    }
    cout << endl;

    //范围for语句中如果需要修改数据其中数据一定要用引用
    cout << "范围for语句修改每个元素至A: ";
    for (auto &elem: value){
        elem = 'A';
    }
    for (auto elem: value){
        cout << elem << " ";
    }
    cout << endl;

}

输出如下： 

value.size() = 3
循环输出: S T L 
value首个元素为:C
向第2个位置插入P
向第3个位置插入P
范围for语句输出: C P P S T L 
范围for语句修改每个元素至A: A A A A A A 

3.2.4、容器迭代器用法

表 1 vector 支持迭代器的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。
end()	返回指向容器最后一个元素之后一个位置的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。
rbegin()	返回指向最后一个元素的反向迭代器；如果是 const 类型容器，在该函数返回的是常量反向迭代器。
rend()	返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器，在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。
cbegin()	和 begin() 功能类似，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。
cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。
crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。

迭代器的用法：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> values{1,2,3,4,5};
    //使用成员函数begin/end获取容器迭代器
    /*
        auto first = values.begin();
        auto end = values.end();
    */
    //也可以使用全局的begin/end从容器中获取迭代器
    auto first = std::begin(values);
    auto end = std::end(values);

    while(first != end){
        *first = 10;  //可以修改数据
        cout << *first << " ";
        first ++;
    }
    cout << endl;
}

常量迭代器不可以用于修改容器中的元素！！

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> values{1,2,3,4,5};
    //常量迭代器不可修改元素
    auto first = values.cbegin();
    auto end = values.cend();

    while(first != end){
        // *first = 10;  //常量迭代器不可修改数据
        cout << *first << " ";
        first ++;
    }
    cout << endl;
}

3.2.5、容器迭代器注意事项

（1）初始化容器时不能使用迭代器

记住一件事情，先有容器然后才有的迭代器。

在容器为空的情况下尝试通过迭代器给容器填充元素是不可行的。

（2）vector容器扩容时之前的迭代器可能会失效

vector 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效。切记，不能用老迭代器。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> values{1,2,3};
    cout << "value容器首个元素地址:" << values.data() << endl;
    auto beg = std::begin(values);
    auto end = std::end(values);
    cout << "values.size()=" << values.size() << endl;
    
    values.reserve(20);
    cout << "values.size()=" << values.size() << endl;
    values.emplace_back(4);
    values.emplace_back(5);
    values.emplace_back(6);

    cout << "reserve后value容器首个元素地址:" << values.data() << endl;
    cout << "老迭代器输出数据: " ;
    while(beg != end){
        cout << *beg << " ";
        beg++;
    }
    cout << endl;

    cout << "容器实际数据:" ;
    for (auto &elem: values){
        cout << elem << " ";
    }
    cout << endl;

    cout << "结论: reverse后地址会变;且迭代器也随时失效(就迭代能输出旧数据是因为就空间没有被利用而已)!" << endl;
}

3.2.6、vector容器访问元素的几种方式

#include <iostream>
#include <vector>
#include <exception>

using namespace std;

int main()
{
    vector<int> values{1,2,3,4,5,6,7,8,9};
    //方式一:通过下标访问。需要自己确保下标不超过容器的容量,否则会发生越界访问错误。
    cout << "通过下标访问!" << endl;
    cout << "values[0]:" << values[0] << "values[1]:" << values[1] << endl;

    //方式二:通过成员函数 at() 访问。注
    cout << "通过at访问!" << endl;
    cout << "首个元素:" << values.at(0) << endl;
    //修改容器中下标为0的元素的值
    values.at(0) = values.at(1) + values.at(2) + values.at(3) + values.at(4);
    cout << "修改后的首个元素:" << values.at(0) << endl;
    //越界时候回自动抛 out_of_range 异常
    //cout << "第15个元素:" << values.at(15) << endl;

    //通过front和back访问vector的首末元素
    cout << "首个元素:" << values.front() << endl;
    cout << "末尾元素:" << values.back() << endl;

    //方式三: data()成员函数;返回指向容器中首个元素的指针,通过该指针也可访问/修改容器中的元素
    cout << "容器中的第3个元素:" << *(values.data()+2) << endl;
    //修改容器中的第二个元素
    *(values.data()+1) = 222;
    cout << "容器中的第2个元素:" << *(values.data()+1) << endl;

    //二、访问多个元素
    //方式1: 借助size()循环遍历
    for(int i = 0; i < values.size(); i++){
        cout << values[i] << " ";
    }
    cout << endl;

    //方式2: 范围for语句
    for(auto &elem: values){
        cout << elem << " ";
    }
    cout << endl;

    //方式3: 迭代器
    for (auto iter = values.begin(); iter < values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

}

3.2.7、vector容器添加元素emplace_back/push_back

emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。建议后续都是用emplace_back。

#include <vector> 
#include <iostream> 
using namespace std;
class testDemo
{
public:
    testDemo(int num):num(num){
        std::cout << "调用构造函数" << endl;
    }
    testDemo(const testDemo& other) :num(other.num) {
        std::cout << "调用拷贝构造函数" << endl;
    }
    testDemo(testDemo&& other) :num(other.num) {
        std::cout << "调用移动构造函数" << endl;
    }
private:
    int num;
};

int main()
{
    cout << "emplace_back:" << endl;
    std::vector<testDemo> demo1;
    demo1.emplace_back(2);  

    cout << "push_back:" << endl;
    std::vector<testDemo> demo2;
    demo2.push_back(2);
}

输出如下：

emplace_back:
调用构造函数
push_back:
调用构造函数
调用移动构造函数

         显然完成同样的操作，push_back() 的底层实现过程比 emplace_back() 更繁琐，换句话说，emplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back()。

3.2.8、vector容器插入元素insert/emplace

vector容器提供了 insert() 和 emplace() 这 2 个成员函数，用来实现在容器指定位置处插入元素，本节将对它们的用法做详细的讲解。

（1）insert() 函数的功能是在 vector 容器的指定位置前插入一个或多个元素。该函数的语法格式有多种，如表 1 所示。

表 1 insert() 成员函数语法格式

语法格式	用法说明
iterator insert(pos,elem)	在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last)	在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist)	在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。

（2）emplace也是在vector容器指定位置之前插入一个新元素。注意：每次只能插一个。

#include <iostream>
#include <vector>
#include <array>

using namespace std;

void print_vec(vector<int> vec){
    for(auto &elem: vec){
        cout << elem << " ";
    }
    cout << endl;
}


int main()
{
    vector<int> values{1,3,5,7};
    print_vec(values);

    //insert第一种用法
    values.insert(values.begin()+1, 2); //{1,2,3,5,7}
    print_vec(values);

    //insert第二种用法
    values.insert(values.end(), 3, 8); //{1,2,3,5,7,8,8,8}
    print_vec(values);

    //insert第三种用法
    std::array<int, 3> arr{9,10,11};
    values.insert(values.end(), arr.begin(), arr.end()); //{1,2,3,5,7,8,8,8,9,10,11}
    print_vec(values);

    //insert第四种用法
    values.insert(values.end(), {12, 13});
    print_vec(values);


    //看看emplace的用法
    values.emplace(values.begin(),0);
    print_vec(values);
}

输出如下：

1 3 5 7 
1 2 3 5 7 
1 2 3 5 7 8 8 8 
1 2 3 5 7 8 8 8 9 10 11 
1 2 3 5 7 8 8 8 9 10 11 12 13 
0 1 2 3 5 7 8 8 8 9 10 11 12 13 

简单的理解，就是 emplace() 在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中。因此，在实际使用中，推荐大家优先使用 emplace()。

3.2.9、vector容器删除容器的几种方式

表 1 删除 vector 容器元素的几种方式

函数	功能
pop_back()	删除 vector 容器中最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
erase(pos)	删除 vector 容器中 pos 迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
swap(beg)、pop_back()	先调用 swap() 函数交换要删除的目标元素和容器最后一个元素的位置，然后使用 pop_back() 删除该目标元素。
erase(beg,end)	删除 vector 容器中位于迭代器 [beg,end)指定区域内的所有元素，并返回指向被删除区域下一个位置元素的迭代器。该容器的大小（size）会减小，但容量（capacity）不会发生改变。
remove()	删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。
clear()	删除 vector 容器中所有的元素，使其变成空的 vector 容器。该函数会改变 vector 的大小（变为 0），但不是改变其容量。

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

void print_vec(vector<int> vec){
    for(auto &elem: vec){
        cout << elem << " ";
    }
    cout << endl;
}


int main()
{
    vector<int> values{1,2,3,4,5,6,7,8,9};
    print_vec(values);
    //方式1: 删除最后一个元素
    values.pop_back();
    print_vec(values);

    //方式2: 删除小标为1的元素
    values.erase(values.begin()+1); //删除元素2
    print_vec(values);

    //方式3: swap + pop_back 删除元素(不介意元素相对位置调整)
    swap(*(values.begin()), *(values.end()));
    values.pop_back();
    print_vec(values);

    //方式4: erase删除指定范围的元素
    values.erase(values.begin(), values.begin()+2); //删除最开始的2个元素
    print_vec(values);



    //方式6: clear清空容器所有元素
    values.clear();
    print_vec(values);

}

注：其中的remove比较有意思，单独拎出来说下。

remove：删除容器中指定值的元素(如删除值为3的元素)。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void print_vec(vector<int> vec){
    for(auto &elem: vec){
        cout << elem << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> values{1,3,3,4,3,5};

    //删除值为3的元素
    auto iter = std::remove(values.begin(), values.end(), 3);
    cout << "size is :" << values.size() << endl;
    cout << "capacity is :" << values.capacity() << endl;

    //输出剩余元素
    for (auto first = values.begin(); first < iter; first++){
        cout << *first << " " ;
    }
    cout << endl;

    //输出所有元素
    print_vec(values);

    //标准玩法是结合erase,在remove的同时在删掉后续无用数据,如下:
    //values.erase(std::remove(values.begin(), values.end(), 3), values.end());
    vector<int> values1{1,3,3,4,3,5};
    values1.erase(std::remove(values1.begin(), values1.end(), 3), values1.end());
    print_vec(values1);

}

remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。

remove()用于删除容器中指定元素时，常和 erase() 成员函数搭配使用。

3.2.10、注意！ vector<bool>不是存储bool类型元素的vector容器

        vector<bool>并不是一个STL容器，不是一个STL容器，不是一个STL容器！

        正常情况下我们使用bool类型他的长度应该是一个字节，即等效于uint8_t。

虽然我们知道bool只需要一个bit来表示，但由于硬件无法直接对bit进行寻址C++语法中也不存在使用指针指向bit的玩法。重点来了，vector<bool>中每个元素的长度真的是1bit，而不是1字节，于是就导致了很多匪夷所思的问题。

        首先vector< bool> 并不是一个通常意义上的vector容器，这个源自于历史遗留问题。 早在C++98的时候，就有vector< bool>这个类型了，但是因为当时为了考虑到节省空间的想法，所以vector< bool>里面不是一个Byte一个Byte储存的，它是一个bit一个bit储存的！
        因为C++没有直接去给一个bit来操作，所以用operator[]的时候，正常容器返回的应该是一个对应元素的引用，但是对于vector< bool>实际上访问的是一个"proxy reference"而不是一个"true reference"，返回的是"std::vector< bool>:reference"类型的对象。 而一般情况情况下

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


int main()
{
    vector c{ false, true, false, true, false };
    bool b = c[0];
    auto d = c[0];
    cout << "b:" << b << endl;
    cout << "d:" << d << endl;

    d = true;
    for (auto i:c){
        cout << i << " ";
    }
    cout << endl;

}


#输出如下:
b:0
d:0
1 1 0 1 0 

对于b的初始化它其实暗含了一个隐式的类型转换。

而对于d，它的类型并不是bool，而是一个vector< bool>中的一个内部类。

而此时如果修改d的值，c中的值也会跟着修改。

而如果c被销毁，d就会变成一个悬垂指针，再对d操作就属于未定义行为。

之所以说vector<int>不是一个标准容器，就是因为它不支持容器该有的基本操作。

3.3、 deque(double-ended queue) 双端队列容器

deque是 double-ended queue的缩写，又称“双端队列容器”。 

#include<deque>

using namespace std;

3.3.1、deque介绍

deque 容器和 vecotr 容器有很多相似之处，比如：

• deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
• deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

当需要向序列两端频繁的添加或删除元素时，应首选 deque 容器。

3.3.3、deque成员函数

基于 deque 双端队列的特点，该容器包含一些 array、vector 容器都没有的成员函数。

表 1 中罗列了 deque 容器提供的所有成员函数。
 

表 1 deque 容器的成员函数

函数成员	函数功能
begin()	返回指向容器中第一个元素的迭代器。
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。
rbegin()	返回指向最后一个元素的迭代器。
rend()	返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
size()	返回实际元素个数。
max_size()	返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。
resize()	改变实际元素的个数。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
shrink _to_fit()	将内存减少到等于当前元素实际所使用的大小。
at()	使用经过边界检查的索引访问元素。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
assign()	用新元素替换原有内容。
push_back()	在序列的尾部添加一个元素。
push_front()	在序列的头部添加一个元素。
pop_back()	移除容器尾部的元素。
pop_front()	移除容器头部的元素。
insert()	在指定的位置插入一个或多个元素。
erase()	移除一个元素或一段元素。
clear()	移出所有的元素，容器大小变为 0。
swap()	交换两个容器的所有元素。
emplace()	在指定的位置直接生成一个元素。
emplace_front()	在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。
emplace_back()	在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。

和 vector 相比，额外增加了实现在容器头部添加和删除元素的成员函数，同时删除了 capacity()、reserve() 和 data() 成员函数。

#include <deque>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    //1、deque的创建
    //1.1、创建没有任何元素的空deque容器
    std::deque<int> d;
    //1.2、创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：
    std::deque<int> d1(10);
    //1.3、创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：
    std::deque<int> d2(10, 5);
    //1.4、在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：
    std::deque<int> d3(d2);

    //2、插入数据
    d.push_back(1);//{1}
    d.push_back(2);//{1,2}
    d.push_back(3);//{1,2,3}

    d.push_front(0); //{0,1,2,3,4}
    cout << "d.size():" << d.size() << endl;
    
    for(auto i = d.begin(); i< d.end(); i++){
        cout << *i << " ";
    }
    cout << endl;
}

3.3.4、deque迭代器用法

和vector看起来一样。

表 1 deque 支持迭代器的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。
end()	返回指向容器最后一个元素之后一个位置的正向迭代器；如果是 const 类型容器，在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。
rbegin()	返回指向最后一个元素的反向迭代器；如果是 const 类型容器，在该函数返回的是常量反向迭代器。
rend()	返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器，在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。
cbegin()	和 begin() 功能类似，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。
cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。
crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器，不能用于修改元素。

迭代器用于遍历或修改容器中的元素，不能用于初始化空的deque容器。

3.3.5、deque访问元素

#include <deque>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    //1、deque的创建
    //1.1、创建没有任何元素的空deque容器
    std::deque<int> d;
    //1.2、创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：
    std::deque<int> d1(10);
    //1.3、创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：
    std::deque<int> d2(10, 5);
    //1.4、在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：
    std::deque<int> d3(d2);

    //2、插入数据
    d.push_back(1);//{1}
    d.push_back(2);//{1,2}
    d.push_back(3);//{1,2,3}

    d.push_front(0); //{0,1,2,3,4}
    cout << "d.size():" << d.size() << endl;
    
    for(auto i = d.begin(); i< d.end(); i++){
        cout << *i << " ";
    }
    cout << endl;

    //3、deque访问元素
    //3.1、下标访问
    cout << "第一个元素:" << d[0] << endl;

    //3.2、at访问
    cout << "第一个元素:" << d.at(0) << endl;

    //3.3、front()/back()访问第一个和最后一个元素(同样可以修改第一个or最后一个元素)
    cout << "第一个元素:" << d.front() << endl;
    cout << "最后个元素:" << d.back() << endl;
    d.front() = 10;
    d.back() = 20;

    //3.4、迭代器访问
    auto beg = d.begin() +2;
    auto end = d.end();
    while(beg < end){
        cout << *beg << " ";
        beg++;
    }
    cout << endl;
}

3.3.6、deque删除元素

deque 容器中，无论是添加元素还是删除元素，都只能借助 deque 模板类提供的成员函数。表 1 中罗列的是所有和添加或删除容器内元素相关的 deque 模板类中的成员函数。
 

表 1 和添加或删除deque容器中元素相关的成员函数

成员函数	功能
push_back()	在容器现有元素的尾部添加一个元素，和 emplace_back() 不同，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的尾部。
pop_back()	移除容器尾部的一个元素。
push_front()	在容器现有元素的头部添加一个元素，和 emplace_back() 不同，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的头部。
pop_front()	移除容器尾部的一个元素。
emplace_back()	C++ 11 新添加的成员函数，其功能是在容器尾部生成一个元素。和 push_back() 不同，该函数直接在容器头部构造元素，省去了复制或移动元素的过程。
emplace_front()	C++ 11 新添加的成员函数，其功能是在容器头部生成一个元素。和 push_front() 不同，该函数直接在容器头部构造元素，省去了复制或移动元素的过程。
insert()	在指定的位置直接生成一个元素。和 emplace() 不同的是，该函数添加新元素的过程是，先构造元素，然后再将该元素移动或复制到容器的指定位置。
emplace()	C++ 11 新添加的成员函数，其功能是 insert() 相同，即在指定的位置直接生成一个元素。和 insert() 不同的是，emplace() 直接在容器指定位置构造元素，省去了复制或移动元素的过程。
erase()	移除一个元素或某一区域内的多个元素。
clear()	删除容器中所有的元素。

在实际应用中，常用 emplace()、emplace_front() 和 emplace_back() 分别代替 insert()、push_front() 和 push_back()，原因和vector一样即前者更快。

上述成员函数中，insert()函数的语法格式比较多、erase()有两种语法格式，其他函数都只有一种用法。下面程序演示使用。

关于insert()函数的用法如下：

表 2 insert() 成员函数语法格式

语法格式	功能
iterator insert(pos,elem)	在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last)	在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist)	在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。

#include <deque>
#include <iostream>
#include <string>
#include <array>

using namespace std;

int main()
{
    deque<int> d;
    //调用push_back()向容器尾部添加数据
    d.push_back(11); //{11}
    //调用pop_back()移除容器尾部的数据
    d.pop_back();   //{}

    //调用push_front()向容器头部添加数据
    d.push_front(22); //{22}
    //调用pop_front()移除容器头部的数据
    d.pop_front();    //{}

    //调用emplace_back/emplace_front函数，向容器中直接生成数据
    d.emplace_back(33);  //{33}
    d.emplace_front(11); //{11}

    //emplace()需要两个参数,第一个指定插入位置,第二个是插入的数值
    d.emplace(d.begin()+1, 22); //{11, 22, 33}
    
    //for循环语句输出
    for(auto i:d){
        cout << i << " ";
    }
    cout << endl;

    //erase()可以接受一个迭代器表示要输出元素所在的位置
    //也可以接受2个迭代器,表示要删除元素所在的区域。
    d.erase(d.begin()); //{22, 33}
    d.erase(d.begin(), d.end()); //全部清空,等同于 clear()
    cout << "d.size():" << d.size() << endl;

    //下面演示 insert 的四种用法
    deque<int> dq{1,3};
    //第一种格式用法
    dq.insert(dq.begin() + 1, 2); //{1, 2, 3}

    //第二种格式用法(插入2个4)
    dq.insert(dq.end(), 2, 4);  //{1,2,3,4,4}

    //第三种格式用法
    array<int, 3>test{6,7,8};
    dq.insert(dq.end(), test.begin(), test.end()); //{1,2,3,4,4,6,7,8}

    //第四种格式用法
    dq.insert(dq.end(),{9,10}); //{1,2,3,4,4,6,7,8,9,10}

    for (auto i : dq){
        cout << i << " ";
    }
    cout << endl;
}

3.4、 list(双向链表)

#include<list>

using namespace std;

3.4.1、list简介

STL list(双向链表容器)，该容器的底层以双向链表的形式实现的。这意味着，list容器中的元素可以分散存储在内存空间里，而不是必须存储在已真快连续的内存空间中。

        可以看到，list容器中各个元素的前后顺序都是靠指针来维系的；每个元素都配备了2个指针，分别指向他的前一个元素和后一个元素。其中第一个元素的前向指针为null，因为其前面没有元素；同理，尾部元素的后向指针也为null。

        基于这样的存储结构，list容器具有一些其他容器(array/vector/deque)所不具备的优势，即他可以在序列一直的任何位置快速插入或删除元素(时间复杂度为O(1))。而且在list容器中移动元素也比其他容器的效率更高。

        当然其缺点也很明显，即它不能像array、vector那样通过位置下标直接访问元素。举例来说如果需要访问第6个元素，只能通过容器的第一个元素开始往后遍历直到找到该位置。

实际场景中，如何需要对序列进行大量添加或删除元素的操作，而直接访问元素的需求却很少，这种情况建议使用 list 容器存储序列。

3.4.2、list可用成员函数

表 2 中罗列出了 list 模板类提供的所有成员函数以及各自的功能。

其实官网上都有  list - C++ Reference

表 2 list 容器可用的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的双向迭代器。
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin()	返回指向最后一个元素的反向双向迭代器。
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
size()	返回当前容器实际包含的元素个数。
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
assign()	用新元素替换容器中原有内容。
emplace_front()	在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。
push_front()	在容器头部插入一个元素。
pop_front()	删除容器头部的一个元素。
emplace_back()	在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。
push_back()	在容器尾部插入一个元素。
pop_back()	删除容器尾部的一个元素。
emplace()	在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。
insert()	在容器中的指定位置插入元素。
erase()	删除容器中一个或某区域内的元素。
swap()	交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
resize()	调整容器的大小。
clear()	删除容器存储的所有元素。
splice()	将一个 list 容器中的元素插入到另一个容器的指定位置。
remove(val)	删除容器中所有等于 val 的元素。
remove_if()	删除容器中满足条件的元素。
unique()	删除容器中相邻的重复元素，只保留一个。
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。
sort()	通过更改容器中元素的位置，将它们进行排序。
reverse()	反转容器中元素的顺序。

除此之外，C++11标准库提供的 begin() 和 end()两个函数也是可用的，效果与成员函数begin()/end()等效。

#include <list>
#include <array>
#include <iostream>

using namespace std;

int main() 
{
    //1、通过一下5种方式创建list容器的方式
    //1.1、创建一个没有任何元素的空list容器
    //list<int> values;

    //1.2、创建一个包含n个元素的list容器
    //list<int> values(10);

    //1.3、创建一个包含n个元素的list容器并为每个元素指定初始值
    //list<int> values(10,5);

    //1.4、在已有list容器的情况下拷贝改容器创建新的list容器
    list<int> value1(10);
    list<int> value2(value1);

    //1.5、拷贝其他容器类型中指定区域的元素，创建新的list容器
    //拷贝普通数组，创建list容器
    //int a[] = { 1,2,3,4,5 };
    //std::list<int> values(a, a+5);
    //拷贝其它类型的容器，创建 list 容器
    //std::array<int, 5>arr{ 11,12,13,14,15 };
    //std::list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}


    //2、部分成员函数的用法

    //创建空的list容器
    list<double> values;
    //向容器中添加元素
    values.push_back(2.2);
    values.push_back(1.1);
    values.push_back(3.3);
    cout << "values.size():" << values.size() << endl;
    //对容器中的元素进行排序
    values.sort();
    //for循环遍历输出
    for (auto i: values){
        cout << i << " ";
    }
    cout << endl;

    //迭代器遍历输出
    for (list<double>::iterator iter = values.begin(); iter != values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    //auto迭代器输出
    for (auto iter = values.begin(); iter!=values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

}

3.4.3、list迭代器的用法

其对应的是双向迭代器，可以++、--、判等，但是不可以比大小、不可以加数值(不可随机访问)。

前面章节已经详细介绍了 array、vector、deque 容器的迭代器，和它们相比，list 容器迭代器最大的不同在于，其配备的迭代器类型为双向迭代器，而不再是随机访问迭代器。

这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1--、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：

• p1[i]：不能通过下标访问 list 容器中指定位置处的元素。
• p1-=i、 p1+=i、 p1+i 、p1-i：双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。
• p1<p2、 p1>p2、 p1<=p2、 p1>=p2：双向迭代器 p1、p2 不支持使用 <、 >、 <=、 >= 比较运算符。

注意，程序中比较迭代器之间的关系，用的是 != 运算符，因为它不支持 < 等运算符。另外在实际场景中，所有迭代器函数的返回值都可以传给使用 auto 关键字定义的变量，因为编译器可以自行判断出该迭代器的类型。

#include <list>
#include <array>
#include <iostream>

using namespace std;

int main() 
{
    //创建list容器
    list<char> values{'h','t','t','p',':','/','/','w','w','w','.','b','a','i','d','u','.','c','o','m'};
    //使用正向迭代器
    for (auto iter = values.begin(); iter != values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    //使用反向迭代器
    for(auto iter = values.rbegin(); iter != values.rend(); iter++){
        cout << *iter << " ";
    }
    cout << endl;
    cout << endl;

    //创建begin()和end()迭代器
    list<char>::iterator beg = values.begin();
    list<char>::iterator end = values.end();
    while(beg!=end){
        cout << *beg << " ";
        beg++;
    }
    cout << endl;

    beg = values.begin();
    end = values.end();
    //头部和尾部插入字符
    values.insert(beg,'1');
    values.insert(end,'1');

    while(beg!=end){
        cout << *beg << " ";
        beg++;
    }
    cout << endl;
}

输出为：

h t t p : / / w w w . b a i d u . c o m 
m o c . u d i a b . w w w / / : p t t h 

h t t p : / / w w w . b a i d u . c o m 
h t t p : / / w w w . b a i d u . c o m 1 

结论：插入元素不会导致之前的迭代器失效(程序不会报错);但是由于插入元素位置的不同，使用老迭代器可能会遗漏新插入元素。

3.4.4、访问list中的元素

不同于之前学过的 STL 容器，访问 list 容器中存储元素的方式很有限，即要么使用 front() 和 back() 成员函数，要么使用 list 容器迭代器。

list 容器不支持随机访问，未提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数。

#include <list>
#include <array>
#include <iostream>

using namespace std;

int main() 
{
    //创建list容器
    list<int> mylist{1,2,3,4};
    cout << "mylist.front():" << mylist.front() << endl;
    cout << "mylist.back():" << mylist.back() << endl;

    //注:front/back不进可以访问首末元素,还可以修改他们的值
    mylist.front() = 11;
    mylist.back() = 44;
    cout << "mylist.front():" << mylist.front() << endl;
    cout << "mylist.back():" << mylist.back() << endl;

    //其他访问方法就是迭代器了
    for (auto iter = mylist.begin(); iter != mylist.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;
}

3.4.5、list插入元素

list 模板类中，与“添加或插入新元素”相关的成员方法有如下几个：

• push_front()：向 list 容器首个元素前添加新元素；
• push_back()：向 list 容器最后一个元素后添加新元素；
• emplace_front()：在容器首个元素前直接生成新的元素；
• emplace_back()：在容器最后一个元素后直接生成新的元素；
• emplace()：在容器的指定位置直接生成新的元素；
• insert()：在指定位置插入新元素；
• splice()：将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。

读者有没有发现，同样是实现插入元素的功能，无论是 push_front()、push_back() 还是 insert()，都有以 emplace 为名且功能和前者相同的成员函数。这是因为，后者是 C++ 11 标准新添加的，在大多数场景中，都可以完全替代前者实现同样的功能。更重要的是，实现同样的功能，emplace 系列方法的执行效率更高。

以上这些成员方法中，除了 insert() 和 splice() 方法有多种语法格式外，其它成员方法都仅有 1 种语法格式。

#include <list>
#include <array>
#include <iostream>

using namespace std;

int main() 
{
    list<int> values{1, 2, 3};
    values.push_front(0); //{0,1,2,3}
    values.push_back(4);  //{0,1,2,3,4}

    values.emplace_front(-1); //{-1,0,1,2,3,4}
    values.emplace_back(5);   //{-1,0,1,2,3,4,5}

    //emplace(pos, value) pos表示插入的位置(用迭代器表示),value为待插入的元素
    values.emplace(values.end(), 6); //{-1,0,1,2,3,4,5,6}

    for(auto iter = values.begin(); iter != values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;
}

list的insert()成员函数。前面介绍的一样有四种方式：如表 1 所示。

表 1 insert() 成员方法语法格式

语法格式	用法说明
iterator insert(pos,elem)	在迭代器 pos 指定的位置之前插入一个新元素 elem，并返回表示新插入元素位置的迭代器。
iterator insert(pos,n,elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,first,last)	在迭代器 pos 指定的位置之前，插入其他容器（例如 array、vector、deque 等）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。
iterator insert(pos,initlist)	在迭代器 pos 指定的位置之前，插入初始化列表（用大括号 { } 括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。

list的splice()成员函数。 splice功能是将其他list容器中的元素添加到当前list容器指定位置处。

splice: 粘接

英[splaɪs]

splice() 成员方法的语法格式有 3 种，如表 2 所示。
 

表 2 splice() 成员方法的用法

语法格式	功能
void splice (iterator position, list& x);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器。 此格式的 splice() 方法的功能是，将 x 容器中存储的所有元素全部移动当前 list 容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator i);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器；i 也是一个迭代器，用于指向 x 容器中某个元素。 此格式的 splice() 方法的功能是将 x 容器中 i 指向的元素移动到当前容器中 position 指明的位置处。
void splice (iterator position, list& x, iterator first, iterator last);	position 为迭代器，用于指明插入位置；x 为另一个 list 容器；first 和 last 都是迭代器，[fist,last) 用于指定 x 容器中的某个区域。 此格式的 splice() 方法的功能是将 x 容器 [first, last) 范围内所有的元素移动到当前容器 position 指明的位置处。

#include <list>
#include <array>
#include <iostream>

using namespace std;

int main() 
{
    //创建两个list容器
    list<int> list1{1,2,3,4}, list2{10,20,30};

    auto it1 = ++list1.begin(); //指向list1容器中的元素2

    //第一种语法:在list1的iter位置处splice list2
    list1.splice(it1, list2);  //list1 {1,10,20,30,2,3,4}
    for(auto i: list1){
        cout << i << " ";
    }
    cout << endl;

    //第二种语法: 将list1迭代器it1指向的元素(2)移动到list2.begin位置处
    list2.splice(list2.begin(), list1, it1);
    cout << "list1:";
    for(auto i: list1){cout << i << " ";}
    cout << endl;

    cout << "list2:";
    for(auto i: list2){cout << i << " ";}
    cout << endl;

    //第三种语法: 将[list1.begin(),list1.end()]范围内的元素移动到list2.begin()位置处
    list2.splice(list2.begin(), list1, list1.begin(), list1.end());
    cout << "list1:";
    for(auto i: list1){cout << i << " ";}
    cout << endl;

    cout << "list2:";
    for(auto i: list2){cout << i << " ";}
    cout << endl;
}

输出结果为：

1 10 20 30 2 3 4 
list1:1 10 20 30 3 4 
list2:2 
list1:
list2:1 10 20 30 3 4 2 

3.4.6、list删除元素

对 list 容器存储的元素执行删除操作，需要借助该容器模板类提供的成员函数。幸运的是，相比其它 STL 容器模板类，list 模板类提供了更多用来实现此操作的成员函数（如表 1 所示）。
 

表 1 实现 list 容器删除元素的成员函数

成员函数	功能
pop_front()	删除位于 list 容器头部的一个元素。
pop_back()	删除位于 list 容器尾部的一个元素。
erase()	该成员函数既可以删除 list 容器中指定位置处的元素，也可以删除容器中某个区域内的多个元素。
clear()	删除 list 容器存储的所有元素。
remove(val)	删除容器中所有等于 val 的元素。
unique()	删除容器中相邻的重复元素，只保留一份。
remove_if()	删除容器中满足条件的元素。

3.5、 forward_list(单向链表)

#include<forward_list>

using namespace std;

3.5.1、forward_list介绍

forward_list 是 C++ 11 新添加的一类容器，其底层实现和 list 容器一样，采用的也是链表结构，只不过 forward_list 使用的是单链表，而 list 使用的是双向链表（如图 1 所示）。

        因此，forward_list 容器具有和 list 容器相同的特性，即擅长在序列的任何位置进行插入元素或删除元素的操作，但对于访问存储的元素，没有其它容器（如 array、vector）的效率高。

       另外，由于单链表没有双向链表那样灵活，因此相比 list 容器，forward_list 容器的功能受到了很多限制。比如，由于单链表只能从前向后遍历，而不支持反向遍历，因此 forward_list 容器只提供前向迭代器，而不是双向迭代器。这意味着，forward_list 容器不具有 rbegin()、rend() 之类的成员函数。

那么，既然 forward_list 容器具有和 list 容器相同的特性，list 容器还可以提供更多的功能函数，forward_list 容器有什么存在的必要呢？
 

效率高是选用 forward_list 而弃用 list 容器最主要的原因，换句话说，只要是 list 容器和 forward_list 容器都能实现的操作，应优先选择 forward_list 容器。

3.5.2、forward_list使用

#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;


int main()
{
    forward_list<int> values{1,2,3,4,5};
    forward_list<int> value1{10};
    forward_list<int> value2(value1);

    values.emplace_front(0); //{0,1,2,3,4,5}
    values.emplace_after(values.begin(), 6); //{0,1,2,3,4,5,6}
    for(auto iter = values.begin(); iter != values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    values.reverse();
    for(auto iter = values.begin(); iter != values.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    //forward_list不提供size()函数，如果想要获取元素数可以通过 头文件<iterator>中的distance()函数。
    int count = std::distance(std::begin(values), std::end(values));
    cout << "count:" << count << endl;

    //forward_list除了吹用++运算符单步移动,还能使用 advance() 函数多步移动
    auto it = values.begin();
    cout << "*it:" << *it << endl;
    advance(it, 2);
    cout << "*it:" << *it << endl;
}

输出如下：

0 6 1 2 3 4 5 
5 4 3 2 1 6 0 
count:7
*it:5
*it:3

4、STL有序关联容器(map/set/multimap/multiset) — 红黑树

4.0、关联容器介绍

        前面序列式容器只存储各种类型的元素。关联式容器则大不一样，此类容器在存储元素值的同时，还会为各元素额外再配备一个“键”（其本质也是一个 C++ 基础数据类型或自定义类型的元素），它的功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。

也就是说，关联式容器存储的元素都是一个一个的“键值对”（ <key,value> ），这是和序列式容器最大的不同。除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素默认会根据各元素的键值的大小做升序排序。
 

注：set的键值相等了而已，也可以视为键值对！！！！！

关联式容器所具备的这些特性，归咎于 STL 标准库在实现该类型容器时，底层选用了 「红黑树」这种数据结构来组织和存储各个键值对。

4.0.1、STL关联容器种类

C++ STL 标准库提供了 4 种关联式容器，分别为 map、set、multimap、multiset，其各自的特点如表 1 所示。

表 1 C++ STL关联式容器类别

关联式容器名称	特点
map	定义在 <map> 头文件中，使用该容器存储的数据，其各个元素的键必须是唯一的（即不能重复），该容器会根据各元素键的大小，默认进行升序排序（调用 std::less<T>）。
set	定义在 <set> 头文件中，使用该容器存储的数据，各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。该容器会自动根据各个元素的键（其实也就是元素值）的大小进行升序排序（调用 std::less<T>）。
multimap	定义在 <map> 头文件中，和 map 容器唯一的不同在于，multimap 容器中存储元素的键可以重复。
multiset	定义在 <set> 头文件中，和 set 容器唯一的不同在于，multiset 容器中存储元素的值可以重复（一旦值重复，则意味着键也是重复的）。

除此之外，C++ 11 还新增了 4 种哈希容器，即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说，它们也属于关联式容器，但由于哈希容器底层采用的是哈希表，而不是红黑树，因此将它们分开进行讲解（有关哈希容器，将放在后续章节做详细讲解）

4.0.2、 pair

#include<utility>

#include <iostream>
#include <string>
#include <utility>

using namespace std;

int main()
{
    //调用默认构造函数
    pair<string, double> pair1;

    //调用第二种构造函数
    pair<string, string> pair2("name","zhizhuo");

    //调用拷贝构造函数
    pair<string, string> pair3(pair2);

    //make_pair构造
    pair<string, string> pair4 = make_pair("age", "20");
    auto pair5 = make_pair("gender", "man");

    //打印各pair
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: " << pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
    cout << "pair5: " << pair5.first << " " << pair5.second << endl;


    //pair类模板还提供一个swap成员函数,能够互换两个pair的键值对;当然前提是类型相同。
    cout << endl;
    pair2.swap(pair4);
    cout << "pair2: " << pair2.first << " " << pair2.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
}

输出为：

pair1:  0
pair2: name zhizhuo
pair3: name zhizhuo
pair4: age 20
pair5: gender man

pair2: age 20
pair4: name zhizhuo

4.1、 map

#include<map>

using namespace std;

4.1.1、map简介

map容器的模板定义如下：

template < class Key,                                     // 指定键（key）的类型
           class T,                                       // 指定值（value）的类型
           class Compare = less<Key>,                     // 指定排序规则
           class Alloc = allocator<pair<const Key,T> >    // 指定分配器对象的类型
           > class map;

        可以看到，map 容器模板有 4 个参数，其中后 2 个参数都设有默认值。大多数场景中，我们只需要设定前 2 个参数的值，有些场景可能会用到第 3 个参数，但最后一个参数几乎不会用到。
 

        在使用map容器存储多个键值对的时候，map会自动根据各键值对的键的大小，按照既定规则进行排序。默认情况下，map容器选用 std::less<T> 排序规则，此时会根据键的大小对所有键值对做升序排序。当然，根据实际情况的需要我们可以手动指定map容器的排序规则，既可以选用STL标准库提供的其他排序规则(比如 std::greater<T>)，也可以自定义排序规则。

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    //调用map默认构造函数，创建一个空的map容器
    std::map<string, int> map1;

    //在创建map容器的同事，进行初始化
    map<string, int> map2{{"math", 100}, {"english", 97}};
    map<string, int> map3{make_pair("chinese", 92), make_pair("physics", 99)};

    //基于已有map创建新的map
    map<string, int> map4(map3);

    //手动修改map容器的排序规则。默认情况下map容器调用std::less<T>规则，此时按照"键"做升序排列
    map<string, int, std::less<string> > map5{{"chemistry", 94}, {"physical culture", 96}};
    //范围for语句遍历
    for (auto iter: map5){
        cout << iter.first << ":" << iter.second << endl;
    }
    cout << endl;

    //手动修改排序规则为降序
    map<string, int, std::greater<string> > map6{{"chemistry", 94}, {"physical culture", 96}};
    //范围for语句遍历
    for (auto iter: map6){
        cout << iter.first << ":" << iter.second << endl;
    }
}

输出如下：

chemistry:94
physical culture:96

physical culture:96
chemistry:94

4.1.2、map成员函数

表 1 列出了 map 容器提供的常用成员方法以及各自的功能。
 

表 1 C++ map容器常用成员方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
find(key)	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)	返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)	返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 map 容器中存有键值对的个数。
max_size()	返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
operator[]	map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
at(key)	找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
insert()	向 map 容器中插入键值对。
erase()	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。
swap()	交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
clear()	清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
emplace()	在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
count(key)	在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    //调用map默认构造函数，创建一个空的map容器
    std::map<string, int, std::greater<string> > map1;

    //插入元素
    map1.emplace("math", 100);
    map1.emplace("chinese", 92);
    map1.emplace("english", 97);
    map1["physics"] = 99;
    map1["chemistry"] = 94;

    //输出当前map容器存储键值对的个数
    cout << "map1.size():" << map1.size() << endl;
    cout << "map1[math]:" << map1.at("math") << endl; 
    cout << "map1[physics]:" << map1.at("physics") << endl; 
    cout << endl;
    
    //判断当前容器是否为空
    if (!map1.empty()){
        //借助迭代器进行遍历
        for (auto iter = map1.begin(); iter != map1.end(); iter++){
            cout << iter->first << ":" << iter->second << endl;
        }
    }

    cout << endl;
    //查找某个key是否存在
    string key = "math";
    if (map1.find(key) == map1.end()){
        cout << "no key " << key << endl; 
    }else{
        cout << "has key " << key << endl;
    }
}

输出结果：

map1.size():5
map1[math]:100
map1[physics]:99

physics:99
math:100
english:97
chinese:92
chemistry:94

has key math

4.1.3、map迭代器用法

C++ STL 标准库为 map 容器配备的是双向迭代器（bidirectional iterator）。这意味着，map 容器迭代器只能进行 ++p、p++、--p、p--、*p 操作，并且迭代器之间只能使用 == 或者 != 运算符进行比较。
 

值得一提的是，相比序列式容器，map 容器提供了更多的成员方法（如表 1 所示），通过调用它们，我们可以轻松获取具有指定含义的迭代器。
 

表 1 map 容器迭代器相关成员方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
find(key)	在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)	返回一个指向当前 map 容器中第一个大于等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)	返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。

同时，map 类模板中还提供有 lower_bound(key) 和 upper_bound(key) 成员方法，它们的功能是类似的，唯一的区别在于：

• lower_bound(key) 返回的是指向第一个键不小于 key 的键值对的迭代器；
• upper_bound(key) 返回的是指向第一个键大于 key 的键值对的迭代器；

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    //调用map默认构造函数，创建一个空的map容器
    std::map<string, string> map1;
    //插入元素
    map1["a"] = "aa";
    map1["b"] = "bb";
    map1["c"] = "cc";
    map1["d"] = "dd";
    map1["e"] = "ee";
    for (auto elem: map1){
        cout << elem.first << " " << elem.second << endl;
    }
    cout << endl;

    auto iter1 = map1.upper_bound("b");
    cout << "upper_bound(b):" << iter1->first << " " << iter1->second << endl;

    auto iter2 = map1.lower_bound("b");
    cout << "lower_bound(b):" << iter2->first << " " << iter2->second << endl;

    cout << endl;
    //创建一个pair对象,来接受equal_range()的返回值
    pair<map<string, string>::iterator, map<string, string>::iterator> mypair = map1.equal_range("d");
    for(auto iter = mypair.first; iter!=mypair.second; ++iter){
        cout << iter->first << " " << iter->second << endl;
    }

}

输出如下：

a aa
b bb
c cc
d dd
e ee

upper_bound(b):c cc
lower_bound(b):b bb

d dd

        lower_bound(key) 和 upper_bound(key) 更多用于 multimap 容器，在 map 容器中很少用到。

        和 lower_bound(key)、upper_bound(key) 一样，该equal_range也更常用于 multimap 容器，因为 map 容器中各键值对的键的值都是唯一的，因此通过 map 容器调用此方法，其返回的范围内最多也只有 1 个键值对。

        equal_range(key) 成员方法可以看做是 lower_bound(key) 和 upper_bound(key) 的结合体，该方法会返回一个 pair 对象，其中的 2 个元素都是迭代器类型，其中 pair.first 实际上就是 lower_bound(key) 的返回值，而 pair.second 则等同于 upper_bound(key) 的返回值。

        显然，equal_range(key) 成员方法表示的一个范围，位于此范围中的键值对，其键的值都为 key。

4.1.4、map获取键对应值的方法

主要有三种方法： 1）重载[]运算符下标法访问   2）at()成员方法  3) find()成员函数

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    //调用map默认构造函数，创建一个空的map容器
    std::map<string, string> map1;
    //插入元素
    map1["a"] = "aa";
    map1["b"] = "bb";
    map1["c"] = "cc";
    map1["d"] = "dd";
    map1["e"] = "ee";
    for (auto elem: map1){
        cout << elem.first << " " << elem.second << endl;
    }
    cout << endl;

    // 方法一: 通过下标访问
    // map 容器中确实存有包含该指定键的键值对，借助重载的 [ ] 运算符才能成功获取该键对应的值；
    // 反之，若当前 map 容器中没有包含该指定键的键值对，则此时使用 [ ] 运算符将不再是访问容器中的元素，而变成了向该 map 容器中增添一个键值对。其中，该键值对的键用 [ ] 运算符中指定的键，其对应的值取决于 map 容器规定键值对中值的数据类型，如果是基本数据类型，则值为 0；如果是 string 类型，其值为 ""，即空字符串（即使用该类型的默认值作为键值对的值）。
    string str_f = map1["f"];
    //可以看到上述指令等效于添加了一项 <"f", "">
    for (auto elem: map1){
        cout << elem.first << " " << elem.second << endl;
    }
    cout << endl;

    //方法二：通过at()成员函数访问
/*     string str_g = map1.at("g");  //抛异常
    cout << "str_g:" << str_g << endl;
    for (auto elem: map1){
        cout << elem.first << " " << elem.second << endl;
    }
    cout << endl; */

    //方法三：通过find()成员函数访问
    string key = "h";
    if (map1.find(key) == map1.end()){
        cout << "no key " << key << endl;
    }else{
        cout << "has key " << key << endl;
    }
}

输出为：

a aa
b bb
c cc
d dd
e ee

a aa
b bb
c cc
d dd
e ee
f 

has key f

本节所介绍的几种方法中，仅从“在 map 容器存储的键值对中，获取指定键对应的值”的角度出发，更推荐使用 at() 成员方法，因为该方法既简单又安全。

4.1.5、map insert成员函数的几种用法

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    //insert插入数据的四种方式
    map<string, string> map1;

    //默认方式：借助[]运算符
    map1["aa"] = "aaaa";
    cout << "map1[aa]:" << map1["aa"] << endl;
    map1["bb"] = "bbbb";
    for (auto elem: map1){
        cout << elem.first << " " << elem.second << endl;
    }
    cout << endl;

    //insert()方式1 无需指定插入位置
    pair<string, string> mypair = {"cc", "cccc"}; //创建一个pair
    pair<map<string, string>::iterator, bool> ret; //创建一个接受insert()方法返回值的pair对象
    ret = map1.insert(mypair);
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
    
    //以右值引用的方式传递临时的键值对变量
    ret = map1.insert({"dd", "dddd"});
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

    //看看插入失败的例子(前面已经有cc了)
    ret = map1.insert({"cc", "cccc"});
    cout << "ret.iter = <{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

    /* 总结:
    从上述执行结果可以看到，程序总共执行了3次插入操作，其中成功2次，失败1次：
    (1)对于插入成功的case，insert返回的pair对象指向新插入键值对的迭代器和值为1的bool变量；
    (2)对于插入失败的base，insert返回想要插入的键值对 和 值为0的bool变量。
    */

    //insert()方式2 支持向map容器的指定位置插入新键值对
    //注: 我觉得这个没啥意义，因为map依然会自动排序
    cout << endl;
    map<string, string>::iterator it = map1.begin();
    pair<string, string> pair2 = {"ee", "eeee"};
    auto iter1 = map1.insert(it, pair2);
    cout << iter1->first << " " << iter1->second << endl;

    cout << endl;
    for (auto iter = map1.begin(); iter != map1.end(); iter++){
        cout << iter->first << " " << iter->second << endl;
    }

    //下面insert的其他用法也就不看了,没啥意思！！


}

输出结果如下：

map1[aa]:aaaa
aa aaaa
bb bbbb

ret.iter = <{cc, cccc}, 1>
ret.iter = <{dd, dddd}, 1>
ret.iter = <{cc, cccc}, 0>

ee eeee

aa aaaa
bb bbbb
cc cccc
dd dddd
ee eeee

4.1.6、map emplace/emplace_hint方法

值得一提的是，实现相同的插入操作，无论是用 emplace() 还是 emplace_hont()，都比 insert() 方法的效率高（后续章节会详细讲解）。

和 insert() 方法相比，emplace() 和 emplace_hint() 方法的使用要简单很多，因为它们各自只有一种语法格式。其中，emplace() 方法的语法格式如下：

template <class... Args>
  pair<iterator,bool> emplace (Args&&... args);

参数 (Args&&... args) 指的是，这里只需要将创建新键值对所需的数据作为参数直接传入即可，此方法可以自行利用这些数据构建出指定的键值对。另外，该方法的返回值也是一个 pair 对象，其中 pair.first 为一个迭代器，pair.second 为一个 bool 类型变量：

• 当该方法将键值对成功插入到 map 容器中时，其返回的迭代器指向该新插入的键值对，同时 bool 变量的值为 true；
• 当插入失败时，则表明 map 容器中存在具有相同键的键值对，此时返回的迭代器指向此具有相同键的键值对，同时 bool 变量的值为 false。

#include <iostream>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main()
{
    map<string, string> map1;
    //构造emplace返回
    pair<map<string, string>::iterator, bool> ret;

    //插入键值对
    ret = map1.emplace("aa","aaaa");
    cout << "1、ret.iter=<{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;

    //新插入键值对
    ret = map1.emplace("bb","bbbb");
    cout << "2、ret.iter=<{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
 
    //插入失败样例
    ret = map1.emplace("aa","aaaa");
    cout << "3、ret.iter=<{" << ret.first->first << ", " << ret.first->second << "}, " << ret.second << ">" << endl;
    
    /*
    可以看到，程序中共执行了 3 次向 map 容器插入键值对的操作，其中前 2 次都成功了，第 3 次由于要插入的键值对的键和 map 容器中已存在的键值对的键相同，因此插入失败。
    */

    //emplace_hint()方法
    //我觉得这个东西没啥意义！！ 虽然可以指定位置插入但是map容器为了保持存储键值对的有序状态还是会移动其位置。


}

输出结果如下：

1、ret.iter=<{aa, aaaa}, 1>
2、ret.iter=<{bb, bbbb}, 1>
3、ret.iter=<{aa, aaaa}, 0>

4.1.7、为什么emplace/emplace_hint的效率更高？

原因很简单，它们向 map 容器插入键值对时，底层的实现方式不同：

• 使用 insert() 向 map 容器中插入键值对的过程是，先创建该键值对，然后再将该键值对复制或者移动到 map 容器中的指定位置；
• 使用 emplace() 或 emplace_hint() 插入键值对的过程是，直接在 map 容器中的指定位置构造该键值对。

也就是说，向 map 容器中插入键值对时，emplace() 和 emplace_hint() 方法都省略了移动键值对的过程，因此执行效率更高。

因此，在实现向 map 容器中插入键值对时，应优先考虑使用 emplace() 或者 emplace_hint()。

4.2、 multimap

和map的区别在于，multimap容器可以存储多个键相同的键值对；其他特性相同。

#include<map>

using namespace std;

multimap容器类模板的定义如下：

template < class Key,                                   // 指定键（key）的类型
           class T,                                     // 指定值（value）的类型
           class Compare = less<Key>,                   // 指定排序规则
           class Alloc = allocator<pair<const Key,T> >  // 指定分配器对象的类型
           > class multimap;

可以看到multimap容器模板有4个参数，其中后两个参数都有默认值。

和map一样，multimap通常只需要设定前两个参数，有些场景可能用到第三个参数，地4个参数几乎不会用到。

表 1 列出了 multimap 类模板提供的常用成员方法及各自的功能。
 

表 1 C++ multimap 容器常用成员方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
find(key)	在 multimap 容器中查找首个键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key)	返回一个指向当前 multimap 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key)	返回一个指向当前 multimap 容器中第一个大于 key 的键值对的迭代器。如果 multimap 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 multimap 容器中存有键值对的个数。
max_size()	返回 multimap 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
insert()	向 multimap 容器中插入键值对。
erase()	删除 multimap 容器指定位置、指定键（key）值或者指定区域内的键值对。
swap()	交换 2 个 multimap 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
clear()	清空 multimap 容器中所有的键值对，使 multimap 容器的 size() 为 0。
emplace()	在当前 multimap 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 multimap 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
count(key)	在当前 multimap 容器中，查找键为 key 的键值对的个数并返回。

和 map 容器相比，multimap 未提供 at() 成员方法，也没有重载 [] 运算符。这意味着，map 容器中通过指定键获取指定指定键值对的方式，将不再适用于 multimap 容器。其实这很好理解，因为 multimap 容器中指定的键可能对应多个键值对，而不再是 1 个。

#include <iostream>
#include <map>

using namespace std;

void print_multimap(std::multimap<string, string> &mmap){
    for(auto iter = mmap.begin(); iter != mmap.end(); iter++){
        cout << iter->first << " " << iter->second << endl;
    }
    cout << endl;
}

int main()
{
    //1、multimap 容器的创建方法(总的来说有5种)

    //1.1、调用multimap类模板的默认构造函数 创建一个空的multimap容器
    std::multimap<string, string> mmap1;
    cout << "mmap1(use less order):" << endl; 
    print_multimap(mmap1);

    //1.2、创建multimap容器的同时 初始化之
    //这种方式会将每个{key,value}对创建成pair类型的键值对，然后用各个键值对初始化multimap容器。
    std::multimap<string, string> mmap2{ {"aa", "aaaa"},
                                         {"bb", "bbbb"},
                                         {"bb", "bbbb"},
                                         {"cc", "cccc"},
                                         {"dd", "dddd"} 
                                        };
    cout << "mmap2(use less order):" << endl; 
    print_multimap(mmap2);

    //实际上，先创建pair然后在初始化效果也是一样的
    std::multimap<string, string> mmap3{ pair<string, string>{"aa", "aaaa"},
                                         pair<string, string>{"bb", "bbbb"},
                                         make_pair("bb", "bbbb"),
                                         make_pair("cc", "cccc"),
                                         make_pair("dd", "dddd"),
                                        };
    cout << "mmap3(use less order):" << endl; 
    print_multimap(mmap3);

    //1.3、通过类模板的拷贝来构造函数
    std::multimap<string, string> mmap4(mmap3);
    cout << "mmap4(use less order):" << endl; 
    print_multimap(mmap4);

    //1.4、支持从已有multimap容器中选定某块区域内的所有键值对,用作初始化新multimap容器
    //multimap的迭代器用法和map完全相同,此处不做过多介绍
    std::multimap<string, string> mmap5(++mmap4.begin(), mmap4.end());
    cout << "mmap5(use less order):" << endl;
    print_multimap(mmap5);

    //1.5、第三个参数默认是std::less表示升序排序,也可以指定std::greater降序排列
    std::multimap<string, string, std::greater<string>> mmap6{
                                                       {"aa", "aaaa"},
                                                       {"bb", "bbbb"},
                                                       {"cc", "cccc"}
                                                    };
    cout << "mmap6(use greater order):" << endl;
    for(auto elem: mmap6){
        cout << elem.first << " " << elem.second << endl;
    }

}

输出如下：

mmap1(use less order):

mmap2(use less order):
aa aaaa
bb bbbb
bb bbbb
cc cccc
dd dddd

mmap3(use less order):
aa aaaa
bb bbbb
bb bbbb
cc cccc
dd dddd

mmap4(use less order):
aa aaaa
bb bbbb
bb bbbb
cc cccc
dd dddd

mmap5(use less order):
bb bbbb
bb bbbb
cc cccc
dd dddd

mmap6(use greater order):
cc cccc
bb bbbb
aa aaaa

如下演示multimap部分成员函数的使用：

#include <iostream>
#include <map>

using namespace std;

void print_multimap(std::multimap<string, string> &mmap){
    for(auto iter = mmap.begin(); iter != mmap.end(); iter++){
        cout << iter->first << " " << iter->second << endl;
    }
    cout << endl;
}

int main()
{
    std::multimap<string, string> mmap2{ {"aa", "aaaa"},
                                         {"bb", "bbbb"},
                                         {"bb", "bbbb"},
                                         {"cc", "cccc"},
                                         {"dd", "dddd"} 
                                        };
    cout << "mmap2(use less order):" << endl; 
    print_multimap(mmap2);

    //如下演示multimap部分成员函数的用法
    
    //输出 multimap 容器存储键值对的数量
    cout << "mmap2.size():" << mmap2.size() << endl;

    //输出 multimap 容器中存储键为 "bb" 的键值对的数量
    cout << "mmap2.count(bb):" << mmap2.count("bb") << endl;

    cout << endl;
    for (auto iter = mmap2.begin(); iter!= mmap2.end(); iter++){
        cout << iter->first << " " << iter->second << endl;
    }
}

输出结果：

mmap2(use less order):
aa aaaa
bb bbbb
bb bbbb
cc cccc
dd dddd

mmap2.size():5
mmap2.count(bb):2

aa aaaa
bb bbbb
bb bbbb
cc cccc
dd dddd

4.3、 set

4.3.1、set简介

C++ STL除了map、multimap还提供有set和multiset两个关联式容器。set/multiset也会像map一样根据键的大小对存储的键值进行排队。只不过set/multiset容器中各键值对的键key和值value是相等的。同理set 容器存储的元素互不相等、multiset则是元素可以相等的set。

#include<set>

using namespace std;

set容器的类模板定义如下：

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

注意，由于 set 容器存储的各个键值对，其键和值完全相同，也就意味着它们的类型相同，因此 set 容器类模板的定义中，仅有第 1 个参数用于设定存储数据的类型。

对于 set 类模板中的 3 个参数，后 2 个参数自带默认值，且几乎所有场景中只需使用前 2 个参数，第 3 个参数不会用到。

4.3.2、创建set容器的5种方法

#include <iostream>
#include <set>

using namespace std;

template<class T> 
void print_set(set<T>& set){
    for(auto iter = set.begin(); iter != set.end(); iter++){
        cout << *iter << endl;
    }
    cout << endl;
}

template<class T>
void print_set(set<T, std::greater<T>>& set){
    for(auto iter = set.begin(); iter != set.end(); iter++){
        cout << *iter << endl;
    }
    cout << endl;
}

int main()
{
    //1、常见的创建set容器的方法

    //1.1、默认构造函数 创建空的set容器
    set<string> set1;
    print_set(set1);

    //1.2、创建set的同时,对其初始化
    set<string> set2{"aa","bb","cc"};
    print_set(set2);

    //1.3、拷贝构造函数,利用已有set进行拷贝创建
    set<string> set3(set2);
    print_set(set3);

    //1.4、取已有set容器中的部分元素初始化新的set容器
    set<string> set4(++set2.begin(), set2.end()); 
    print_set(set4);

    //1.5、默认采用std::less<T>规则,也可以指定排序顺序为 std::greater<T>
    set<string, std::greater<string> > set5{"aa","bb","cc","dd","ee"};
    print_set(set5);
}

输出如下：

aa
bb
cc

aa
bb
cc

bb
cc

ee
dd
cc
bb
aa

4.3.3、set容器的成员函数

表 1 列出了 set 容器提供的常用成员方法以及各自的功能。
 

表 1 C++ set 容器常用成员方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val)	在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)	返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)	返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 set 容器中存有元素的个数。
max_size()	返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
insert()	向 set 容器中插入元素。
erase()	删除 set 容器中存储的元素。
swap()	交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。
clear()	清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。
emplace()	在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
count(val)	在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。

部分成员函数使用：

#include <iostream>
#include <set>

using namespace std;

template<class T> 
void print_set(set<T>& set){
    for(auto iter = set.begin(); iter != set.end(); iter++){
        cout << *iter << endl;
    }
    cout << endl;
}

template<class T>
void print_set(set<T, std::greater<T>>& set){
    for(auto iter = set.begin(); iter != set.end(); iter++){
        cout << *iter << endl;
    }
    cout << endl;
}

int main()
{
    set<string> myset;
    cout << "1、myset.size():" << myset.size() << endl;

    //向set中插入新元素
    myset.insert("aa");
    myset.insert("bb");
    myset.emplace("cc");
    myset.emplace("dd");
    cout << "2、myset.size():" << myset.size() << endl;

    //使用双向迭代器遍历set
    for (auto iter = myset.begin(); iter != myset.end(); ++iter){
        cout << *iter << endl;
    }
}

输出如下：

1、myset.size():0
2、myset.size():4
aa
bb
cc
dd

4.3.4、set的迭代器

        和 map 容器不同，C++ STL 中的 set 容器类模板中未提供 at() 成员函数，也未对 [] 运算符进行重载。因此，要想访问 set 容器中存储的元素，只能借助 set 容器的迭代器。
        C++ STL 标准库为 set 容器配置的迭代器类型为双向迭代器。这意味着，假设 p 为此类型的迭代器，则其只能进行 ++p、p++、--p、p--、*p 操作，并且 2 个双向迭代器之间做比较，也只能使用 == 或者 != 运算符。

在 set 容器类模板提供的所有成员函数中，返回迭代器的成员函数如表 1 所示。
 

表 1 C++ set 容器迭代器方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。通常和 rbegin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val)	在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)	返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)	返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。

注意，以上成员函数返回的迭代器，指向的只是 set 容器中存储的元素，而不再是键值对。另外，以上成员方法返回的迭代器，无论是 const 类型还是非 const 类型，都不能用于修改 set 容器中的值。

值得一提的是，虽然 C++ STL 标准中，set 类模板中包含 lower_bound()、upper_bound()、equal_range() 这 3 个成员函数，但它们更适用于 multiset 容器，几乎不会用于操作 set 容器。

4.3.5、set insert()方法

#include <set> 
#include <string>
#include <iostream>

using namespace std;

int main()
{
    //insert方式像set插入数据

    //1、只要给定目标元素的值,insert()方法就可以将元素添加到容器
    /*
    普通引用方式传参和右值引用方式传参格式的 insert() 方法，返回的都是 pair 类型的值，其包含 2 个数据，一个迭代器和一个 bool 值：
        当向 set 容器添加元素成功时，该迭代器指向 set 容器新添加的元素，bool 类型的值为 true；
        如果添加失败，即证明原 set 容器中已存有相同的元素，此时返回的迭代器就指向容器中相同的此元素，同时 bool 类型的值为 false。
    */
    std::set<string> myset;
    //insert的返回值
    pair<set<string>::iterator, bool> retpair;
    retpair = myset.insert("aa");
    cout << "iter->" << *(retpair.first) << " " << "bool=" << retpair.second << endl;

    string str = "bb";
    retpair = myset.insert(str);
    cout << "iter->" << *(retpair.first) << " " << "bool=" << retpair.second << endl;

    //搞一个插入失败的例子
    retpair = myset.insert("bb");
    cout << "iter->" << *(retpair.first) << " " << "bool=" << retpair.second << endl;

    //2、insert()还可以将新元素插入到set容器的具体位置
    //注：不演示了,没啥意义(还是会自动排序的)！！

    //3、insert() 方法支持向当前 set 容器中插入其它 set 容器指定区域内的所有元素，只要这 2 个 set 容器存储的元素类型相同即可。
    /* 此时语法格式如下:
    template <class InputIterator>
        void insert (InputIterator first, InputIterator last);
    */
    cout << endl;
    std::set<string> set1{"aa","bb","cc", "dd"};
    std::set<string> set2;
    set2.insert(++set1.begin(), set1.end());
    for(auto iter = set2.begin(); iter != set2.end(); iter++){
        cout << *iter << endl;
    }

    //4、一次向set中insert多个元素
    cout << endl;
    std::set<string> set3;
    set3.insert({"aa","bb","cc","dd"});
    for (auto elem: set3){
        cout << elem << endl;
    }
}

除了insert外，C++11还另外提供了2个成员函数 emplace() 和 emplace_hint()；同样实现插入的效果而且效率更高。

4.3.6、emplace()方法

emplace() 和 emplace_hint() 是 C++ 11 标准加入到 set 类模板中的，相比具有同样功能的 insert() 方法，完成同样的任务，emplace() 和 emplace_hint() 的效率会更高。
 

注意，和 insert() 方法一样，虽然 emplace_hint() 方法中指定了添加新元素的位置，但 set 容器为了保持数据的有序状态，可能会移动其位置。个人觉得没啥意义！

#include <set> 
#include <string>
#include <iostream>

using namespace std;

int main()
{
    //1、emplace()方法插入数据
    /* 
    语法格式如下：
        template <class... Args>
            pair<iterator,bool> emplace (Args&&... args);
    另外，该方法的返回值类型为 pair 类型，其包含 2 个元素，一个迭代器和一个 bool 值：
        当该方法将目标元素成功添加到 set 容器中时，其返回的迭代器指向新插入的元素，同时 bool 值为 true；
        当添加失败时，则表明原 set 容器中已存在相同值的元素，此时返回的迭代器指向容器中具有相同键的这个元素，同时 bool 值为 false。
    */
    std::set<string> myset;
    pair<set<string,string>::iterator, bool> ret = myset.emplace("aa");
    cout << "ret.first->" << *(ret.first) << ", ret.second->" << ret.second << endl;
    cout << "myset.size():" << myset.size() << endl;


    //2、emplace_hint()的用法
    //注: 注意，和 insert() 方法一样，虽然 emplace_hint() 方法中指定了添加新元素的位置，但 set 容器为了保持数据的有序状态，可能会移动其位置。所以没啥意义！！！
    /*
    语法格式如下：
        template <class... Args>
            iterator emplace_hint (const_iterator position, Args&&... args);
    和emplace()相比，有一下2点不同:
        该方法需要额外传入一个迭代器，用来指明新元素添加到 set 容器的具体位置（新元素会添加到该迭代器指向元素的前面）；
        返回值是一个迭代器，而不再是 pair 对象。当成功添加元素时，返回的迭代器指向新添加的元素；反之，如果添加失败，则迭代器就指向 set 容器和要添加元素的值相同的元素。
    */
   cout << endl;
   set<string>::iterator iter = myset.emplace_hint(myset.begin(), "gg");
   cout << *iter << endl;
   cout << "myset.size()=" << myset.size() << endl;
   for(auto elem: myset){
     cout << elem << endl;
   }
}

4.3.7、set删除数据erase()/clear()

如果想删除 set 容器存储的元素，可以选择用 erase() 或者 clear() 成员方法。
 

1、set 类模板中，erase() 方法有 3 种语法格式，分别如下：

（1）删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);

（2）删除 position 迭代器指向的元素
iterator  erase (const_iterator position);

（3）删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);

其中，第 1 种格式的 erase() 方法，其返回值为一个整数，表示成功删除的元素个数；

后 2 种格式的 erase() 方法，返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素。

注意，如果要删除的元素就是 set 容器最后一个元素，则 erase() 方法返回的迭代器就指向新 set 容器中最后一个元素之后的位置（等价于 end() 方法返回的迭代器）。

2、如果要清空整个set使用clear()方法

#include <set> 
#include <string>
#include <iostream>

using namespace std;

void print_set(set<string> myset){
    for(auto elem: myset){
        cout << elem << endl;
    }
    cout << endl;
}

int main()
{
    //一、set的erase方法删除数据

    set<string> myset;
    myset.emplace("aa");
    myset.emplace("bb");
    myset.emplace("cc");
    myset.emplace("dd");
    myset.emplace("dd");
    myset.emplace("ee");
    myset.emplace("ff");
    myset.emplace("gg");
    cout << "myset.size:" << myset.size() << endl; 
    print_set(myset);

    //1、删除set容器中值为val的元素
    /*
        删除 set 容器中值为 val 的元素
        size_type erase (const value_type& val);
        返回: 返回值为一个整数，表示成功删除的元素个数；
    */
    
    int num = myset.erase("cc");
    cout << "num:" << num << endl;
    cout << "1.myset.size:" << myset.size() << endl;
    cout << endl;
    //print_set(myset);

    //2、删除pos迭代器指向的元素
    /*
        删除 position 迭代器指向的元素
        iterator  erase (const_iterator position);
        返回: 返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素
    */
    set<string>::iterator iter1 = myset.erase(myset.begin());
    cout << "2.myset.size():" << myset.size() << endl;
    cout << "2.*iter1=" << *iter1 << endl;
    cout << endl;
    //print_set(myset);

    //3、删除[first,last]区间内的所有元素
    /*
        删除 [first,last) 区间内的所有元素
        iterator  erase (const_iterator first, const_iterator last);
        返回: 返回值都是迭代器，其指向的是 set 容器中删除元素之后的第一个元素
    */
    set<string>::iterator iter2 = myset.erase(myset.begin(), --myset.end());
    cout << "3.myset.size():" << myset.size() << endl;
    cout << "*iter2=" << *iter2 << endl;
    cout << endl;
    //print_set(myset);
 
    //二、set的clear方法情况所有元素
    myset.clear();
    cout << "4.myset.size():" << myset.size() << endl;
}

输出如下：

myset.size:7
aa
bb
cc
dd
ee
ff
gg

num:1
1.myset.size:6

2.myset.size():5
2.*iter1=bb

3.myset.size():1
*iter2=gg

4.myset.size():0

4.4、 multiset

前面章节中，对 set 容器做了详细的讲解。回忆一下，set 容器具有以下几个特性：

• 不再以键值对的方式存储数据，因为 set 容器专门用于存储键和值相等的键值对，因此该容器中真正存储的是各个键值对的值（value）；
• set 容器在存储数据时，会根据各元素值的大小对存储的元素进行排序（默认做升序排序）；
• 存储到 set 容器中的元素，虽然其类型没有明确用 const 修饰，但正常情况下它们的值是无法被修改的；
• set 容器存储的元素必须互不相等。

        在此基础上，C++ STL 标准库中还提供有一个和 set 容器相似的关联式容器，即 multiset 容器。所谓“相似”，是指 multiset 容器遵循 set 容器的前 3 个特性，仅在第 4 条特性上有差异。和 set 容器不同的是，multiset 容器可以存储多个值相同的元素。

也就是说，multiset 容器和 set 容器唯一的差别在于， multiset 容器允许存储多个值相同的元素，而 set 容器中只能存储互不相同的元素。

#include <set>

4.4.1、multiset构造函数

multiset 类模板提供的构造函数，和 set 类模板中提供创建 set 容器的构造函数，是完全相同的。这意味着，创建 set 容器的方式，也同样适用于创建 multiset 容器。

4.4.2、multiset常用成员函数

multiset 容器提供的成员方法，和 set 容器提供的完全一样，如表 1 所示。
 

表 1 C++ multiset 容器常用成员方法

成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val)	在 multiset 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)	返回一个指向当前 multiset 容器中第一个大于或等于 val 的元素的双向迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)	返回一个指向当前 multiset 容器中第一个大于 val 的元素的迭代器。如果 multiset 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含所有值为 val 的元素。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 multiset 容器中存有元素的个数。
max_size()	返回 multiset 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
insert()	向 multiset 容器中插入元素。
erase()	删除 multiset 容器中存储的指定元素。
swap()	交换 2 个 multiset 容器中存储的所有元素。这意味着，操作的 2 个 multiset 容器的类型必须相同。
clear()	清空 multiset 容器中所有的元素，即令 multiset 容器的 size() 为 0。
emplace()	在当前 multiset 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()	本质上和 emplace() 在 multiset 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
count(val)	在当前 multiset 容器中，查找值为 val 的元素的个数，并返回。

注意，虽然 multiset 容器和 set 容器拥有的成员方法完全相同，但由于 multiset 容器允许存储多个值相同的元素，因此诸如 count()、find()、lower_bound()、upper_bound()、equal_range()等方法，更常用于 multiset 容器。

#include <set>
#include <iostream>
#include <string>

using namespace std;

void print_multiset(multiset<string> mymultiset){
    for(auto elem:mymultiset){
        cout << elem << " ";
    }
    cout << endl;
}

int main()
{
    //一、multiset构造函数

    //1）默认构造函数(默认采用 std::less<T> 规则,升序排列)
    std::multiset<string> mymultiset1;

    //2)创建变量的同时初始化
    std::multiset<string> mymultiset2{"aa","bb","cc","dd","ee","cc"};
    cout << "mymultiset2:";
    print_multiset(mymultiset2);

    //3) 还提供了拷贝(复制)构造函数
    std::multiset<string> mymultiset3(mymultiset2);
    cout << "mymultiset3:";
    print_multiset(mymultiset3);

    //4)在3的基础上,multiset还支持利用已有multiset容器的部元素来初始化multiset容器
    std::multiset<string> mymultiset4(++mymultiset3.begin(), mymultiset3.end());
    cout << "mymultiset4:";
    print_multiset(mymultiset4);

    //5)修改排序规则为 std::greater<T>
    std::multiset<string, std::greater<string> > mymultiset5{"aa","bb","cc","dd","dd","ee"};
    cout << "mymultiset5:";
    for(auto elem: mymultiset5){
        cout << elem << " ";
    }
    cout << endl;

    //二、multiset常用成员函数
    cout << "mymultiset5.size():" << mymultiset5.size() << endl;
    cout << "mymultiset5.count(dd):" << mymultiset5.count("dd") << endl;
    //添加元素ff
    mymultiset5.emplace("ff");
    //删除所有值为dd的元素
    int num = mymultiset5.erase("dd");
    cout << "删除了 " << num << " 个，值为" << " dd 的元素！" << endl;
    for (auto iter = mymultiset5.begin(); iter != mymultiset5.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;
}

输出如下：

mymultiset2:aa bb cc cc dd ee 
mymultiset3:aa bb cc cc dd ee 
mymultiset4:bb cc cc dd ee 
mymultiset5:ee dd dd cc bb aa 
mymultiset5.size():6
mymultiset5.count(dd):2
删除了 2 个，值为 dd 的元素！
ff ee cc bb aa 

4.5、 C++ STL关联容器排序规则

4.5.0、函数对象(仿函数)
 

（1）概念

重载函数调用操作符()的类，其对象称为函数对象；
函数对象使用重载时的行为类似于函数调用,所以也叫仿函数。 注：关于这块看个具体的例子就知道了。

简单来说：就是有一个类将 () 运算符重载为成员函数了，那么这个类就称为函数对象类、这个类的对象就是函数对象。函数对象本质上是一个对象，但是使用的形式看起来特别像是函数调用，因此也被称为"仿函数"。

本质： 函数对象(仿函数)实际上是类、是对象，不是一个函数。

（2）函数对象使用举例
 

case1：函数对象基本使用举例
 

#include <iostream>
#include <string>

using namespace std;

class CAverage
{
public:
    //重载 () 运算符
    double operator() (int a, int b, int c){
        return (double)(a + b + c)/3;
    }
};


int main()
{
    CAverage average;
    cout << "average(1, 2, 4):" << average(1, 2, 4) << endl;
}

可以看到：
(1) 函数对象在使用时,可以像普通函数那样调用,可以有参数,可以有返回值
(2) average(3, 2, 3)这种用法,使得average看上去像函数的名字,所以称其为函数对象。

case2：函数对象在sort算法中的应用

STL中sort能将区间从小到大排序。sort算法有两个版本；一个是默认、另一个是自定义排序规则。

template <class_Randlt>
void sort(_Randlt first, _RandIt last);

该模板可以用来将区间 [first, last) 中的元素从小到大排序，要求 first、last 是随机访问迭代器。元素比较大小是用<进行的。如果表达式a<b的值为 true，则 a 排在 b 前面；如果a<b的值为 false，则 b 未必排在 a 前面，还要看b<a是否成立，成立的话 b 才排在 a 前面。要使用这个版本的 sort 算法，待排序的对象必须能用<运算符进行比较。

template <class_Randlt, class Pred>
void sort(_Randlt first, _RandIt last, Pred op);

这个版本和第一个版本的差别在于，元素 a、b 比较大小是通过表达式op(a, b)进行的。如果该表达式的值为 true，则 a 比 b 小；如果该表达式的值为 false，也不能认为 b 比 a 小，还要看op(b, a)的值。总之，op 定义了元素比较大小的规则。下面是一个使用 sort 算法的例子。
 

#include <iostream>
#include <algorithm>
#include <string>
#include <ostream>

using namespace std;

//首先定义一个打印函数,用模板实现
template<typename T>
void PrintInterval(T first, T last){
    //用以输出[first, last)区间的元素
    for(; first!=last; first++){
        cout << *first << " ";
    }
    cout << endl;
}

//定义一个类A
class CTest
{
public:
    //成员函数
    int v;
    //定义构造函数
    CTest(int n):v(n) {}
};

//重载 < 操作符
bool operator < (const CTest & o1, const CTest &o2){
    return o1.v < o2.v;
}

//为sort定义一个排序规则
bool GreaterRule(const CTest& o1, const CTest& o2){
    //v值大的元素作为较小的数
    return (o1.v < o2.v);
}

//定义一个函数对象
struct LessTest
{
    bool operator() (const CTest& o1, const CTest o2){
        //v个位数小的元素就作为较小的数
        return (o1.v % 10) < (o2.v % 10);
    }
};

//重载(<<)运算符;此处用于在自定义类中方便输出对象内容
ostream & operator << (ostream & o, const CTest & obj)
{
    o << obj.v;
    return o;
}


int main()
{
    CTest obj[5] = {5, 8, 10, 3, 6};
    sort(obj, obj+5);
    cout << "1)"; 
    PrintInterval(obj, obj + 5); 

    sort(obj, obj+5, GreaterRule);
    cout << "2)"; 
    PrintInterval(obj, obj + 5); 

    sort(obj, obj+5, LessTest());
    cout << "3)"; 
    PrintInterval(obj, obj + 5); 
}

输出如下：

1)3 5 6 8 10 
2)3 5 6 8 10 
3)10 3 5 6 8 

编译至第 2 个sort时，编译器将 sort 实例化得到的函数原型如下：
void sort(A* first, A* last, bool (*op)(const A &, const A &) );

该函数在执行过程中，当要比较两个元素 a、b 的大小时，就是看 op(a, b) 和 op(b, a) 的返回值。本程序中 op 指向 GreaterA,因此就用 GreaterA 定义的规则来比较大小。

编译至第 3 个sort时，编译器将 sort 实例化得到的函数原型如下：
void sort( A* first, A* last, LessA op);

该函数在执行过程中，当要比较两个元素 a、b 的大小时，就是看 op(a, b) 和 op(b, a) 的返回值。本程序中，op(a, b) 等价于 op.opeartor(a, b)，因此就用 LessA 定义的规则来比较大小。

4.5.1、使用函数对象自定义关联容器的排序规则
 

#include <iostream>
#include <set>
#include <string>

using namespace std;

//1、定义函数对象类
class cmp1{
    public:
        //重载()运算符
        bool operator() (const string& a, const string& b){
            //按照字符长度进行排序
            return (a.length() < b.length());
        }
};

//2、定义函数对象类(struct关键字)
struct cmp2{
    bool operator() (const string &a, const string &b){
        //按照字符串的长度进行排序
        return (a.length() < b.length());
    }
};

//3、模板类
template<typename T>
class cmp3{
    public:
        bool operator() (const T& a, const T& b){
            //按照值的大小进行排序
            return a < b;
        }
};


int main()
{
    std::set<string, cmp1> myset1{"aa","bbbbbbb","c","ddd"};
    cout << "1、class函数对象类按照字符长度排序:" ;
    for (auto iter = myset1.begin(); iter!= myset1.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    std::set<string, cmp2> myset2{"aa","bbbbbbb","c","ddd"};
    cout << "2、struct函数对象类按照字符长度排序:";
    for (auto iter = myset1.begin(); iter!= myset1.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

    std::set<string, cmp3<string>> myset3{"aa","bbbbbb","c","ddd"};
    cout << "3、模板函数对象类按照值大小排序";
    for (auto iter = myset3.begin(); iter != myset3.end(); iter++){
        cout << *iter << " ";
    }
    cout << endl;

}

 输出如下：

1、class函数对象类按照字符长度排序:c aa ddd bbbbbbb 
2、struct函数对象类按照字符长度排序:c aa ddd bbbbbbb 
3、模板函数对象类按照值大小排序aa bbbbbb c ddd 

4.5.2、重载关系运算符实现自定义排序

在STL标准库中本身就包含几个内置的排序规则，如下表所示：

排序规则	功能
std::less	底层采用 < 运算符实现升序排序，各关联式容器默认采用的排序规则。
std::greater	底层采用 > 运算符实现降序排序，同样适用于各个关联式容器。
std::less_equal	底层采用 <= 运算符实现升序排序，多用于 multimap 和 multiset 容器。
std::greater_equal	底层采用 >= 运算符实现降序排序，多用于 multimap 和 multiset 容器。

值得注意的是，表中的这些排序规则其底层也是采用函数对象的方式实现的。以 std::less 为例，其底层实现为：

template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
}

在此基础上，当关联式容器中存储的数据类型为自定义的结构体变量或者类对象时，通过对现有排序规则中所用的关系运算符进行重载，也能实现自定义排序规则的目的。

注意，当关联式容器中存储的元素类型为结构体指针变量或者类的指针对象时，只能使用函数对象的方式自定义排序规则，此方法不再适用。

对于如下程序： 

#include <iostream>
#include <string>
#include <set>

using namespace std;

class myString{
public:
    myString(string tmpStr): str(tmpStr){};
    string getStr() const;
private:
    string str;
};

string myString::getStr() const{
    return this->str;
}

bool operator <(const myString &str1, const myString &str2){
    //以字符串长度为标准进行排序
    return (str1.getStr().length() < str2.getStr().length());
}

int main()
{
    std::set<myString> myset;
    //插入后会自动调用myString类的构造函数
    myset.emplace("aaaaa");
    myset.emplace("bbbb");
    myset.emplace("dd");
    myset.emplace("eeeeeeee");

    for(auto iter = myset.begin(); iter!= myset.end(); iter++){
        cout << iter->getStr() << endl;
    }
}

输出如下：

dd
bbbb
aaaaa
eeeeeeee

分析：

在这个程序中，虽然myset容器表面扔采用默认的 std::less 排序规则，但是由于我们对于所使用的 < 运算符进行重载，是的myset容器内部实则是以字符串的长度为基准，对各个myString类对象进行排序。

4.6、 如何修改关联式容器中键值对的键？

        通过前面的学习，已经掌握了所有关联式容器（包括 map、multimap、set 和 multiset）的特性和用法。其中需要指出的是，对于如何修改容器中某个键值对的键，所有关联式容器可以采用同一种解决思路，即先删除该键值对，然后再向容器中添加修改之后的新键值对。

        那么，是否可以不删除目标键值对，而直接修改它的键呢？接下来就围绕此问题，给读者展开详细的讲解。

4.6.1、map/multimap不可修改键值对的键

      首先可以明确的是，map 和 multimap 容器只能采用“先删除，再添加”的方式修改某个键值对的键。原因很简单，C++ STL 标准中明确规定，map 和 multimap 容器用于存储类型为 pair<const K, V> 的键值对。显然，只要目标键值对存储在当前容器中，键的值就无法被修改。

map<int, int> mymap{ {1,10},{2,20} };
//map 容器的键为 const 类型，不能被修改
mymap.begin()->first = 100;
multimap<int, int> mymultimap{ {10,100},{20,200} };
//multimap 容器的键为 const 类型，同样不能被修改
mymultimap.begin()->first = 100;

   上述第3行和第7行尝试修改键的程序都是不能通过编译的。

4.6.2、set/multiset借助const_cast可以修改键

        和 map、multimap 不同，C++ STL 标准中并没有用 const 限定 set 和 multiset 容器中存储元素的类型。换句话说，对于 set 或者 multiset 类型的容器，其存储元素的类型是 T 而不是 const T。

        事实上，对 set 和 multiset 容器中的元素类型作 const 修饰，是违背常理的。举个例子，假设我们使用 set 容器存储多个学生信息，如下是一个表示学生的类：

class student {
public:
    student(string name, int id, int age) :name(name), id(id), age(age) {
    }
    const int& getid() const {
        return id;
    }
    void setname(const string name){
        this->name = name;
    }
    string getname() const{
        return  name;
    }
    void setage(int age){
        this->age = age;
    }
    int getage() const{
        return  age;
    }
private:
    string name;
    int id;
    int age;
};

在创建 set 容器之前，我们还需要为其设计一个排序规则，这里假定以每个学生的 id 做升序排序，其排序规则如下：

class cmp {
public:
    bool operator ()(const student &stua, const student &stub) {
        //按照字符串的长度，做升序排序(即存储的字符串从短到长)
        return  stua.getid() < stub.getid();
    }
};

做完以上所有的准备工作后，就可以创建一个可存储 student 对象的 set 容器了，比如：

set<student, cmp> myset{ {"zhangsan",10,20},{"lisi",20,21},{"wangwu",15,19} };

实际存储数据如下：

{“zhangsan”,10,20}
{“wangwu”,15,19}
{“lisi”,20,21}

        注意，set 容器中每个元素也可以看做是键和值相等的键值对，但对于这里的 myset 容器来说，其实每个 student 对象的 id 才是真正的键，其它信息（name 和 age）只不过是和 id 绑定在一起而已。因此，在不破坏 myset 容器中元素的有序性的前提下（即不修改每个学生的 id），学生的其它信息是应该允许修改的，但有一个前提，即 myset 容器中存储的各个 student 对象不能被 const 修饰（这也是 set 容器中的元素类型不能被 const 修饰的原因）。

例如，在已创建好的 myset 容器的基础上，如下代码尝试修改 myset 容器中某个学生的 name 名字：

set<student>::iterator iter = mymap.begin();
(*iter).setname("xiaoming");

注意，如果读者运行代码会发现，它也是无法通过编译的。

虽然 C++ STL 标准没有用 const 修饰 set 或者 multiset 容器中元素的类型，但也做了其它工作来限制用户修改容器的元素。例如上面代码中，iter 会调用 operator，其返回的是一个 const T& 类型元素。这意味着，C++ STL 标准不允许用户借助迭代器来直接修改 set 或者 multiset 容器中的元素。

那么，如何才能正确修改 set 或 multiset 容器中的元素呢？最直接的方式就是借助 const_cast 运算符，该运算符可以去掉指针或者引用的 const 限定符。

比如，我们只需要借助 const_cast 运算符对上面程序稍作修改，就可以运行成功：

set<student>::iterator iter = mymap.begin();
const_cast<student&>(*iter).setname("xiaoming");

5、无序关联式容器(unordered_map/set/multimap/multiset)-哈希表

5.0、无序关联式容器介绍

5.0.1、什么是无序关联式容器

        继 map、multimap、set、multiset 关联式容器之后，本节再讲解一类“特殊”的关联式容器，它们常被称为“无序容器”、“哈希容器”或者“无序关联容器”。

        和关联式容器一样，无序容器也使用键值对（pair 类型）的方式存储数据。不过，本教程将二者分开进行讲解，因为它们有本质上的不同：

• 关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
• 无序容器的底层实现采用的是哈希表的存储结构。

        C++ STL 底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）。有关哈希表存储结构，读者可阅读《哈希表(散列表)详解》一文做详细了解。

        基于底层实现采用了不同的数据结构，因此和关联式容器相比，无序容器具有以下 2 个特点：

1. 无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，
2. 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

和关联式容器一样，无序容器只是一类容器的统称，其包含有 4 个具体容器，分别为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。

表 1 对这 4 种无序容器的功能做了详细的介绍。
 

表 1 无序容器种类

无序容器	功能
unordered_map	存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。
unordered_multimap	和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。
unordered_set	不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。
unordered_multiset	和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。

可以看到实际上就是前面学过的 map、multimap、set、multiset，前面在加上"unordered"。

5.0.2、如何选择无序容器和关联式容器

        总的来说，如果实际场景涉及大量遍历容器的操作，首选关联式容器；反之，如果如果更多是根据键获取对应的值，则应首选无序容器。

5.1、 unordered_map

5.1.1、unordered_map简介

不废话，就理解成无序的map容器。

ps： unordered_map和map一样键也是不能相等的(注:能相等就是 multimap 了)。

#include <unordered_map>

unordered_map容器模板的定义如下所示：

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

以上 5 个参数中，必须显式给前 2 个参数传值，并且除特殊情况外，最多只需要使用前 4 个参数，各自的含义和功能如表 1 所示。
 

表 1 unordered_map 容器模板类的常用参数

参数	含义
<key,T>	前 2 个参数分别用于确定键值对中键和值的类型，也就是存储键值对的类型。
Hash = hash<Key>	用于指明容器在存储各个键值对时要使用的哈希函数，默认使用 STL 标准库提供的 hash<key> 哈希函数。注意，默认哈希函数只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。
Pred = equal_to<Key>	要知道，unordered_map 容器中存储的各个键值对的键是不能相等的，而判断是否相等的规则，就由此参数指定。默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。

总的来说，当无序容器中存储键值对的键为自定义类型时，默认的哈希函数 hash 以及比较函数 equal_to 将不再适用，只能自己设计适用该类型的哈希函数和比较函数，并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义，后续章节会做详细讲解。

5.1.2、创建unordered_map容器的方法

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

void print_umap(unordered_map<string, string> umap)
{
    for (auto elem : umap){
        cout << elem.first << ":" << elem.second << endl;
    }
    cout << endl;
}

int main()
{
    //一、看看创建 unordered_map 容器的几种方法

    //1. 调用unordered_map的默认构造函数,创建空的 unordered_map 容器。
    std::unordered_map<string, string> umap1;
    print_umap(umap1);
 
    //2. 在创建unordered_map的同时完成是实话
    std::unordered_map<string, string> umap2{
        {"chinese", "97"},
        {"math", "100"},
        {"english", "93"},
        {"pe", "100"}
    };
    //注:我觉得这个最好用！！！！！！！！！！！！！！
    umap2["chemistry"] = "92";
    print_umap(umap2);

    //3. 拷贝构造函数初始化
    std::unordered_map<string, string> umap3(umap2);
    print_umap(umap3);

    //4. 如果不想全拷贝可以使用unordered_map提供的迭代器,选择现有umap容器中的部分区域内的键值对初始化新的umap
    std::unordered_map<string, string> umap4(++umap2.begin(), umap2.end());
    print_umap(umap4);

    //输出 umpa 存储键值对的数量
    cout << "umap4 size:" << umap4.size() << endl;
    for (unordered_map<string, string>::iterator iter = umap4.begin(); iter != umap4.end(); iter++){
        cout << iter->first << ":" << iter->second << endl;
    }
    cout << endl;

    //find()的用法
    string target_key = "chinese";
    unordered_map<string, string>::iterator iter = umap4.find(target_key);
    if (iter == umap4.end()){
        cout << "no " << target_key << endl;
    }else{
        cout << "have " << target_key << endl;
    }
}

5.1.3、unordered_map容器成员函数

unordered_map 既可以看做是关联式容器，更属于自成一脉的无序容器。因此在该容器模板类中，既包含一些在学习关联式容器时常见的成员方法，还有一些属于无序容器特有的成员方法。

表 2 列出了 unordered_map 类模板提供的所有常用的成员方法以及各自的功能。
 

表 2 unordered_map类模板成员方法

成员方法	功能
begin()	返回指向容器中第一个键值对的正向迭代器。
end()	返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有键值对的个数。
max_size()	返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
operator[key]	该模板类中重载了 [] 运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值。注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对。
at(key)	返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常。
find(key)	查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key)	在容器中查找以 key 键的键值对的个数。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
emplace()	向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint()	向容器中添加新键值对，效率比 insert() 方法高。
insert()	向容器中添加新键值对。
erase()	删除指定键值对。
clear()	清空容器，即删除容器中存储的所有键值对。
swap()	交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。
bucket_count()	返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()	返回当前系统中，unordered_map 容器底层最多可以使用多少桶。
bucket_size(n)	返回第 n 个桶中存储键值对的数量。
bucket(key)	返回以 key 为键的键值对所在桶的编号。
load_factor()	返回 unordered_map 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()	返回或者设置当前 unordered_map 容器的负载因子。
rehash(n)	将当前容器底层使用桶的数量设置为 n。
reserve()	将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()	返回当前容器使用的哈希函数对象。

5.1.4、unordered_map迭代器的用法

C++ STL 标准库中，unordered_map 容器迭代器的类型为前向迭代器（又称正向迭代器）。这意味着，假设 p 是一个前向迭代器，则其只能进行 *p、p++、++p 操作，且 2 个前向迭代器之间只能用 == 和 != 运算符做比较。

在 unordered_map 容器模板中，提供了表 1 所示的成员方法，可用来获取指向指定位置的前向迭代器。
 

表 1 C++ unordered_map迭代器相关成员方法

成员方法	功能
begin()	返回指向容器中第一个键值对的正向迭代器。
end()	返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
find(key)	查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。

值得一提的是，equal_range(key) 很少用于 unordered_map 容器，因为该容器中存储的都是键不相等的键值对，即便调用该成员方法，得到的 2 个迭代器所表示的范围中，最多只包含 1 个键值对。事实上，该成员方法更适用于 unordered_multimap 容器（该容器后续章节会做详细讲解）。

5.1.5、unordered_map获取元素的四种方法

①[] ②at() ③find() ④begin()/end()完整遍历

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

void print_umap(unordered_map<string, string> umap)
{
    for (auto elem : umap){
        cout << elem.first << ":" << elem.second << endl;
    }
    cout << endl;
}

int main()
{
    // unordered_map获取元素的四种方法  ①[] ②at() ③find() ④begin()/end()完整遍历
    std::unordered_map<string, string> umap{
        {"chinese", "97"},
        {"math", "100"},
        {"english", "93"},
        {"pe", "100"}
    };
    umap["chemistry"] = "92";
    print_umap(umap);

    //①[]
    cout << "umap[\"math\"]:" << umap["math"] << endl;

    //②at()
    cout << "umap.at(\"math\"):" << umap.at("math") << endl;

    //③find()
    //前面演示过了,此处不在演示

    //④begin()/end()或cbegin()/cend() 完整遍历
    //没啥意思,不在演示
}

5.1.6、unordered_map删除元素的方法

C++ STL 标准库为了方便用户可以随时删除 unordered_map 容器中存储的键值对，unordered_map 容器类模板中提供了以下 2 个成员方法：

• erase()：删除 unordered_map 容器中指定的键值对；
• clear()：删除 unordered_map 容器中所有的键值对，即清空容器。

为了满足不同场景删除 unordered_map 容器中键值对的需要，此容器的类模板中提供了 3 种语法格式的 erase() 方法。

（1）erase() 方法可以接受一个正向迭代器，并删除该迭代器指向的键值对。该方法的语法格式如下：

iterator erase ( const_iterator position );

其中 position 为指向容器中某个键值对的迭代器，该方法会返回一个指向被删除键值对之后位置的迭代器。

（2）我们还可以直接将要删除键值对的键作为参数直接传给 erase() 方法，该方法会自行去 unordered_map 容器中找和给定键相同的键值对，将其删除。erase() 方法的语法格式如下：

size_type erase ( const key_type& k );

其中，k 表示目标键值对的键的值；该方法会返回一个整数，其表示成功删除的键值对的数量。

（3）除了支持删除 unordered_map 容器中指定的某个键值对，erase() 方法还支持一次删除指定范围内的所有键值对，其语法格式如下：

iterator erase ( const_iterator first, const_iterator last );

其中 first 和 last 都是正向迭代器，[first, last) 范围内的所有键值对都会被 erase() 方法删除；同时，该方法会返回一个指向被删除的最后一个键值对之后一个位置的迭代器。

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

void print_umap(unordered_map<string, string> umap)
{
    for (auto elem : umap){
        cout << elem.first << ":" << elem.second << endl;
    }
    cout << endl;
}

int main()
{
    /*unordered_map删除元素。
    1、erase()：删除 unordered_map 容器中指定的键值对；
    2、clear()：删除 unordered_map 容器中所有的键值对，即清空容器。
    */
    std::unordered_map<string, string> umap{
        {"chinese", "97"},
        {"math", "100"},
        {"english", "93"},
        {"pe", "100"}
    };
    umap["chemistry"] = "92";

    print_umap(umap);

    //第一种erase()方法: 指定迭代器进行删除

    //定义一个接受erase()方法的迭代器
    unordered_map<string, string>::iterator ret;
    //删除容器中的第一个键值对
    ret = umap.erase(umap.begin());
    //输出下ret
    cout << "ret " << ret->first << " " << ret->second << endl;
    cout << endl;
    cout << "after erase(umap.begin())" << endl << endl;
    print_umap(umap);

    //第二种erase()方法: 将要删除的键值对的键作为参数直接传给erase()方法
    int delNum = umap.erase("math");
    cout << "delNum:" << delNum << endl;
    print_umap(umap);

    //第三种erase()方法: 根据迭代器范围删除
    auto iter = umap.erase(++umap.begin(), umap.end());
    cout << "umap.size():" << umap.size() << endl;
    print_umap(umap);


    //2、clear()方法
    umap.clear();
    cout << "after clear, umap.size():" << umap.size() << endl;
}

5.1.2、unordered_map成员函数

5.2、 unordered_multimap

5.2.1、unordered_multimap简介

C++ STL 标准库中，除了提供有 unordered_map 无序关联容器，还提供有和 unordered_map 容器非常相似的 unordered_multimap 无序关联容器。

和 unordered_map 容器一样，unordered_multimap 容器也以键值对的形式存储数据，且底层也采用哈希表结构存储各个键值对。两者唯一的不同之处在于，unordered_multimap 容器可以存储多个键相等的键值对，而 unordered_map 容器不行。

另外值得一提得是，STL 标准库中实现 unordered_multimap 容器的模板类并没有定义在以自己名称命名的头文件中，而是和 unordered_map 容器一样，定义在<unordered_map>头文件，且位于 std 命名空间中。因此，在使用 unordered_multimap 容器之前，程序中应包含如下 2 行代码：

#include <unordered_map>

using namespace std;

unordered_multimap 容器模板的定义如下所示：

template < class Key,      //键（key）的类型
           class T,        //值（value）的类型
           class Hash = hash<Key>,  //底层存储键值对时采用的哈希函数
           class Pred = equal_to<Key>,  //判断各个键值对的键相等的规则
           class Alloc = allocator< pair<const Key,T> > // 指定分配器对象的类型
           > class unordered_multimap;

以上 5 个参数中，必须显式给前 2 个参数传值，且除极个别的情况外，最多只使用前 4 个参数，它们各自的含义和功能如表 1 所示。
 

表 1 unordered_multimap 容器模板类的常用参数

参数	含义
<key,T>	前 2 个参数分别用于确定键值对中键和值的类型，也就是存储键值对的类型。
Hash = hash<Key>	用于指明容器在存储各个键值对时要使用的哈希函数，默认使用 STL 标准库提供的 hash<key> 哈希函数。注意，默认哈希函数只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。
Pred = equal_to<Key>	unordered_multimap 容器可以存储多个键相等的键值对，而判断是否相等的规则，由此参数指定。默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。

注意，当 unordered_multimap 容器中存储键值对的键为自定义类型时，默认的哈希函数 hash<key> 以及比较函数 equal_to<key> 将不再适用，这种情况下，需要我们自定义适用的哈希函数和比较函数，并分别显式传递给 Hash 参数和 Pred 参数。

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

void print_ummap( std::unordered_multimap<string, string> ummap){
    for(auto iter = ummap.begin(); iter != ummap.end(); iter++)
    {
        cout << iter->first << ": " << iter->second << endl;
    }
    cout << endl;
}

int main()
{
    //一、创建 unordered_multimap 容器
    //其实和 unordered_map 的几种方法一样
    //1、
    std::unordered_multimap<string, string> ummap1;
    ummap1.insert({"aa", "11"});
    ummap1.insert({"aa", "11"});
    ummap1.insert({"bb", "22"});
    print_ummap(ummap1);

    //2、
    std::unordered_multimap<string, string> ummap2{
            {"aaa", "111"},
            {"bbb", "222"},
            {"ccc", "333"}
        };
    print_ummap(ummap2);
    
    //3、
    std::unordered_multimap<string, string> ummap3(ummap2);
    print_ummap(ummap3);

    //4、
    std::unordered_multimap<string, string> ummap4(++ummap3.begin(), ummap3.end());
    print_ummap(ummap4);

}

5.2.2、unordered_multimap成员函数

和 unordered_map 容器相比，unordered_multimap 容器的类模板中没有重载 [ ] 运算符，也没有提供 at() 成员方法，除此之外它们完全一致。

没有提供 [ ] 运算符和 at() 成员方法，意味着 unordered_multimap 容器无法通过指定键获取该键对应的值，因为该容器允许存储多个键相等的键值对，每个指定的键可能对应多个不同的值。

unordered_multimap 类模板提供的成员方法如表 2 所示。  
 

表 2 unordered_multimap类模板成员方法

成员方法	功能
begin()	返回指向容器中第一个键值对的正向迭代器。
end()	返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有键值对的个数。
max_size()	返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
find(key)	查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key)	在容器中查找以 key 键的键值对的个数。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
emplace()	向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint()	向容器中添加新键值对，效率比 insert() 方法高。
insert()	向容器中添加新键值对。
erase()	删除指定键值对。
clear()	清空容器，即删除容器中存储的所有键值对。
swap()	交换 2 个 unordered_multimap 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。
bucket_count()	返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()	返回当前系统中，unordered_multimap 容器底层最多可以使用多少桶。
bucket_size(n)	返回第 n 个桶中存储键值对的数量。
bucket(key)	返回以 key 为键的键值对所在桶的编号。
load_factor()	返回 unordered_multimap 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()	返回或者设置当前 unordered_multimap 容器的负载因子。
rehash(n)	将当前容器底层使用桶的数量设置为 n。
reserve()	将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()	返回当前容器使用的哈希函数对象。

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    std::unordered_multimap<string, string> ummap1;
    ummap1.emplace("aaa", "111");
    ummap1.emplace("bbb", "222");
    ummap1.emplace("ccc", "333");
    ummap1.emplace("aaa", "111111");

    // 输出ummap的
    cout << "ummap1.size():" << ummap1.size() << endl;

    //范围for语句输出
    for (auto elem: ummap1){
        cout << elem.first << ": " << elem.second << endl;
    }
}

输出如下：

ummap1.size():4
ccc: 333
aaa: 111
aaa: 111111
bbb: 222

5.3、 unordered_set

5.3.1、unordered_set简介

        unordered_set 容器，可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。

总的来说，unordered_set 容器具有以下几个特性：

1. 不再以键值对的形式存储数据，而是直接存储数据的值；
2. 容器内部存储的各个元素的值都互不相等，且不能被修改。
3. 不会对内部存储的数据进行排序（这和该容器底层采用哈希表结构存储数据有关，可阅读《C++ STL无序容器底层实现原理》一文做详细了解）；

        对于 unordered_set 容器不以键值对的形式存储数据，读者也可以这样认为，即 unordered_set 存储的都是键和值相等的键值对，为了节省存储空间，该类容器在实际存储时选择只存储每个键值对的值。

#include <unordered_set>
using namespace std;

unordered_set 容器的类模板定义如下：

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_set;

可以看到，以上 4 个参数中，只有第一个参数没有默认值，这意味着如果我们想创建一个 unordered_set 容器，至少需要手动传递 1 个参数。事实上，在 99% 的实际场景中最多只需要使用前 3 个参数（各自含义如表 1 所示），最后一个参数保持默认值即可。
 

表 1 unordered_set模板类定义

参数	含义
Key	确定容器存储元素的类型，如果读者将 unordered_set 看做是存储键和值相同的键值对的容器，则此参数则用于确定各个键值对的键和值的类型，因为它们是完全相同的，因此一定是同一数据类型的数据。
Hash = hash<Key>	指定 unordered_set 容器底层存储各个元素时，所使用的哈希函数。需要注意的是，默认哈希函数 hash<Key> 只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。
Pred = equal_to<Key>	unordered_set 容器内部不能存储相等的元素，而衡量 2 个元素是否相等的标准，取决于该参数指定的函数。 默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。

注意，如果 unordered_set 容器中存储的元素为自定义的数据类型，则默认的哈希函数 hash<key> 以及比较函数 equal_to<key> 将不再适用，只能自己设计适用该类型的哈希函数和比较函数，并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义，后续章节会做详细讲解。

#include <unordered_set>
#include <string>
#include <iostream>

using namespace std;

void print_uset(std::unordered_set<string> uset){
    for (std::unordered_set<string>::iterator iter = uset.begin(); iter != uset.end(); iter++){
        cout << *iter << endl;
    }
    cout << endl;
}

int main()
{
    //一、创建 unordered_set 容器的几张方法
    //注: 都差不多

    //1、
    std::unordered_set<string> uset1;
    uset1.emplace("aaa");
    uset1.emplace("bbb");
    print_uset(uset1);

    //2、
    std::unordered_set<string> uset2{"111","222","333","444"};
    print_uset(uset2);

    //3、
    std::unordered_set<string> uset3(uset2);
    print_uset(uset3);

    //4、
    std::unordered_set<string> uset4(++uset3.begin(), uset3.end());
    print_uset(uset4);

    //
    cout << "uset2.size():" << uset2.size() << endl;
}

注意，此容器模板类中没有重载 [ ] 运算符，也没有提供 at() 成员方法。不仅如此，由于 unordered_set 容器内部存储的元素值不能被修改，因此无论使用那个迭代器方法获得的迭代器，都不能用于修改容器中元素的值。
 

输出如下：

aaa
bbb

111
222
333
444

444
333
222
111

222
333
444

uset2.size():4

5.3.2、unordered_set成员函数

unordered_set 类模板中，提供了如表 2 所示的成员方法。
 

表 2 unordered_set 类模板成员方法

成员方法	功能
begin()	返回指向容器中第一个元素的正向迭代器。
end();	返回指向容器中最后一个元素之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不过其返回的是 const 类型的正向迭代器。
cend()	和 end() 功能相同，只不过其返回的是 const 类型的正向迭代器。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有元素的个数。
max_size()	返回容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
find(key)	查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key)	在容器中查找值为 key 的元素的个数。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中值为 key 的元素所在的范围。
emplace()	向容器中添加新元素，效率比 insert() 方法高。
emplace_hint()	向容器中添加新元素，效率比 insert() 方法高。
insert()	向容器中添加新元素。
erase()	删除指定元素。
clear()	清空容器，即删除容器中存储的所有元素。
swap()	交换 2 个 unordered_set 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等。
bucket_count()	返回当前容器底层存储元素时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()	返回当前系统中，unordered_set 容器底层最多可以使用多少桶。
bucket_size(n)	返回第 n 个桶中存储元素的数量。
bucket(key)	返回值为 key 的元素所在桶的编号。
load_factor()	返回 unordered_set 容器中当前的负载因子。负载因子，指的是的当前容器中存储元素的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()	返回或者设置当前 unordered_set 容器的负载因子。
rehash(n)	将当前容器底层使用桶的数量设置为 n。
reserve()	将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳 count 个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()	返回当前容器使用的哈希函数对象。

5.4、 unordered_multiset

5.4.1、unordered_multiset简介

所谓“类似”，指的是 unordered_multiset 容器大部分的特性都和 unordered_set 容器相同，包括：

1. unordered_multiset 不以键值对的形式存储数据，而是直接存储数据的值；
2. 该类型容器底层采用的也是哈希表存储结构（可阅读《C++ STL无序容器底层实现原理》一文做详细了解），它不会对内部存储的数据进行排序；
3. unordered_multiset 容器内部存储的元素，其值不能被修改。

和 unordered_set 容器不同的是，unordered_multiset 容器可以同时存储多个值相同的元素，且这些元素会存储到哈希表中同一个桶（本质就是链表）上。

读者可以这样认为，unordered_multiset 除了能存储相同值的元素外，它和 unordered_set 容器完全相同。

另外值得一提的是，实现 unordered_multiset 容器的模板类并没有定义在以该容器名命名的文件中，而是和 unordered_set 容器共用同一个<unordered_set>头文件，并且也位于 std 命名空间。因此，如果程序中需要使用该类型容器，应包含如下代码：

#include <unordered_set>
using namespace std;

unordered_multiset 容器类模板的定义如下：

template < class Key,            //容器中存储元素的类型
           class Hash = hash<Key>,    //确定元素存储位置所用的哈希函数
           class Pred = equal_to<Key>,   //判断各个元素是否相等所用的函数
           class Alloc = allocator<Key>   //指定分配器对象的类型
           > class unordered_multiset;

需要说明的是，在 99% 的实际场景中，最多只需要使用前 3 个参数（各自含义如表 1 所示），最后一个参数保持默认值即可。

表 1 unordered_multiset 模板类定义

参数	含义
Key	确定容器存储元素的类型，如果读者将 unordered_multiset 看做是存储键和值相同的键值对的容器，则此参数则用于确定各个键值对的键和值的类型，因为它们是完全相同的，因此一定是同一数据类型的数据。
Hash = hash<Key>	指定 unordered_multiset 容器底层存储各个元素时所使用的哈希函数。需要注意的是，默认哈希函数 hash<Key> 只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类。
Pred = equal_to<Key>	用于指定 unordered_multiset 容器判断元素值相等的规则。默认情况下，使用 STL 标准库中提供的 equal_to<key> 规则，该规则仅支持可直接用 == 运算符做比较的数据类型。

总之，如果 unordered_multiset 容器中存储的元素为自定义的数据类型，则默认的哈希函数 hash<key> 以及比较函数 equal_to<key> 将不再适用，只能自己设计适用该类型的哈希函数和比较函数，并显式传递给 Hash 参数和 Pred 参数。至于如何实现自定义，后续章节会做详细讲解。

5.4.2、unordered_multiset成员函数

值得一提的是，unordered_multiset 模板类中提供的成员方法，无论是种类还是数量，都和 unordered_set 类模板一样，如表 2 所示。
 

表 2 unordered_multiset 类模板成员方法

成员方法	功能
begin()	返回指向容器中第一个元素的正向迭代器。
end();	返回指向容器中最后一个元素之后位置的正向迭代器。
cbegin()	和 begin() 功能相同，只不过其返回的是 const 类型的正向迭代器。
cend()	和 end() 功能相同，只不过其返回的是 const 类型的正向迭代器。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前容器中存有元素的个数。
max_size()	返回容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
find(key)	查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key)	在容器中查找值为 key 的元素的个数。
equal_range(key)	返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中值为 key 的元素所在的范围。
emplace()	向容器中添加新元素，效率比 insert() 方法高。
emplace_hint()	向容器中添加新元素，效率比 insert() 方法高。
insert()	向容器中添加新元素。
erase()	删除指定元素。
clear()	清空容器，即删除容器中存储的所有元素。
swap()	交换 2 个 unordered_multiset 容器存储的元素，前提是必须保证这 2 个容器的类型完全相等。
bucket_count()	返回当前容器底层存储元素时，使用桶（一个线性链表代表一个桶）的数量。
max_bucket_count()	返回当前系统中，容器底层最多可以使用多少桶。
bucket_size(n)	返回第 n 个桶中存储元素的数量。
bucket(key)	返回值为 key 的元素所在桶的编号。
load_factor()	返回容器当前的负载因子。所谓负载因子，指的是的当前容器中存储元素的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。
max_load_factor()	返回或者设置当前 unordered_multiset 容器的负载因子。
rehash(n)	将当前容器底层使用桶的数量设置为 n。
reserve()	将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。
hash_function()	返回当前容器使用的哈希函数对象。

6、 stl容器适配器

6.0、容器适配器介绍

6.0.1、容器适配器概念介绍

        容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。

        本章将介绍 3 种容器适配器，分别是 stack、queue、priority_queue：

1. stack<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack<T> 模板定义在头文件 stack 中。
2. queue<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。queue<T> 模板定义在头文件 queue 中。
3. priority_queue<T>：是一个封装了 vector<T> 容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。priority_queue<T> 模板定义在头文件 queue 中。

        在详解什么是容器适配器之前，初学者首先要理解适配器的含义。其实，容器适配器中的“适配器”，和生活中常见的电源适配器中“适配器”的含义非常接近。我们知道，无论是电脑、手机还是其它电器，充电时都无法直接使用 220V 的交流电，为了方便用户使用，各个电器厂商都会提供一个适用于自己产品的电源线，它可以将 220V 的交流电转换成适合电器使用的低压直流电。
        从用户的角度看，电源线扮演的角色就是将原本不适用的交流电变得适用，因此其又被称为电源适配器。

        再举个例子。假设一个代码模块A的构成如下：

class A{
public:
    void f1(){}
    void f2(){}
    void f3(){}
    void f4(){}
};

现在我们需要设计一个模板 B，但发现，其实只需要组合一下模块 A 中的 f1()、f2()、f3()，就可以实现模板 B 需要的功能。其中 f1() 单独使用即可，而 f2() 和 f3() 需要组合起来使用，如下所示：

class B{
private:
    A * a;
public:
    void g1(){
        a->f1();
    }
    void g2(){
        a->f2();
        a->f3();
    }
};

        可以看到，就如同是电源适配器将不适用的交流电变得适用一样，模板 B 将不适合直接拿来用的模板 A 变得适用了，因此我们可以将模板 B 称为 B 适配器。

        容器适配器也是同样的道理，简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。容器适配器的底层实现和模板 A、B 的关系是完全相同的，即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。

容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。

6.0.2、三种容器适配器

        STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。其中，各适配器所使用的默认基础容器以及可供用户选择的基础容器，如表 1 所示。

表 1 STL 容器适配器及其基础容器

容器适配器	基础容器筛选条件	默认使用的基础容器
stack	基础容器需包含以下成员函数： empty() size() back() push_back() pop_back() 满足条件的基础容器有 vector、deque、list。	deque
queue	基础容器需包含以下成员函数： empty() size() front() back() push_back() pop_front() 满足条件的基础容器有 deque、list。	deque
priority_queue	基础容器需包含以下成员函数： empty() size() front() push_back() pop_back() 满足条件的基础容器有vector、deque。	vector

不同场景下，由于不同的序列式容器其底层采用的数据结构不同，因此容器适配器的执行效率也不尽相同。但通常情况下，使用默认的基础容器即可。当然，我们也可以手动修改，具体的修改容器适配器基础容器的方法，后续讲解具体的容器适配器会详细介绍。

6.1、 stack 栈适配器

关于堆栈的概念这里就不介绍了，知道后入先出即可。

由于 stack 适配器以模板类 stack<T,Container=deque<T>>（其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于<stack>头文件中，并定义在 std 命名空间里。因此，在创建该容器之前，程序中应包含以下 2 行代码： 

#include <stack>
using namespace std;

6.2、stack适配器成员函数

和其他序列容器相比，stack 是一类存储机制简单、提供成员函数较少的容器。表 1 列出了 stack 容器支持的全部成员函数。

表 1 stack容器适配器支持的成员函数

成员函数	功能
empty()	当 stack 栈中没有元素时，该成员函数返回 true；反之，返回 false。
size()	返回 stack 栈中存储元素的个数。
top()	返回一个栈顶元素的引用，类型为 T&。如果栈为空，程序会报错。
push(const T& val)	先复制 val，再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj)	以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()	弹出栈顶元素。
emplace(arg...)	arg... 可以是一个参数，也可以是多个参数，但它们都只用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素。
swap(stack<T> & other_stack)	将两个 stack 适配器中的元素进行互换，需要注意的是，进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。

#include <stack>
#include <list>
#include <iostream>
using namespace std;

int main()
{
    //1、创建stack适配器

    //方法1:创建一个不包含任何元素的stack适配器,并采用默认的deque
    //上面这行代码，就成功创建了一个可存储 int 类型元素，底层采用 deque 基础容器的 stack 适配器。
    std::stack<int> s1;

    //方法2:上面提到，stack<T,Container=deque<T>> 模板类提供了 2 个参数，通过指定第二个模板类型参数，我们可以使用出 deque 容器外的其它序列式容器，只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可。
    //在介绍适配器时提到，序列式容器中同时包含这 5 个成员函数的，有 vector、deque 和 list 这 3 个容器。因此，stack 适配器的基础容器可以是它们 3 个中任何一个。例如，下面展示了如何定义一个使用 list 基础容器的 stack 适配器：
    std::stack<int, std::list<int>> s2;
 
    //方法3:也可以用一个基础容器来初始化stack适配器,只要该容器的类型和stack底层使用的基础容器类型相同即可。
    std::list<int> list1{1, 2, 3};
    std::stack<int, std::list<int>> s3(list1);

    //方法4:用一个stack容器初始化另一个stack容器
    std::stack<int> s4(s1);

    //2、常用成员函数用法
    cout << "size of s3 is:" << s3.size() << endl;

    //将s3中存储的元素一次弹出,直到为空
    while(!s3.empty()){
        cout << s3.top() << endl;
        s3.pop();
    }
}

6.2、 queue 队列适配器

队列(queue)是典型的 FIFO(先入先出)的数据结构。

https://cplusplus.com/reference/queue/queue/

表 2 queue容器适配器支持的成员函数

成员函数	功能
empty()	当 queue 中没有元素时，该成员函数返回 true；反之，返回 false。
size()	返回 queue 队列中存储元素的个数。
front()	返回队列头部元素。如果队列为空，程序会报错。
back()	返回队列尾部元素。如果对了为空，程序会报错
push	在队列尾部插入一个元素
emplace()	在队列尾部插入一个元素
pop()	移除队列头部的元素

6.3、 priority_queue 优先权队列适配器

    基础容器需包含以下成员函数：
    empty()
    size()
    front()
    push_back()
    pop_back()
    满足条件的基础容器有vector、deque。 默认使用的基础容器是vector。

7. 迭代器适配器

        本章将介绍 5 种迭代器适配器，分别是反向迭代器适配器、插入型迭代器适配器、流迭代器适配器、流缓冲区迭代器适配器、移动迭代器适配器。

        初学者完全可以将迭代器适配器视为普通迭代器。之所以称为迭代器适配器，是因为这些迭代器是在输入迭代器、输出迭代器、正向迭代器、双向迭代器或者随机访问迭代器这些基础迭代器的基础上实现的。也就是说，使用迭代器适配器的过程中，其本质就是在操作某种基础迭代器。

        不同的迭代器适配器，其功能大不相同，这些知识都会在本章中做详细讲解。

8、常用算法

8.1、C++排序算法

8.1.0、C++ STL标准库提供的排序函数

C++ STL 标准库提供有很多实用的排序函数，如表 1 所示。通过调用它们，我们可以很轻松地实现对普通数组或者容器中指定范围内的元素进行排序。
 

表 1 C++ STL 排序函数

函数名	用法
sort (first, last)	对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序。
stable_sort (first, last)	和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置。
partial_sort (first, middle, last)	从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中。
partial_sort_copy (first, last, result_first, result_last)	从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中。
is_sorted (first, last)	检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。
is_sorted_until (first, last)	和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器。
void nth_element (first, nth, last)	找到 [first, last) 范围内按照排序规则（默认按照升序排序）应该位于第 nth 个位置处的元素，并将其放置到此位置。同时使该位置左侧的所有元素都比其存放的元素小，该位置右侧的所有元素都比其存放的元素大。

对于表 1 中罗列的这些函数，本教程会一一进行讲解，这里先介绍 sort() 函数。

8.1.1、C++ sort()排序函数

#include <algorithm>

using namespace std;

sort() 函数是基于快速排序实现的，有关快速排序的具体实现过程。

需要注意的是，sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 sort() 函数：

1. 容器支持的迭代器类型必须为随机访问迭代器。这意味着，sort() 只对 array、vector、deque 这 3 个容器提供支持。
2. 如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
3. sort() 函数在实现排序时，需要交换容器中元素的存储位置。这种情况下，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

另外还需要注意的一点是，对于指定区域内值相等的元素，sort() 函数无法保证它们的相对位置不发生改变。

sort() 函数有 2 种用法，其语法格式分别为：

//对 [first, last) 区域内的元素做默认的升序排序
void sort (RandomAccessIterator first, RandomAccessIterator last);
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print_vec(std::vector<int> vec){
    for(auto elem: vec){
        cout << elem << " ";
    }
    cout << endl;
}

//以普通函数的方式实现自定义排序规则
bool mycomp(int i, int j){
    return (i < j);
}

//以函数对象的方式实现自定义排序规则
class mycomp2{
    public:
        bool operator() (int i, int j){
            return (i < j);
        }
};


int main()
{
    std::vector<int> myvec{77,66,55,44,33,22,11};
    print_vec(myvec);
    //调用第一种格式对前五个元素进行排序
    std::sort(myvec.begin(), myvec.begin() + 4);
    print_vec(myvec);

    //调用第二种语法格式，通过调用自定义比较规则进行排序
    //std::sort(myvec.begin(), myvec.end(), mycomp());
    std::sort(myvec.begin(), myvec.end(), mycomp2());
    print_vec(myvec);
}

输出如下：

77 66 55 44 33 22 11 
44 55 66 77 33 22 11 
11 22 33 44 55 66 77 

8.1.2、C++ stable_sort()

#include <algorithm>
using namespace std;

         当指定范围内包含多个相等的元素时，sort() 排序函数无法保证不改变它们的相对位置。那么，如果既要完成排序又要保证相等元素的相对位置，该怎么办呢？可以使用 stable_sort() 函数。

有些场景是需要保证相等元素的相对位置的。例如对于一个保存某种事务（比如银行账户）的容器，在处理这些事务之前，为了能够有序更新这些账户，需要按照账号对它们进行排序。而这时就很有可能出现相等的账号（即同一账号在某段时间做多次的存取钱操作），它们的相对顺序意味着添加到容器的时间顺序，此顺序不能修改，否则很可能出现账户透支的情况。

值得一提的是，stable_sort() 函数完全可以看作是 sort() 函数在功能方面的升级版。换句话说，stable_sort() 和 sort() 具有相同的使用场景，就连语法格式也是相同的（后续会讲），只不过前者在功能上除了可以实现排序，还可以保证不改变相等元素的相对位置。

并且，table_sort() 函数的用法也有 2 种，其语法格式和 sort() 函数完全相同（仅函数名不同）：

//对 [first, last) 区域内的元素做默认的升序排序
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
//按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

其中，first 和 last 都为随机访问迭代器，它们的组合 [first, last) 用来指定要排序的目标区域；另外在第 2 种格式中，comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater<T>），也可以是自定义的排序规则。

8.1.3、C++ partial_sort()排序

#include <algorithm>
using namespace std;

    假设这样一种情境，有一个存有 100 万个元素的容器，但我们只想从中提取出值最小的 10 个元素，该如何实现呢？
    通过前面的学习，读者可能会想到使用 sort() 或者 stable_sort() 排序函数，即通过对容器中存储的 100 万个元素进行排序，就可以成功筛选出最小的 10 个元素。但仅仅为了提取 10 个元素，却要先对 100 万个元素进行排序，可想而知这种实现方式的效率是非常低的。
    对于解决类似的问题，C++ STL 标准库提供了更高效的解决方案，即使用 partial_sort() 或者 partial_sort_copy() 函数，本节就对这 2 个排序函数的功能和用法做详细的讲解。

        要知道，一个函数的功能往往可以从它的函数名中体现出来，以 partial_sort() 函数为例，partial sort 可直译为“部分排序”。partial_sort() 函数的功能确是如此，即该函数可以从指定区域中提取出部分数据，并对它们进行排序。

//按照默认的升序排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last);
//按照 comp 排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last,
                   Compare comp);

其中，first、middle 和 last 都是随机访问迭代器，comp 参数用于自定义排序规则。

        partial_sort() 函数会以交换元素存储位置的方式实现部分排序的。具体来说，partial_sort() 会将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序。
        

需要注意的是，partial_sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 partial_sort() 函数：

• 容器支持的迭代器类型必须为随机访问迭代器。这意味着，partial_sort() 函数只适用于 array、vector、deque 这 3 个容器。
• 当选用默认的升序排序规则时，容器中存储的元素类型必须支持 <小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
• partial_sort() 函数在实现过程中，需要交换某些元素的存储位置。因此，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void print_vec(std::vector<int> vec){
    for(auto elem: vec){
        cout << elem << " ";
    }
    cout << endl;
}

//以普通函数的方式实现自定义排序规则
bool mycomp(int i, int j){
    return (i > j);
}

//以函数对象的方式实现自定义排序规则
class mycomp2{
    public:
        bool operator() (int i, int j){
            return (i > j);
        }
};

int main()
{
    std::vector<int> myvec{9,7,5,3,1,2,4,6,8};
    print_vec(myvec);
    //以默认的升序排序作为排序规则,将myvec中最小的5个元素移动到开头位置并排好序
    std::partial_sort(myvec.begin(), myvec.begin()+5, myvec.end());
    print_vec(myvec);

    //以指定的mycomp2作为排序规则，将myvec中最大的5个元素移动到开头位置并排好序
    std::partial_sort(myvec.begin(), myvec.begin()+5, myvec.end(), mycomp2());
    print_vec(myvec);

}

8.1.4、C++ partial_sort_copy()排序

partial_sort_copy() 函数的功能和 partial_sort() 类似，唯一的区别在于，前者不会对原有数据做任何变动，而是先将选定的部分元素拷贝到另外指定的数组或容器中，然后再对这部分元素进行排序。
 

8.1.5、C++ nth_element()用法

#include <nth_element>
using namespace std;

前面章节中，已经给大家介绍了 sort()、stable_sort()、partial_sort() 这些函数的功能和用法，本节再介绍一个排序函数，即 nth_element() 函数。

不过，在系统讲解 nth_element() 函数之前，我们先形成一个共识，即在有序序列中，我们可以称第 n 个元素为整个序列中“第 n 大”的元素。比如，下面是一个升序序列：

2 4 6 8 10

在这个序列中，我们可以称元素 6 为整个序列中“第 3 小”的元素，并位于第 3 的位置处；同样，元素 8 为整个序列中“第 4 小”的元素，并位于第 4 的位置处。

        简单的理解 nth_element() 函数的功能，当采用默认的升序排序规则（std::less<T>）时，该函数可以从某个序列中找到第 n 小的元素 K，并将 K 移动到序列中第 n 的位置处。不仅如此，整个序列经过 nth_element() 函数处理后，所有位于 K 之前的元素都比 K 小，所有位于 K 之后的元素都比 K 大。

举个例子，对于如下序列

        3  4  1  2  5

假设按照升序排序，并通过nth_element()函数查找此序列中第3小的元素，则最终得到的序列可能如下：

        2  1  3  4  5

显然，nth_element() 函数找到了第 3 小的元素 3 并将其位于第 3 的位置，同时元素 3 之前的所有元素都比该元素小，元素 3 之后的所有元素都比该元素大。

nth_element() 函数有以下 2 种语法格式：

//排序规则采用默认的升序排序
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last);
//排序规则为自定义的 comp 排序规则
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last,
                  Compare comp);

其中，各个参数的含义如下：

• first 和 last：都是随机访问迭代器，[first, last) 用于指定该函数的作用范围（即要处理哪些数据）；
• nth：也是随机访问迭代器，其功能是令函数查找“第 nth 大”的元素，并将其移动到 nth 指向的位置；
• comp：用于自定义排序规则。

注意，鉴于 nth_element() 函数中各个参数的类型，其只能对普通数组或者部分容器进行排序。换句话说，只有普通数组和符合以下全部条件的容器，才能使用使用 nth_element() 函数：

1. 容器支持的迭代器类型必须为随机访问迭代器。这意味着，nth_element() 函数只适用于 array、vector、deque 这 3 个容器。
2. 当选用默认的升序排序规则时，容器中存储的元素类型必须支持 <小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
3. nth_element() 函数在实现过程中，需要交换某些元素的存储位置。因此，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

参考： STL教程：C++ STL快速入门（非常详细）