什么是容器？

简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法（也就是数据结构）。

STL 提供有 3 类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器。

容器种类	功能
序列容器	主要包括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++）是不支持的。

C++ STL迭代器（iterator）

数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的，利用泛型技术，将它们设计成适用所有容器的通用算法，从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置，它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。于是乎，迭代器就产生了。

简单来讲，迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

迭代器类别

STL 标准库为每一种标准容器定义了一种迭代器类型，这意味着，不同容器的迭代器也不同，其功能强弱也有所不同。

容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。

常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。

输入迭代器和输出迭代器比较特殊，它们不是把数组或容器当做操作对象，而是把输入流/输出流作为操作对象。有关这 2 个迭代器，我们会在后续章节做详细介绍。

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个元素的引用。

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

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

注意，容器适配器 stack 和 queue 没有迭代器，它们包含有一些成员函数，可以用来对元素进行访问。

迭代器的定义方式

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

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

值得一提的是，表 2 中的反向迭代器全称为 “反向迭代器适配器”，后续章节会做详细讲解，这里读者只需要知道其用法即可。

通过定义以上几种迭代器，就可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。

常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。

反向迭代器和正向迭代器的区别在于：

对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

注意，以上 4 种定义迭代器的方式，并不是每个容器都适用。

迭代器示例

以vector示例：

//遍历 vector 容器。
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
    cout << "第一种遍历方法：" << endl;
    //size返回元素个数
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; //像普通数组一样使用vector容器
    //创建一个正向迭代器，当然，vector也支持其他 3 种定义迭代器的方式
    
       cout << endl << "第二种遍历方法：" << endl;
       vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    
       cout << endl << "第三种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";
   
       cout << endl << "第四种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) { //间隔一个输出
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}

运行结果为：

第一种遍历方法：

1 2 3 4 5 6 7 8 9 10

第二种遍历方法：

1 2 3 4 5 6 7 8 9 10

第三种遍历方法：

1 2 3 4 5 6 7 8 9 10

第四种遍历方法：

1 3 5 7 9

再举一个例子，我们知道，list 容器的迭代器是双向迭代器。假设 v 和 i 的定义如下：

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

则以下代码是合法的：

1 2	for(i = v.begin(); i != v.end(); ++i) cout << *i;

以下代码则不合法，因为双向迭代器不支持用“<”进行比较：

1 2	for(i = v.begin(); i < v.end(); ++i) cout << *i;

以下代码也不合法，因为双向迭代器不支持用下标随机访问元素：

1 2	for(int i=0; i<v.size(); ++i) cout << v[i];

以上有关 vector、list 容器的具体用法，后续章节会做详细讲解。

STL序列式容器

序列式容器：线性排列的存储数据，并且该类容器的数据的排序与容器内的元素无关。

序列式容器分类

序列容器是指一类容器，包含以下几类容器：

**array<T,N>(数组容器)**：C++本身提供的容器。此类容器初始化之后，长度不可表，也就是说不可以增加和删除，只能对元素访问或修改。
**vector(向量容器)**：长度可变，即空间不足时，会自动申请更多内存。在尾部增加或删除元素时效率最高（时间复杂度O(1) ），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶）;
deque（双端队列容器）：和 vector 非常相似。头尾增加删除高效率（O(1)）,其它位置效率极差（O(n)）。
list（链表容器）：双向链表的存储方式，长度课表，任何位置增加删除快（时间复杂度都为常数阶 O(1)），但是访问慢。
forward_list（正向链表容器）：和list类似，但是是以单链表存储，比list快且省内存。

注意，其实除此之外，stack 和 queue 本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器，有关它们的介绍，会放到后续章节中。

容器中常见的函数成员

序列容器包含一些相同的成员函数，它们的功能也相同，本教程会在某个容器的上下文中详细介绍下面的每个函数，但对于每种类型的容器不会重复介绍它们的细节。

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

列表中 - 表明对应的容器并没有定义这个函数。

2.
list 和 forward_list 容器彼此非常相似，forward_list 中包含了 list 的大部分成员函数，而未包含那些需要反向遍历的函数。表 3 展示了 list 和 forward_list 的函数成员。

函数成员	函数功能	list	forward_list
begin()	返回指向容器中第一个元素的迭代器。	是	是
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器。	是	是
rbegin()	返回指向最后一个元素的迭代器。	是	-
rend()	返回指向第一个元素所在位置前一个位置的迭代器。	是	-
cbegin()	和begin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。	是	是
before_begin()	返回指向第一个元素前一个位置的迭代器。	-	是
cbefore_begin()	和before_begin()功能相同，只不过在其基础上，增加了const属性，即不能用该指针修改元素的值。	-	是
cend()	和end()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。	是	是
crbegin()	和rbegin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。	是	-
crend()	和rend()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。	是	-
assign()	用新元素替换原有内容。	是	是
operator=()	复制同类型容器的元素，或者用初始化列表替换现有内容。	是	是
size()	返回实际元素个数。	是	-
max_size()	返回元素个数的最大值，这通常是一个很大的值，一般是2-1，所以我们很少会用到这个函数。	是	是
resize()	改变实际元素的个数。	是	是
empty()	判断容器中是否有元素，若无元素，则返回true；反之，返回false。	是	是
front()	返回容器中第一个元素的引用。	是	是
back()	返回容器中最后一个元素的引用。	是	-
push_back()	在序列的尾部添加一个元素。	是	-
push_front()	在序列的起始位置添加一个元素。	是	是
emplace()	在指定位置直接生成一个元素。	是	-
emplace_after()	在指定位置的后面直接生成一个元素。	-	是
emplace_back()	在序列尾部生成一个元素。	是	-
cmplacc_front()	在序列的起始位生成一个元索。	是	是
insert()	在指定的位置插入一个或多个元素。	是	-
insert_after()	在指定位置的后面插入一个或多个元素。	-	是
pop_back()	移除序列尾部的元素。	是	-
pop_front()	移除序列头部的元素。	是	是
reverse()	反转容器中某一段的元素。	是	是
erase()	移除指定位置的一个元素或一段元素。	是	-
erase_after()	移除指定位置后面的一个元素或一段元素。	-	是
remove()	移除所有和参数匹配的元素。	是	是
remove_if()	移除满足一元函数条件的所有元素。	是	是
unique()	移除所有连续重复的元素。	是	是
clear()	移除所有的元素，容器大小变为0。	是	是
swap()	交换两个容器的所有元素。	是	是
sort()	对元素进行排序。	是	是
merge()	合并两个有序容器。	是	是
splice()	移动指定位置前面的所有元素到另一个同类型的list中。	是	-
splice_after()	移动指定位置后面的所有元素到另一个同类型的list中。	-	是

array(STL array)序列容器

基本介绍

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

array容器大小固定，无法动态扩展和收缩，只允许访问或替换。

基本使用

array 容器以类模板的形式定义在头文件，并位于命名空间 std 中，如下所示：

namespace std{
    template <typename T, size_t N>
    class array;
}

因此，在使用该容器之前，代码中需引入头文件，并默认使用 std 命令空间，如下所示：

1 2	#include <array> using namespace std;

在 array<T,N> 类模板中，T 用于指明容器中的存储的具体数据类型，N 用于指明容器的大小，需要注意的是，这里的 N 必须是常量，不能用变量表示。

array 容器有多种初始化方式，如下代码展示了如何创建具有 10 个 double 类型元素的 array 容器：

1	std::array<double, 10> values;

提示，如果程序中已经默认指定了 std 命令空间，这里可以省略 std::。

由此，就创建好了一个名为 values 的 array 容器，其包含 10 个浮点型元素。但是，由于未显式指定这 10 个元素的值，因此使用这种方式创建的容器中，各个元素的值是不确定的（array 容器不会做默认初始化操作）。

通过如下创建 array 容器的方式，可以将所有的元素初始化为 0 或者和默认元素类型等效的值：

1	std::array<double, 10> values {};

使用该语句，容器中所有的元素都会被初始化为 0.0。

当然，在创建 array 容器的实例时，也可以像创建常规数组那样对元素进行初始化：

1	std::array<double, 10> values {0.5,1.0,1.5,,2.0};

可以看到，这里只初始化了前 4 个元素，剩余的元素都会被初始化为 0.0。图 1 说明了这一点。

除此之外，array 容器还提供有很多功能实用的成员函数，如表 2 所示。

成员函数	功能
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 容器中的所有元素，但前提是它们具有相同的长度和类型。

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

另外，在头文件中还重载了 get() 全局函数，该重载函数的功能是访问容器中指定的元素，并返回该元素的引用。

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

例如代码演示了表 2 中一部分成员函数的用法和功能：

#include <iostream>
//需要引入 array 头文件
#include <array>
using namespace std;
int main()
{
    std::array<int, 4> values{};
    //初始化 values 容器为 {0,1,2,3}
    for (int i = 0; i < values.size(); i++) {
        values.at(i) = i;
    }
    //使用 get() 重载函数输出指定位置元素
    cout << get<3>(values) << endl;
    //如果容器不为空，则输出容器中所有的元素
    if (!values.empty()) {
        for (auto val = values.begin(); val < values.end(); val++) {
            cout << *val << " ";
        }
    }
}

注意，代码中的 auto 关键字，可以使编译器自动判定变量的类型。运行这段代码，输出结果为：

0 1 2 3

array随机访问迭代器

STL 为 array 容器配备了随机访问迭代器，该类迭代器是功能最强大的迭代器。

在 array 容器的模板类中，和随机访问迭代器相关的成员函数如表 1 所示。

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

这些成员函数的具体功能下图所示。

array容器访问元素

当 array 容器创建完成之后，最常做的操作就是获取其中的元素，甚至有时还会通过循环结构获取多个元素。本节就对获取容器中元素的方法做个汇总。

1.
访问array容器中单个元素

首先，可以通过容器名[]的方式直接访问和使用容器中的元素，这和 C++ 标准数组访问元素的方式相同，例如：

1	values[4] = values[3] + 2.O*values[1];

此行代码中，第 5 个元素的值被赋值为右边表达式的值。需要注意的是，使用如上这样方式，由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到。

为了能够有效地避免越界访问的情况，可以使用 array 容器提供的 at() 成员函数，例如:

1	values.at (4) = values.at(3) + 2.O*values.at(1);

这行代码和前一行语句实现的功能相同，其次当传给 at() 的索引是一个越界值时，程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时，建议大家使用 at()，除非确定索引没有越界。

读者可能有这样一个疑问，即为什么 array 容器在重载 [] 运算符时，没有实现边界检查的功能呢？答案很简单，因为性能。如果每次访问元素，都去检查索引值，无疑会产生很多开销。当不存在越界访问的可能时，就能避免这种开销。

除此之外，array 容器还提供了 get 模板函数，它是一个辅助函数，能够获取到容器的第 n 个元素。需要注意的是，该模板函数中，参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。也就是说，它只能访问模板参数指定的元素，编译器在编译时会对它进行检查。

2.
访问array容器中多个元素

array 容器提供的 size() 函数能够返回容器中元素的个数（函数返回值为 size_t 类型），所以能够像下面这样去逐个提取容器中的元素，并计算它们的和：

double total = 0;
for(size_t i = 0 ; i < values.size() ; ++i)
{
	total += values[i];
}

size() 函数的存在，为 array 容器提供了标准数组所没有的优势，即能够知道它包含多少元素。

并且，接受数组容器作为参数的函数，只需要通过调用容器的成员函数 size()，就能得到元素的个数。除此之外，通过调用 array 容器的 empty() 成员函数，即可知道容器中有没有元素（如果容器中没有元素，此函数返回 true），如下所示：

if(values.empty())
	std::cout << "The container has no elements.\n";
else
	std::cout << "The container has "<< values.size()<<"elements.\n";

然而，很少会创建空的 array 容器，因为当生成一个 array 容器时，它的元素个数就固定了，而且无法改变，所以生成空 array 容器的唯一方法是将模板的第二个参数指定为 0，但这种情况基本不可能发生。

array 容器之所以提供 empty() 成员函数的原因，对于其他元素可变或者元素可删除的容器（例如 vector、deque 等）来说，它们使用 empty() 时的机制是一样的，因此为它们提供了一个一致性的操作。

除了借助 size() 外，对于任何可以使用迭代器的容器，都可以使用基于范围的循环，因此能够更加简便地计算容器中所有元素的和，比如：

1
2
3

double total = 0;
for(auto&& value : values)
	total += value;

读者可以这样认为，array 容器就是普通数组的“升级版”，使用普通数组能实现的，使用 array 容器都可以实现，而且无论是代码功能的实现效率，还是程序执行效率，都比普通数组更高。

vector序列容器

基本介绍

vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++ 普通数组的“升级版”。

不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

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

vector 容器以类模板 vector（ T 表示存储元素的类型）的形式定义在头文件中，并位于 std 命名空间中。因此，在创建该容器之前，代码中需包含如下内容：

1 2	#include <vector> using namespace std;

注意，std 命名空间也可以在使用 vector 容器时额外注明，两种方式都可以。

vector初始化

初始化vector容器的方式有很多，如下：

1.
创建存储 double 类型元素的一个 vector 容器

1	std::vector<double> values;

这时是一个空的vector容器。

调用reserve()成员函数来增加容器的容量：

1	values.reserve(20);

2.
除了创建空 vector 容器外，还可以在创建的同时指定初始值以及元素个数，比如：

1	std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};

这样就创建了一个含有 8 个素数的 vector 容器。

3.
在创建 vector 容器时，也可以指定元素个数：

1	std::vector<double> values(20);

如此，values 容器开始时就有 20 个元素，它们的默认初始值都为 0。

如果不想用 0 作为默认值，也可以指定一个其它值，例如：

1	std::vector<double> values(20, 1.0);

第二个参数指定了所有元素的初始值，因此这 20 个元素的值都是 1.0。

4.
通过存储元素类型相同的其它 vector 容器，也可以创建新的 vector 容器，例如：

1 2	std::vector<char>value1(5, 'c'); std::vector<char>value2(value1);

由此，value2 容器中也具有 5 个字符 ‘c’。在此基础上，如果不想复制其它容器中所有的元素，可以用一对指针或者迭代器来指定初始值的范围，例如：

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);//value2保存{1,2,3}

由此，value2 容器中就包含了 {1,2,3} 这 3 个元素。

vector的成员函数

函数成员	函数功能
begin()	返回指向容器中第一个元素的迭代器。
end()	返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和begin()结合使用。
rbegin()	返回指向最后一个元素的迭代器。
rend()	返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()	和 begin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
cend()	和end()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
crbegin()	和rbegin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
crend()	和rend()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
size()	返回实际元素个数。
max_size()	返回元素个数的最大值。这通常是一个很大的值，一般是2-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()	在序列尾部生成一个元素。

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

vector容器迭代器的使用

略

vector容器访问元素

访问vector容器中单个元素
1. 使用容器名[n]这种获取元素的方式。需要确保下标 n 的值不会超过容器的容量（可以通过 capacity() 成员函数获取），否则会发生越界访问的错误。
2. vector 容器也提供了 at() 成员函数，当传给 at() 的索引会造成越界时，会抛出std::out_of_range异常。
3. vector 容器还提供了 2 个成员函数，即 front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用，通过利用这 2 个函数返回的引用，可以访问（甚至修改）容器中的首尾元素。
4. vector 容器还提供了 data() 成员函数，该函数的功能是返回指向容器中首个元素的指针。通过该指针也可以访问甚至修改容器中的元素。```c

#include
#include
using namespace std;
int main()
{
vector values{1,2,3,4,5};
//输出容器中第 3 个元素的值
cout << *(values.data() + 2) << endl;
//修改容器中第 2 个元素的值
*(values.data() + 1) = 10;
cout << *(values.data() + 1) << endl;
return 0;
}



2. 访问vector容器中多个元素

   1. 
可以借助 size() 成员函数，该函数可以返回 vector 容器中实际存储的元素个数。
```c
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> values{1,2,3,4,5};
	for (auto&& value : values)
		cout << value << " ";
	return 0;
}

2.
可以使用 vector 迭代器遍历 vector 容器，这里以 begin()/end() 为例：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> values{1,2,3,4,5};
	for (auto first = values.begin(); first < values.end(); ++first) {
		cout << *first << " ";
	}
	return 0;
}

vector容量（capacity）和大小（size

capacity和size的区别

vector 容器的容量（用 capacity 表示），指的是在不分配更多内存的情况下，容器可以保存的最多元素个数；而 vector 容器的大小（用 size 表示），指的是它实际所包含的元素个数。

修改vector容器的容量和大小

调用 reserve() 成员函数来增加容器的容量（但并不会改变存储元素的个数）；而通过调用成员函数 resize() 可以改变容器的大小，并且该函数也可能会导致 vector 容器容量的增加。比如说：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>value{ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
    cout << "value 容量是：" << value.capacity() << endl;
    cout << "value 大小是：" << value.size() << endl;
    value.reserve(20);
    cout << "value 容量是(2)：" << value.capacity() << endl;
    cout << "value 大小是(2)：" << value.size() << endl;
    //将元素个数改变为 21 个，所以会增加 6 个默认初始化的元素
    value.resize(21);
    //将元素个数改变为 21 个，新增加的 6 个元素默认值为 99。
    //value.resize(21,99);
    //当需要减小容器的大小时，会移除多余的元素。
    //value.resize(20);
    cout << "value 容量是(3)：" << value.capacity() << endl;
    cout << "value 大小是(3)：" << value.size() << endl;
    return 0;
}

运行结果为：

value 容量是：15

value 大小是：15

value 容量是(2)：20

value 大小是(2)：15

value 容量是(3)：30

value 大小是(3)：21

程序中给出了关于 resize() 成员函数的 3 种不同的用法，有兴趣的读者可自行查看不同用法的运行结果。

仅通过 reserve() 成员函数增加 value 容器的容量，其大小并没有改变；但通过 resize() 成员函数改变 value 容器的大小，它的容量可能会发生改变。另外需要注意的是，通过 resize() 成员函数减少容器的大小（多余的元素会直接被删除），不会影响容器的容量。

vector容器容量和大小的数据类型

在实际场景中，我们可能需要将容器的容量和大小保存在变量中，要知道 vector 对象的容量和大小类型都是 vector::size_type 类型。因此，当定义一个变量去保存这些值时，可以如下所示：

1 2	vector<int>::size_type cap = value.capacity(); vector<int>::size_type size = value.size();

size_type 类型是定义在由 vector 类模板生成的 vecotr 类中的，它表示的真实类型和操作系统有关，在 32 位架构下普遍表示的是 unsigned int 类型，而在 64 位架构下普通表示 unsigned long 类型。

当然，我们还可以使用 auto 关键字代替 vector::size_type，比如：

1 2	auto cap = value.capacity(); auto size = value.size();

vector容器类结构

vector 是最常用的容器之一，其底层所采用的数据结构非常简单，就只是一段连续的线性内存空间（顺序存储）。

通过分析 vector 容器的源代码不难发现，它就是使用 3 个迭代器（可以理解成指针）来表示的：

//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

其中，_Myfirst 指向的是 vector 容器对象的起始字节位置；_Mylast 指向当前最后一个元素的末尾字节；_myend 指向整个 vector 容器所占用内存空间的末尾字节。

演示了以上这 3 个迭代器分别指向的位置。

通过这 3 个迭代器，就可以表示出一个已容纳 2 个元素，容量为 5 的 vector 容器。

在此基础上，将 3 个迭代器两两结合，还可以表达不同的含义，例如：

_Myfirst 和 _Mylast 可以用来表示 vector 容器中目前已被使用的内存空间；
_Mylast 和 _Myend 可以用来表示 vector 容器目前空闲的内存空间；
_Myfirst 和 _Myend 可以用表示 vector 容器的容量。

对于空的 vector 容器，由于没有任何元素的空间分配，因此 _Myfirst、_Mylast 和 _Myend 均为 null。

通过灵活运用这 3 个迭代器，vector 容器可以轻松的实现诸如首尾标识、大小、容器、空容器判断等几乎所有的功能，比如：

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
public：
    iterator begin() {return _Myfirst;}
    iterator end() {return _Mylast;}
    size_type size() const {return size_type(end() - begin());}
    size_type capacity() const {return size_type(_Myend - begin());}
    bool empty() const {return begin() == end();}
    reference operator[] (size_type n) {return *(begin() + n);}
    reference front() { return *begin();}
    reference back() {return *(end()-1);}
    ...
};

vector扩大容量的本质

当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

完全弃用现有的内存空间，重新申请更大的内存空间；
将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
最后将旧的内存空间释放。

这也就解释了，为什么 vector 容器在进行扩容后，与其相关的指针、引用以及迭代器可能会失效的原因。

由此可见，vector 扩容是非常耗时的。为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是 vector 容量的由来，即 capacity>=size），以便后期使用。

vector 容器扩容时，不同的编译器申请更多内存空间的量是不同的。以 VS 为例，它会扩容现有容器容量的 50%。

vector添加元素push_back()和emplace_back()

向 vector 容器中添加元素的唯一方式就是使用它的成员函数，如果不调用成员函数，非成员函数既不能添加也不能删除元素。这意味着，vector 容器对象必须通过它所允许的函数去访问，迭代器显然不行。

push_back():在 vector 容器尾部添加一个元素
emplace_back():该函数是 C++ 11 新增加的，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素。

读者可能会发现，以上 2 段代码，只是用 emplace_back() 替换了 push_back()，既然它们实现的功能是一样的，那么 C++ 11 标准中为什么要多此一举呢？

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

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

vector插入元素——insert()和emplace()

insert()

insert() 函数的功能是在 vector 容器的指定位置插入一个或多个元素。该函数的语法格式有多种,如下表：

语法格式	用法说明
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 <iostream> 
#include <vector> 
#include <array> 
using namespace std;
int main()
{
    std::vector<int> demo{1,2};
    //第一种格式用法
    demo.insert(demo.begin() + 1, 3);//{1,3,2}
    //第二种格式用法
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
    //第三种格式用法
    std::array<int,3>test{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
    //第四种格式用法
    demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
    return 0;
}

emplace()

emplace() 是 C++ 11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。

注意，emplace() 每次只能插入一个元素，而不是多个。

该函数的语法格式如下：

1	iterator emplace (const_iterator pos, args...);

其中，pos 为指定插入位置的迭代器；args… 表示与新插入元素的构造函数相对应的多个参数；该函数会返回表示新插入元素位置的迭代器。

#include <vector>
#include <iostream>
using namespace std;
int main()
{
    std::vector<int> demo1{1,2};
    //emplace() 每次只能插入一个 int 类型元素
    demo1.emplace(demo1.begin(), 3);
    for (int i = 0; i < demo1.size(); i++) {
        cout << demo1[i] << " ";
    }
    return 0;
}

运行结果为：

3 1 2

vector删除元素的几种方式

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），但不是改变其容量。

避免vector进行不必要的扩容？

vector 容器扩容的整个过程，和 realloc() 函数的实现方法类似，大致分为以下 4 个步骤：

分配一块大小是当前 vector 容量几倍的新存储空间。注意，多数 STL 版本中的 vector 容器，其容器都会以 2 的倍数增长，也就是说，每次 vector 容器扩容，它们的容量都会提高到之前的 2 倍；
将 vector 容器存储的所有元素，依照原有次序从旧的存储空间复制到新的存储空间中；
析构掉旧存储空间中存储的所有元素；
释放旧的存储空间。

vector 容器的扩容过程是非常耗时的，并且当容器进行扩容后，之前和该容器相关的所有指针、迭代器以及引用都会失效。因此在使用 vector 容器过程中，我们应尽量避免执行不必要的扩容操作。

要实现这个目标，可以借助 vector 模板类中提供的 reserve() 成员方法。强制 vector 容器的容量至少为 n。注意，如果 n 比当前 vector 容器的容量小，则该方法什么也不会做；反之如果 n 比当前 vector 容器的容量大，则 vector 容器就会扩容。

只要有新元素要添加到 vector 容器中而恰好此时 vector 容器的容量不足时，该容器就会自动扩容。

避免 vector 容器执行不必要的扩容操作的关键在于，在使用 vector 容器初期，就要将其容量设为足够大的值。换句话说，在 vector 容器刚刚构造出来的那一刻，就应该借助 reserve() 成员方法为其扩充足够大的容量。

举个例子，假设我们想创建一个包含 1~1000 的 vector，通常会这样实现：

vector<int>myvector;
for (int i = 1; i <= 1000; i++) {
    myvector.push_back(i);
}

值得一提的是，上面代码的整个循环过程中，vector 容器会进行 2~10 次自动扩容（多数的 STL 标准库版本中，vector 容器通常会扩容至当前容量的 2 倍，而这里 1000≈2 10），程序的执行效率可想而知。

在上面程序的基础上，下面代码演示了如何使用 reserve() 成员方法尽量避免 vector 容器执行不必要的扩容操作：

vector<int>myvector;
myvector.reserve(1000);
cout << myvector.capacity();
for (int i = 1; i <= 1000; i++) {
    myvector.push_back(i);
}

相比前面的代码实现，整段程序在运行过程中，vector 容器的容量仅扩充了 1 次，执行效率大大提高。

当然在实际场景中，我们可能并不知道 vector 容器到底要存储多少个元素。这种情况下，可以先预留出足够大的空间，当所有元素都存储到 vector 容器中之后，再去除多余的容量。

那么如何去除多余的容量呢？后续揭晓。

vector去除多余容量——shrink_to_fit()与swap()

shrink_to_fit()

1
2
3

vector<int> myvector;
...
myvector.shrink_to_fit();

swap()妙用去除多余容量

vector 模板类中提供有 swap() 成员方法，该方法的基础功能是交换 2 个相同类型的 vector 容器（交换容量和存储的所有元素），但其也能用于去除 vector 容器多余的容量。

如果想用 swap() 成员方法去除当前 vector 容器多余的容量时，可以套用如下的语法格式：

1	vector<T>(x).swap(x);

其中，x 指当前要操作的容器，T 为该容器存储元素的类型。

下面程序演示了此语法格式的 swap() 方法的用法和功能：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>myvector;
    //手动为 myvector 扩容
    myvector.reserve(1000);
    cout << "1、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
    //利用 myvector 容器存储 10 个元素
    for (int i = 1; i <= 10; i++) {
        myvector.push_back(i);
    }
    //将 myvector 容量缩减至 10
    vector<int>(myvector).swap(myvector);
    cout << "2、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
    return 0;
}

程序执行结果为：

1、当前 myvector 拥有 0 个元素，容量为 1000

2、当前 myvector 拥有 10 个元素，容量为 10

显然，第 16 行代码成功将 myvector 容器的容量 1000 修改为 10，此行代码的执行流程可细分为以下 3 步：

1.
先执行 vector(myvector)，此表达式会调用 vector 模板类中的拷贝构造函数，从而创建出一个临时的 vector 容器（后续称其为 tempvector）。

值得一提的是，tempvector 临时容器并不为空，因为我们将 myvector 作为参数传递给了复制构造函数，该函数会将 myvector 容器中的所有元素拷贝一份，并存储到 tempvector 临时容器中。

注意，vector 模板类中的拷贝构造函数只会为拷贝的元素分配存储空间。换句话说，tempvector 临时容器中没有空闲的存储空间，其容量等于存储元素的个数。

2.
然后借助 swap() 成员方法对 tempvector 临时容器和 myvector 容器进行调换，此过程不仅会交换 2 个容器存储的元素，还会交换它们的容量。换句话说经过 swap() 操作，myvetor 容器具有了 tempvector 临时容器存储的所有元素和容量，同时 tempvector 也具有了原 myvector 容器存储的所有元素和容量。

3.
当整条语句执行结束时，临时的 tempvector 容器会被销毁，其占据的存储空间都会被释放。注意，这里释放的其实是原 myvector 容器占用的存储空间。

经过以上 3 个步骤，就成功的将 myvector 容器的容量由 100 缩减至 10。

利用swap()方法清空vector容器

在以上内容的学习过程中，如果读者善于举一反三，应该不难想到，swap() 方法还可以用来清空 vector 容器。

当 swap() 成员方法用于清空 vector 容器时，可以套用如下的语法格式：

1	vector<T>().swap(x);

其中，x 指当前要操作的容器，T 为该容器存储元素的类型。

注意，和上面语法格式唯一的不同之处在于，这里没有为 vector() 表达式传递任何参数。这意味着，此表达式将调用 vector 模板类的默认构造函数，而不再是复制构造函数。也就是说，此格式会先生成一个空的 vector 容器，再借助 swap() 方法将空容器交换给 x，从而达到清空 x 的目的。

下面程序演示了此语法格式的 swap() 方法的用法和功能：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>myvector;
    //手动为 myvector 扩容
    myvector.reserve(1000);
    cout << "1、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
    //利用 myvector 容器存储 10 个元素
    for (int i = 1; i <= 10; i++) {
        myvector.push_back(i);
    }
    //清空 myvector 容器
    vector<int>().swap(myvector);
    cout << "2、当前 myvector 拥有 " << myvector.size() << " 个元素，容量为 " << myvector.capacity() << endl;
    return 0;
}

程序执行结果为：

1、当前 myvector 拥有 0 个元素，容量为 1000

2、当前 myvector 拥有 0 个元素，容量为 0

`vector<bool>`不是存储bool类型元素的vector容器！

前面章节中，已经详细介绍了vector<T>容器的功能和用法。特别需要提醒的是，在使用 vector 容器时，要尽量避免使用该容器存储 bool 类型的元素，即避免使用vector<bool>。

具体来讲，不推荐使用 vector 的原因有以下 2 个：

严格意义上讲，vector 并不是一个 STL 容器；
vector 底层存储的并不是 bool 类型值。

读者可能会感到有些困惑，别着急，继续往下读

`vector<bool>`不是容器

值得一提的是，对于是否为 STL 容器，C++ 标准库中有明确的判断条件，其中一个条件是：如果 cont 是包含对象 T 的 STL 容器，且该容器中重载了 [ ] 运算符（即支持 operator[]），则以下代码必须能够被编译：

1	T *p = &cont[0];

此行代码的含义是，借助 operator[ ] 获取一个 cont 容器中存储的 T 对象，同时将这个对象的地址赋予给一个 T 类型的指针。

这就意味着，如果 vector< bool> 是一个 STL 容器，则下面这段代码是可以通过编译的：

//创建一个 vector<bool> 容器
vector<bool>cont{0,1};
//试图将指针 p 指向 cont 容器中第一个元素
bool *p = &cont[0];

但不幸的是，此段代码不能通过编译。原因在于 vector< bool> 底层采用了独特的存储机制。

实际上，为了节省空间，vector< bool> 底层在存储各个 bool 类型值时，每个 bool 值都只使用一个比特位（二进制位）来存储。也就是说在 vector< bool> 底层，一个字节可以存储 8 个 bool 类型值。在这种存储机制的影响下，operator[ ] 势必就需要返回一个指向单个比特位的引用，但显然这样的引用是不存在的。

C++ 标准中解决这个问题的方案是，令 operator[] 返回一个代理对象（proxy object）。有关代理对象，由于不是本节重点，这里不再做描述，有兴趣的读者可自行查阅相关资料。

同样对于指针来说，其指向的最小单位是字节，无法另其指向单个比特位。综上所述可以得出一个结论，即上面第 2 行代码中，用 = 赋值号连接 bool *p 和 &cont[0] 是矛盾的。

由于 vector< bool> 并不完全满足 C++ 标准中对容器的要求，所以严格意义上来说它并不是一个 STL 容器。可能有读者会问，既然 vector< bool> 不完全是一个容器，为什么还会出现在 C++ 标准中呢？

这和一个雄心勃勃的试验有关，还要从前面提到的代理对象开始说起。由于代理对象在 C++ 软件开发中很受欢迎，引起了 C++ 标准委员会的注意，他们决定以开发 vector< bool> 作为一个样例，来演示 STL 中的容器如何通过代理对象来存取元素，这样当用户想自己实现一个基于代理对象的容器时，就会有一个现成的参考模板。

然而开发人员在实现 vector< bool> 的过程中发现，既要创建一个基于代理对象的容器，同时还要求该容器满足 C++ 标准中对容器的所有要求，是不可能的。由于种种原因，这个试验最终失败了，但是他们所做过的尝试（即开发失败的 vector< bool>）遗留在了 C++ 标准中。

至于将 vector< bool> 遗留到 C++ 标准中，是无心之作，还是有意为之，这都无关紧要，重要的是让读者明白，vector< bool> 不完全满足 C++ 标准中对容器的要求，尽量避免在实际场景中使用它！

如何避免使用`vector<bool>`

那么，如果在实际场景中需要使用 vector<bool> 这样的存储结构，该怎么办呢？很简单，可以选择使用 deque<bool> 或者 bitset 来替代 vector<bool>。

要知道，deque 容器几乎具有 vecotr 容器全部的功能（拥有的成员方法也仅差 reserve() 和 capacity()），而且更重要的是，deque 容器可以正常存储 bool 类型元素。

有关 deque 容器的具体用法，后续章节会做详细讲解。

还可以考虑用 bitset 代替 vector<bool>，其本质是一个模板类，可以看做是一种类似数组的存储结构。和后者一样，bitset 只能用来存储 bool 类型值，且底层存储机制也采用的是用一个比特位来存储一个 bool 值。

和 vector 容器不同的是，bitset 的大小在一开始就确定了，因此不支持插入和删除元素；另外 bitset 不是容器，所以不支持使用迭代器。

有关 bitset 的用法，感兴趣的读者可查阅 C++ 官方提供的 bitset使用手册。

deque容器

基本介绍

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

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

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

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

deque 容器以模板类 deque（T 为存储元素的类型）的形式在头文件中，并位于 std 命名空间中。因此，在使用该容器之前，代码中需要包含下面两行代码：

1 2	#include <deque> using namespace std;

注意，std 命名空间也可以在使用 deque 容器时额外注明，两种方式都可以。

deque初始化

创建 deque 容器，根据不同的实际场景，可选择使用如下几种方式。

创建一个没有任何元素的空 deque 容器：```c
std::deque d;


和空 array 容器不同，空的 deque 容器在创建之后可以做添加或删除元素的操作，因此这种简单创建 deque 容器的方式比较常见。
2. 创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：```c
std::deque<int> d(10);

此行代码创建一个具有 10 个元素（默认都为 0）的 deque 容器。
3. 创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：```c
std::deque d(10, 5)


如此就创建了一个包含 10 个元素（值都为 5）的 deque 容器。
4. 在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：```c
std::deque<int> d1(5);
std::deque<int> d2(d1);

注意，采用此方式，必须保证新旧容器存储的元素类型一致。
5. 通过拷贝其他类型容器中指定区域内的元素（也可以是普通数组），可以创建一个新容器，例如：```c
//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
std::dequed(a, a + 5);
//适用于所有类型的容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::dequed(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}




## deque的成员函数
| 函数成员 | 函数功能 |
| --- | --- |
| begin() | 返回指向容器中第一个元素的迭代器。 |
| end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和begin()结合使用。 |
| rbegin() | 返回指向最后一个元素的迭代器。 |
| rend() | 返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin() | 和 begin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。 |
| cend() | 和end()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。 |
| crbegin() | 和rbegin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。 |
| crend() | 和rend()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。 |
| size() | 返回实际元素个数。 |
| max_size() | 返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是2-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() 成员函数。


## deque容器迭代器

deque 容器迭代器的类型为随机访问迭代器。

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


> C++ 11 新添加的 begin() 和 end() 全局函数也同样适用于 deque 容器。即当操作对象为 deque 容器时，其功能分别和表 1 中的 begin()、end() 成员函数相同，具体用法本节后续会做详细介绍。


![](https://lautung-1256670757.cos.ap-guangzhou.myqcloud.com/image_1619847424547.png#alt=%E8%BF%AD%E4%BB%A3%E5%99%A8%E7%9A%84%E5%85%B7%E4%BD%93%E5%8A%9F%E8%83%BD%E7%A4%BA%E6%84%8F%E5%9B%BE)

## deque容器底层实现原理

### deque容器的存储结构

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。

为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间。

![](https://lautung-1256670757.cos.ap-guangzhou.myqcloud.com/image_1619847754808.png#alt=deque%E5%AE%B9%E5%99%A8%E7%9A%84%E5%BA%95%E5%B1%82%E5%AD%98%E5%82%A8%E6%9C%BA%E5%88%B6)

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

如果 map 数组满了，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。

deque 容器的分段存储结构，提高了在序列两端添加或删除元素的效率，但也使该容器迭代器的底层实现变得更复杂。

### deque容器迭代器的底层实现

由于 deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题：

1. 迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置；
2. 迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。

为了实现遍历 deque 容器的功能，deque 迭代器定义了如下的结构：

template<class T,...>

struct __deque_iterator{

...

T* cur;

T* first;

T* last;

map_pointer node;//map_pointer 等价于 T**

}

可以看到，迭代器内部包含 4 个指针，它们各自的作用为：

- cur：指向当前正在遍历的元素；
- first：指向当前连续空间的首地址；
- last：指向当前连续空间的末尾地址；
- node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。

借助这 4 个指针，deque 迭代器对随机访问迭代器支持的各种运算符进行了重载，能够对 deque 分段连续空间中存储的元素进行遍历。例如：

```c
//当迭代器处于当前连续空间边缘的位置时，如果继续遍历，就需要跳跃到其它的连续空间中，该函数可用来实现此功能
void set_node(map_pointer new_node){
    node = new_node;//记录新的连续空间在 map 数组中的位置
    first = *new_node; //更新 first 指针
    //更新 last 指针，difference_type(buffer_size())表示每段连续空间的长度
    last = first + difference_type(buffer_size());
}
//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator->() const{return &(operator *());}
//重载前置 ++ 运算符
self & operator++(){
    ++cur;
    //处理 cur 处于连续空间边缘的特殊情况
    if(cur == last){
        //调用该函数，将迭代器跳跃到下一个连续空间中
        set_node(node+1);
        //对 cur 重新赋值
        cur = first;
    }
    return *this;
}
//重置前置 -- 运算符
self& operator--(){
    //如果 cur 位于连续空间边缘，则先将迭代器跳跃到前一个连续空间中
    if(cur == first){
        set_node(node-1);
        cur == last;
    }
    --cur;
    return *this;
}

deque容器的底层实现

了解了 deque 容器底层存储序列的结构，以及 deque 容器迭代器的内部结构之后，接下来看看 deque 容器究竟是如何实现的。

deque 容器除了维护先前讲过的 map 数组，还需要维护 start、finish 这 2 个 deque 迭代器。以下为 deque 容器的定义：

//_Alloc为内存分配器
template<class _Ty,
    class _Alloc = allocator<_Ty>>
class deque{
    ...
protected:
    iterator start;
    iterator finish;
    map_pointer map;
...
}

其中，start 迭代器记录着 map 数组中首个连续空间的信息，finish 迭代器记录着 map 数组中最后一个连续空间的信息。另外需要注意的是，和普通 deque 迭代器不同，start 迭代器中的 cur 指针指向的是连续空间中首个元素；而 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置。

因此，deque 容器的底层实现如图 2 所示。

借助 start 和 finish，以及 deque 迭代器中重载的诸多运算符，就可以实现 deque 容器提供的大部分成员函数，比如：

//begin() 成员函数
iterator begin() {return start;}
//end() 成员函数
iterator end() { return finish;}
//front() 成员函数
reference front(){return *start;}
//back() 成员函数
reference back(){
    iterator tmp = finish;
    --tmp;
    return *tmp;
}
//size() 成员函数
size_type size() const{return finish - start;}//deque迭代器重载了 - 运算符
//enpty() 成员函数
bool empty() const{return finish == start;}

deque容器访问元素（4种方法）

容器名[n]
容器名.at(n)
deque 容器的2 个成员函数，即 front() 和 back()。
迭代器

deque容器添加和删除元素方法

deque 容器中，无论是添加元素还是删除元素，都只能借助 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()。

语法格式	功能
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指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。

list容器

基本介绍

STL list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。

list初始化

根据不同的使用场景，有以下 5 种创建 list 容器的方式供选择。

创建一个没有任何元素的空 list 容器：```c
std::list values;


和空 array 容器不同，空的 list 容器在创建之后仍可以添加元素，因此创建 list 容器的方式很常用。

2. 
创建一个包含 n 个元素的 list 容器：
```c
std::list<int> values(10);

通过此方式创建 values 容器，其中包含 10 个元素，每个元素的值都为相应类型的默认值（int类型的默认值为 0）。

3.
创建一个包含 n 个元素的 list 容器，并为每个元素指定初始值。例如：

1	std::list<int> values(10, 5);

如此就创建了一个包含 10 个元素并且值都为 5 个 values 容器。

4.
在已有 list 容器的情况下，通过拷贝该容器可以创建新的 list 容器。例如：

1 2	std::list<int> value1(10); std::list<int> value2(value1);

注意，采用此方式，必须保证新旧容器存储的元素类型一致。

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}

list容器可用的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的双向迭代器。
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin()	返回指向最后一个元素的反向双向迭代器。
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin()	和begin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
cend()	和end()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
crbegin()	和rbegin()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
crend()	和rend()功能相同，只不过在其基础上，增加了const属性，不能用于修改元素。
empty()	判断容器中是否有元素，若无元素，则返回true；反之，返回false。
size()	返回当前容器实际包含的元素个数。
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是2-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()	反转容器中元素的顺序。

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

list迭代器及用法

迭代器函数	功能
begin()	返回指向容器中第一个元素的双向迭代器（正向迭代器）。
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。（正向迭代器）。
rbegin()	返回指向最后一个元素的反向双向迭代器。
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin()	和begin()功能相同，只不过在其基础上，正向迭代器增加了const属性，即不能用于修改元素。
cend()	和end()功能相同，只不过在其基础上，正向迭代器增加了const属性，即不能用于修改元素。
crbegin()	和rbegin()功能相同，只不过在其基础上，反向迭代器增加了const属性，即不能用于修改元素。
crend()	和rend()功能相同，只不过在其基础上，反向迭代器增加了const属性，即不能用于修改元素。

前面章节已经详细介绍了 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 不支持使用 <、 >、 <=、 >= 比较运算符。

list容器底层实现原理

list容器底层存储结构

前面在讲 STL list 容器时提到，该容器的底层是用双向链表实现的，甚至一些 STL 版本中（比如 SGI STL），list 容器的底层实现使用的是双向循环链表。

使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针（图 1 以箭头表示）来维持。

list容器节点结构

template<typename T,...>
struct __List_node{
    //...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    //...
}

可以看到，list 容器定义的每个节点中，都包含 _prev、_next 和 myval。其中，prev 指针用于指向前一个节点；next 指针用于指向后一个节点；myval 用于存储当前元素的值。

list容器迭代器的底层实现

和 array、vector 这些容器迭代器的实现方式不同，由于 list 容器的元素并不是连续存储的，所以该容器迭代器中，必须包含一个可以指向 list 容器的指针，并且该指针还可以借助重载的 *、++、–、==、!= 等运算符，实现迭代器正确的递增、递减、取值等操作。

因此，list 容器迭代器的实现代码如下：

template<tyepname T,...>
struct __list_iterator{
    __list_node<T>* node;
    //...
    //重载 == 运算符
    bool operator==(const __list_iterator& x){return node == x.node;}
    //重载 != 运算符
    bool operator!=(const __list_iterator& x){return node != x.node;}
    //重载 * 运算符，返回引用类型
    T* operator *() const {return *(node).myval;}
    //重载前置 ++ 运算符
    __list_iterator<T>& operator ++(){
        node = (*node).next;
        return *this;
    }
    //重载后置 ++ 运算符
    __list_iterator<T>& operator ++(int){
        __list_iterator<T> tmp = *this;
        ++(*this);
        return tmp;
    }
    //重载前置 -- 运算符
    __list_iterator<T>& operator--(){
        node = (*node).prev;
        return *this;
    }
    //重载后置 -- 运算符
    __list_iterator<T> operator--(int){
        __list_iterator<T> tmp = *this;
        --(*this);
        return tmp;
    }
    //...
}

可以看到，迭代器的移动就是通过操作节点的指针实现的。

list容器的底层实现

本节开头提到，不同版本的 STL 标准库中，list 容器的底层实现并不完全一致，但原理基本相同。这里以 SGI STL 中的 list 容器为例，讲解该容器的具体实现过程。

SGI STL 标准库中，list 容器的底层实现为双向循环链表，相比双向链表结构的好处是在构建 list 容器时，只需借助一个指针即可轻松表示 list 容器的首尾元素。

如下是 SGI STL 标准库中对 list 容器的定义：

template <class T,...>
class list
{
    //...
    //指向链表的头节点，并不存放数据
    __list_node<T>* node;
    //...以下还有list 容器的构造函数以及很多操作函数
}

另外，为了更方便的实现 list 模板类提供的函数，该模板类在构建容器时，会刻意在容器链表中添加一个空白节点，并作为 list 链表的首个节点（又称头节点）。

使用双向链表实现的 list 容器，其内部通常包含 2 个指针，并分别指向链表中头部的空白节点和尾部的空白节点（也就是说，其包含 2 个空白节点）。

比如，我们经常构造空的 list 容器，其用到的构造函数如下所示：

list() { empty_initialize(); }
// 用于空链表的建立
void empty_initialize()
{
    node = get_node();//初始化节点
    node->next = node; // 前置节点指向自己
    node->prev = node; // 后置节点指向自己
}

显然，即便是创建空的 list 容器，它也包含有 1 个节点。

除此之外，list 模板类中还提供有带参的构造函数，它们的实现过程大致分为以下 2 步：

调用 empty_initialize() 函数，构造带有头节点的空 list 容器链表；
将各个参数按照次序插入到空的 list 容器链表中。

由此可以总结出，list 容器实际上就是一个带有头节点的双向循环链表。如图 2 所示，此为存有 2 个元素的 list 容器：

在此基础上，通过借助 node 头节点，就可以实现 list 容器中的所有成员函数，比如：

//begin()成员函数
__list_iterator<T> begin(){return (*node).next;}
//end()成员函数
__list_iterator<T> end(){return node;}
//empty()成员函数
bool empty() const{return (*node).next == node;}
//front()成员函数
T& front() {return *begin();}
//back()成员函数
T& back() {return *(--end();)}
//...

感兴趣的读者，可下载 list 容器的实现源码。

list容器访问元素

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

list添加（插入）元素

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

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

empty()和size()都可以判断容器是否为空，谁更好？

到目前为止，我们已经了解了 C++ STL 标准库中 vector、deque 和 list 这 3 个容器的功能和具体用法。学习过程中，读者是否想过一个问题，即这些容器的模板类中都提供了 empty() 成员方法和 size() 成员方法，它们都可以用来判断容器是否为空。

换句话说，假设有一个容器 cont，则此代码：

1	if(cont.size() == 0)

本质上和如下代码是等价的：

1	if(cont.empty())

那么，在实际场景中，到底应该使用哪一种呢？

建议使用 empty() 成员方法。理由很简单，无论是哪种容器，只要其模板类中提供了 empty() 成员方法，使用此方法都可以保证在 O(1) 时间复杂度内完成对“容器是否为空”的判断；但对于 list 容器来说，使用 size() 成员方法判断“容器是否为空”，可能要消耗 O(n) 的时间复杂度。

注意，这个结论不仅适用于 vector、deque 和 list 容器，后续还会讲解更多容器的用法，该结论也依然适用。

那么，为什么 list 容器这么特殊呢？这和 list 模板类提供了独有的 splice() 成员方法有关。

深度剖析选用empty()的原因：

做一个大胆的设想，假设我们自己就是 list 容器的设计者。从始至终，我们的目标都是让 list 成为标准容器，并被广泛使用，因此打造“高效率的 list”成为我们奋斗的目标。

在实现 list 容器的过程中我们发现，用户经常需要知道当前 list 容器中存有多少个元素，于是我们想让 size() 成员方法的执行效率达到 O(1)。为了实现这个目的，我们必须重新设计 list，使它总能以最快的效率知道自己含有多少个元素。

要想令 size() 的执行效率达到 O(1)，最直接的实现方式是：在 list 模板类中设置一个专门用于统计存储元素数量的 size 变量，其位于所有成员方法的外部。与此同时，在每一个可用来为容器添加或删除元素的成员方法中，添加对 size 变量值的更新操作。由此，size() 成员方法只需返回 size 这个变量即可（时间复杂度为 O(1)）。

不仅如此，由于 list 容器底层采用的是链式存储结构（也就是链表），该结构最大的特点就是，某一链表中存有元素的节点，无需经过拷贝就可以直接链接到其它链表中，且整个过程只需要消耗 O(1) 的时间复杂度。考虑到很多用户之所以选用 list 容器，就是看中了其底层存储结构的这一特性。因此，作为 list 容器设计者的我们，自然也想将 splice() 方法的时间复杂度设计为 O(1)。

这里就产生了一个矛盾，即如果将 size() 设计为 O(1) 时间复杂度，则由于 splice() 成员方法会修改 list 容器存储元素的个数，因此该方法中就需要添加更新 size 变量的代码（更新方式无疑是通过遍历链表来实现），这也就意味着 splice() 成员方法的执行效率将无法达到 O(1)；反之，如果将 splice() 成员方法的执行效率提高到 O(1)，则 size() 成员方法将无法实现 O(1) 的时间复杂度。

也就是说，list 容器中的 size() 和 splice() 总有一个要做出让步，即只能实现其中一个方法的执行效率达到 O(1)。

值得一提的是，不同版本的 STL 标准库，其底层解决此冲突的抉择是不同的。以本教程所用的 C++ STL 标准模板库为例，其选择将 splice() 成员方法的执行效率达到 O(1)，而 size() 成员方法的执行效率为 O(n)。当然，有些版本的 STL 标准库中，选择将 size() 方法的执行效率设计为 O(1)。

但不论怎样，选用 empty() 判断容器是否为空，效率总是最高的。所以，如果程序中需要判断当前容器是否为空，应优先考虑使用 empty()。

list删除元素

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

forward_list容器完全攻略

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

H 表示链表的表头。

其它相关资料自行查阅cplusplus

什么是容器？

C++ STL迭代器（iterator）

迭代器类别

迭代器的定义方式

迭代器示例

STL序列式容器

序列式容器分类

容器中常见的函数成员

array(STL array)序列容器

基本介绍

基本使用

array随机访问迭代器

array容器访问元素

vector序列容器

基本介绍

vector初始化

vector的成员函数

vector容器迭代器的使用

vector容器访问元素

vector容量（capacity）和大小（size

capacity和size的区别

修改vector容器的容量和大小

vector容器容量和大小的数据类型

vector容器类结构

vector扩大容量的本质

vector添加元素push_back()和emplace_back()

vector插入元素——insert()和emplace()

insert()

emplace()

vector删除元素的几种方式

避免vector进行不必要的扩容？

vector去除多余容量——shrink_to_fit()与swap()

shrink_to_fit()

swap()妙用去除多余容量

利用swap()方法清空vector容器

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

vector<bool>不是容器

如何避免使用vector<bool>

deque容器

基本介绍

deque初始化

deque容器的底层实现

deque容器访问元素（4种方法）

deque容器添加和删除元素方法

list容器

基本介绍

list初始化

list容器可用的成员函数

list迭代器及用法

list容器底层实现原理

list容器底层存储结构

list容器节点结构

list容器迭代器的底层实现

list容器的底层实现

list容器访问元素

list添加（插入）元素

empty()和size()都可以判断容器是否为空，谁更好？

list删除元素

forward_list容器完全攻略

`vector<bool>`不是存储bool类型元素的vector容器！

`vector<bool>`不是容器

如何避免使用`vector<bool>`