【STL二】STL序列式容器（array、vector、deque、list、forward_list）

所谓序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。

1.array<T,N>（数组容器）

• 表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；

• 因为，空间大小指定后不能改变，元素存储在连续的线性内存空间，所以，不具备动态扩容的能力，因此，实际应用中几乎没有。

• 其迭代器类型为 Random Access Iterator 随机访问迭代器。

2.vector（向量容器）

• 用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。

• 使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；

• 元素存储在连续的线性内存空间，其空间可以动态缩小或扩大，实际应用中非常普遍。

• 引起 vector 内存空间重新配置的操作（如插入、删除操作），会导致之前定义的迭代器失效。

• 其迭代器类型为 Random Access Iterator 随机访问迭代器，支持算术运算。

3.deque（双端队列容器）：

• 和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；

• deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。

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

若需要对 deque 排序，最好借助 vector 完成。

其迭代器类型为 Random Access Iterator 随机访问迭代器，支持算术运算。

4.list（链表容器）

• 是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，

• 在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。

• 双向循环链表，元素存储在非线性内存空间，实际应用中非常普遍。

list 不会重新配置空间，因此只有被删除元素的迭代器会失效，其他原先的迭代器不会失效。

• 其迭代器类型为 Bidirectional Iterator 双向迭代器，只支持自增（++）和自减（–）运算。

5.forward_list（正向链表容器）

• 和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

6.各个容器区别

下图说明了可供使用的序列容器以及它们之间的区别。

每一种容器的详细用法，后面我们都会分一篇篇详细介绍。

参考
1、STL序列式容器使用注意、概念总结:https://www.cnblogs.com/zwjason/p/17038449.html
2、C++ STL 容器库 中文文档
3、STL教程：C++ STL快速入门
4、https://www.apiref.com/cpp-zh/cpp/header.html
5、https://en.cppreference.com/w/cpp/container