导入
简介
我们将要学习的第一类容器是顺序容器。以下是各种类型顺序容器的主要特性。
顺序容器 具有许多共同点，但每种容器都有其特定的应用场景。在深入细节之前，我先对 std 命名空间中的五种顺序容器做一个概览。
以下是这五种顺序容器：
| 指标 | 数组（Array） | 向量（Vector） | 双端队列（Deque） | 列表（List） | 前向列表（Forward List） |
|---|---|---|---|---|---|
| 大小 | 静态 | 动态 | 动态 | 动态 | 动态 |
| 实现方式 | 静态数组 | 动态数组 | 多个数组组成的序列 | 双向链表 | 单向链表 |
| 访问方式 | 随机访问 | 随机访问 | 随机访问 | 双向遍历 | 单向遍历 |
| 插入与删除优化位置 | --- | 尾部：O(1) | 首尾：O(1) | 首尾：O(1)；任意位置：O(1) | 首部：O(1)；任意位置：O(1) |
| 内存预留支持 | --- | 是 | 否 | 否 | 否 |
| 内存释放机制 | --- | shrink_to_fit | shrink_to_fit | 自动释放 | 自动释放 |
| 优势 | 无需动态分配内存；内存开销最小 | 适用于95%的场景 | 在首尾插入和删除高效 | 在任意位置插入删除高效 | 插入删除速度快；内存开销最小 |
| 劣势 | 不支持动态扩容；固定大小 | 在任意位置插入删除：O(n) | 在任意位置插入删除：O(n) | 不支持随机访问 | 不支持随机访问 |
顺序容器对比表
对上表的一些补充说明：
O(i) 表示操作的时间复杂度（运行时间）。O(1) 表示该操作在容器上的执行时间是常数级别的，与容器大小无关；而 O(n) 表示运行时间与容器中元素数量成正比。以 std::vector 为例，访问某个元素的时间不随容器大小变化，但如果容器元素数量增加 k 倍，那么在任意位置插入或删除元素的操作将大约变慢 k 倍。
尽管 std::vector 和 std::deque 对元素的随机访问都具有相同的时间复杂度 O(1)，但这并不意味着两者的访问速度完全相同。
对于双向链表（std::list）或单向链表（std::forward_list），只有当迭代器已指向目标元素时，插入或删除操作的 O(1) 时间复杂度才能得到保证。
ℹ️ std::string 类似于 std::vector
当然，std::string并不是标准模板库中的普通容器。但从行为特性来看，它非常类似于一个顺序容器，尤其是像std::vector<char>。因此，本文中将std::string视为std::vector<char>来对待。