序列式容器

std::vector 是 STL 提供的 内存连续的、可变长度 的数组（亦称列表）数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。

作为 OIer，对程序效率的追求远比对工程级别的稳定性要高得多，而 vector 由于其对内存的动态处理，时间效率在部分情况下低于静态数组，并且在 OJ 服务器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候，通常不选择 vector。下面给出几个 vector 优秀的特性，在需要用到这些特性的情况下，vector 能给我们带来很大的帮助。

很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要 vector 来把内存占用量控制在合适的范围内。vector 还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。

vector 重载了六个比较运算符，以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系）。例如可以利用 vector<char> 实现字符串比较（当然，还是用 std::string 会更快更方便）。另外 vector 也重载了赋值运算符，使得数组拷贝更加方便。

由于 vector 重载了 = 运算符，所以我们可以方便的初始化。此外从 C++11 起 vector 还支持 列表初始化，例如 vector<int> data {1, 2, 3};。

以下介绍常用用法，详细内容 请参见 C++ 文档。

用例参见如下代码（假设你已经 using 了 std 命名空间相关类型）：

可以利用上述的方法构造一个 vector，足够我们使用了。

vector 提供了如下几种方法进行元素访问

at()

v.at(pos) 返回容器中下标为 pos 的引用。如果数组越界抛出 std::out_of_range 类型的异常。

operator[]

v[pos] 返回容器中下标为 pos 的引用。不执行越界检查。

front()

v.front() 返回首元素的引用。

back()

v.back() 返回末尾元素的引用。

data()

v.data() 返回指向数组第一个元素的指针。

vector 提供了如下几种 迭代器

begin()/cbegin()

返回指向首元素的迭代器，其中 *begin = front。

end()/cend()

返回指向数组尾端占位符的迭代器，注意是没有元素的。

rbegin()/crbegin()

返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。

rend()/crend()

返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

以上列出的迭代器中，含有字符 c 的为只读迭代器，你不能通过只读迭代器去修改 vector 中的元素的值。如果一个 vector 本身就是只读的，那么它的一般迭代器和只读迭代器完全等价。只读迭代器自 C++11 开始支持。

vector 有以下几个与容器长度和容量相关的函数。注意，vector 的长度（size）指有效元素数量，而容量（capacity）指其实际分配的内存长度，相关细节请参见后文的实现细节介绍。

与长度相关：

empty() 返回一个 bool 值，即 v.begin() == v.end()，true 为空，false 为非空。

size() 返回容器长度（元素数量），即 std::distance(v.begin(), v.end())。

resize() 改变 vector 的长度，多退少补。补充元素可以由参数指定。

max_size() 返回容器的最大可能长度。

与容量相关：

reserve() 使得 vector 预留一定的内存空间，避免不必要的内存拷贝。

capacity() 返回容器的容量，即不发生拷贝的情况下容器的长度上限。

shrink_to_fit() 使得 vector 的容量与长度一致，多退但不会少。

vector 的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 vector 中元素的数量（长度） 与它已分配内存最多能包含元素的数量（容量） 是不一致的，vector 会分开存储这两个量。当向 vector 中添加元素时，如发现 ，那么容器会分配一个尺寸为 的数组，然后将旧数据从原本的位置拷贝到新的数组中，再将原来的内存释放。尽管这个操作的渐进复杂度是 ，但是可以证明其均摊复杂度为 。而在末尾删除元素和访问元素则都仍然是 的开销。 因此，只要对 vector 的尺寸估计得当并善用 resize() 和 reserve()，就能使得 vector 的效率与定长数组不会有太大差距。

标准库特别提供了对 bool 的 vector 特化，每个「bool」只占 1 bit，且支持动态增长。但是其 operator[] 的返回值的类型不是 bool& 而是 vector<bool>::reference。因此，使用 vector<bool> 使需谨慎，可以考虑使用 deque<bool> 或 vector<char> 替代。而如果你需要节省空间，请直接使用 bitset。

std::array 是 STL 提供的 内存连续的、固定长度 的数组数据结构。其本质是对原生数组的直接封装。

array 实际上是 STL 对数组的封装。它相比 vector 牺牲了动态扩容的特性，但是换来了与原生数组几乎一致的性能（在开满优化的前提下）。因此如果能使用 C++11 特性的情况下，能够使用原生数组的地方几乎都可以直接把定长数组都换成 array，而动态分配的数组可以替换为 vector。

at 若遇 pos >= size() 的情况会抛出 std::out_of_range。

由于每个 array 都是固定大小容器，size() 返回的值等于 max_size() 返回的值。

注意，交换两个 array 是 的，而非与常规 STL 容器一样为 。

下面是一个 array 的使用示例：

std::deque 是 STL 提供的 双端队列 数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。

以下介绍常用用法，详细内容 请参见 C++ 文档。deque 的迭代器函数与 vector 相同，因此不作详细介绍。

参见如下代码（假设你已经 using 了 std 命名空间相关类型）：

与 vector 一致，但无法访问底层内存。其高效的元素访问速度可参考实现细节部分。

与 vector 一致。

与 vector 一致，但是没有 reserve() 和 capacity() 函数。（仍然有 shrink_to_fit() 函数）

与 vector 一致，并额外有向队列头部增加元素的函数。

deque 通常的底层实现是多个不连续的缓冲区，而缓冲区中的内存是连续的。而每个缓冲区还会记录首指针和尾指针，用来标记有效数据的区间。当一个缓冲区填满之后便会在之前或者之后分配新的缓冲区来存储更多的数据。更详细的说明可以参考 STL 源码剖析——deque 的实现原理和使用方法详解。

std::list 是 STL 提供的 双向链表 数据结构。能够提供线性复杂度的随机访问，以及常数复杂度的插入和删除。

list 的使用方法与 deque 基本相同，但是增删操作和访问的复杂度不同。详细内容 请参见 C++ 文档。list 的迭代器、长度、元素增删及修改相关的函数与 deque 相同，因此不作详细介绍。

由于 list 的实现是链表，因此它不提供随机访问的接口。若需要访问中间元素，则需要使用迭代器。

list 类型还提供了一些针对其特性实现的 STL 算法函数。由于这些算法需要 随机访问迭代器，因此 list 提供了特别的实现以便于使用。这些算法有 splice()、remove()、sort()、unique()、merge() 等。

std::forward_list 是 STL 提供的 单向链表 数据结构，相比于 std::list 减小了空间开销。

forward_list 的使用方法与 list 几乎一致，但是迭代器只有单向的，因此其具体用法不作详细介绍。详细内容 请参见 C++ 文档