序列式容器：vector、deque、list、forward_list、array、string——底层原理与使用场景
序列式容器，说白了就是管理一组线性排列的数据。C++标准库给我们提供了六种：vector、deque、list、forward_list、array、string。每种容器的底层实现都不一样，性能特点也天差地别。我刚开始学的时候也经常搞混，后来在项目里踩过几次坑，才真正理解它们各自的脾气。
今天我们就来把这六个容器彻底讲透。我会从底层原理入手，再结合使用场景，帮你建立一套「什么时候该用谁」的判断标准。
1. vector——动态数组，最常用的容器
vector 的底层就是一块连续的内存空间。它维护三个指针：start、finish、end_of_storage。start 指向分配的内存起始位置，finish 指向已构造元素的末尾，end_of_storage 指向分配的内存末尾。
当元素数量超过容量时，vector 会重新分配一块更大的内存（通常是当前容量的 1.5 倍或 2 倍），然后把所有元素搬过去。这个过程叫「扩容」。扩容时所有迭代器、指针、引用都会失效——嗯，这里要注意。
- 随机访问 O(1)——底层连续内存，直接通过偏移量计算地址
- 尾部插入/删除 O(1) 均摊——大多数情况下直接写，偶尔触发扩容
- 中间插入/删除 O(n)——需要移动后续所有元素
// vector 典型用法
std::vector<int> vec;
vec.reserve(100); // 提前预留空间，避免多次扩容
for (int i = 0; i < 100; ++i) {
vec.push_back(i);
}
// 随机访问
int val = vec[50]; // O(1)
2. deque——双端队列，两端操作都很快
deque 的底层实现比 vector 复杂。它由一段段连续的内存块（buffer）组成，这些 buffer 由一个中央控制器（map）管理。map 本身也是一个连续数组，每个元素指向一个 buffer。
这种结构的好处是：在头部和尾部插入元素时，只需要在 map 中新增一个 buffer 或者调整指针，不需要移动已有元素。所以 deque 的 push_front 和 push_back 都是 O(1)。
但随机访问比 vector 慢一点，因为需要先通过 map 找到对应的 buffer，再在 buffer 内偏移。不过仍然是 O(1)。
- 头部和尾部插入/删除 O(1)
- 随机访问 O(1) 但常数比 vector 大
- 中间插入/删除 O(n)
- 扩容时不会使所有迭代器失效（只有指向被删除元素的迭代器失效）
// deque 典型用法——实现一个双端队列
std::deque<int> dq;
dq.push_back(1);
dq.push_front(2);
dq.push_back(3);
// 现在 dq 的内容是：2, 1, 3
int front = dq.front(); // 2
int back = dq.back(); // 3
3. list——双向链表，插入删除是强项
list 的底层是双向链表。每个节点包含三个部分：数据、指向前一个节点的指针、指向后一个节点的指针。链表的节点在内存中是不连续的，分散在各处。
这种结构决定了 list 的优缺点非常鲜明：
- 任意位置插入/删除 O(1)——只需要修改相邻节点的指针
- 不支持随机访问——要找到第 n 个元素，必须从头遍历
- 每个节点有额外开销——两个指针，大约 16 字节（64 位系统）
// list 典型用法——频繁在中间插入
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // 移动到第 3 个位置
lst.insert(it, 99); // 在位置 3 插入 99
// 现在 lst 的内容：1, 2, 99, 3, 4, 5
4. forward_list——单向链表，更轻量
forward_list 是 C++11 引入的，底层是单向链表。每个节点只包含数据和指向下一个节点的指针，没有前驱指针。所以它比 list 更省内存，但功能也更受限。
它只支持前向遍历，不支持反向遍历。插入和删除也只能在已知位置之后进行（因为找不到前驱节点）。
- 比 list 更省内存（每个节点少一个指针）
- 只支持前向迭代
- 插入/删除 O(1) 但只能在已知位置之后操作
- 适合内存敏感且只需要前向遍历的场景
// forward_list 典型用法
std::forward_list<int> flst = {1, 2, 3, 4};
auto prev = flst.before_begin(); // 指向第一个元素之前的哨兵
auto curr = flst.begin();
flst.insert_after(prev, 99); // 在开头插入 99
// 现在 flst 的内容：99, 1, 2, 3, 4
5. array——固定大小数组，零开销
array 是 C++11 引入的，底层就是普通的 C 风格数组。它的大小在编译期就确定了，不能动态改变。没有动态内存分配，没有扩容，没有额外的内存开销。
array 的优势在于：它提供了 STL 容器的接口（begin、end、size、at 等），同时保持了 C 数组的性能。你可以把它当作「带 STL 接口的 C 数组」。
// array 典型用法
std::array<int, 5> arr = {1, 2, 3, 4, 5};
// 安全的边界检查访问
int val = arr.at(3); // 如果越界会抛出异常
// 不检查的访问（更快）
int val2 = arr[3];
// 获取大小
size_t sz = arr.size(); // 编译期常量
6. string——字符序列容器
string 的底层实现因标准库而异，但大多数实现都采用了「小字符串优化」（SSO）。简单来说：对于短字符串（通常是 15 个字符以内），直接存储在对象内部，不分配堆内存。对于长字符串，才动态分配内存。
string 本质上是一个管理字符序列的容器，它提供了丰富的字符串操作接口：拼接、查找、替换、比较等。
- 底层连续内存，支持随机访问 O(1)
- 小字符串优化，避免短字符串的堆分配开销
- 提供了大量字符串专用操作
- COW（写时复制）在 C++11 后被禁止，现在都是深拷贝或移动语义
// string 典型用法
std::string s = "Hello";
s += " World"; // 拼接
size_t pos = s.find("World"); // 查找
std::string sub = s.substr(0, 5); // 子串
// 小字符串优化：短字符串不分配堆内存
std::string short_str = "Hi"; // 存储在栈上
std::string long_str = "This is a very long string that exceeds SSO buffer"; // 堆分配
7. 容器选择决策树
说了这么多，到底该怎么选？我总结了一个简单的决策流程：
- 需要随机访问？ → vector、deque、array、string
- 需要在头部频繁操作？ → deque
- 需要在中间频繁插入/删除？ → list、forward_list
- 大小在编译期已知？ → array
- 操作的是字符？ → string
- 内存敏感且只前向遍历？ → forward_list
8. 性能对比一览
| 操作 | vector | deque | list | forward_list | array | string |
|---|---|---|---|---|---|---|
| 随机访问 | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| 尾部插入 | O(1) 均摊 | O(1) | O(1) | O(1) | 不支持 | O(1) 均摊 |
| 头部插入 | O(n) | O(1) | O(1) | O(1) | 不支持 | O(n) |
| 中间插入 | O(n) | O(n) | O(1) | O(1) | 不支持 | O(n) |
| 内存开销 | 低 | 中 | 高 | 中 | 无 | 低 |
| 缓存友好 | 高 | 中 | 低 | 低 | 高 | 高 |
9. 底层结构对比图
下面这张图展示了六种容器的底层内存布局，帮你直观理解它们的差异：
10. 总结
六种序列式容器，各有各的脾气。vector 是万金油，deque 适合双端操作，list 适合频繁插入删除，forward_list 是轻量版 list，array 是零开销的固定数组，string 是字符序列的专用容器。
选容器的时候，先想清楚你的核心操作是什么。是随机访问多？还是插入删除多？还是遍历多？想清楚了，选择就简单了。
嗯，最后说一句：不要过度设计。先用 vector，性能不够再换。我见过太多人一开始就上 list，结果代码写起来麻烦，性能也没好到哪去。