list / deque
更新时间：2026-08-27。本文是
languages/cpp/主题入门层第 35 篇。vector 之外的顺序容器：list双向链表（中间插入 O(1)）、deque双端队列（头尾都 O(1)）。选它们要小心"理论复杂度 ≠ 实际性能"——list 的每个节点分散在内存里，遍历可能比 vector 慢一个数量级。
本文要回答的问题
list和deque各自擅长什么？- 为什么 list 插入是 O(1) 却常常比 vector 慢？
- 顺序容器到底怎么选？
一、list：双向链表
#include <list>
std::list<int> l = {1, 2, 3};
l.push_back(4); // 尾插 O(1)
l.push_front(0); // 头插 O(1)——这是 list 比 vector 强的地方
l.insert(++l.begin(), 99); // 中间插入 O(1)，不用搬元素
for (int x : l) { /* 遍历 */ }list 是双向链表：每个元素是一个节点，节点里存着前驱/后继指针。在已知位置插入/删除是 O(1)——改两个指针就完事，不像 vector 要搬动后面所有元素。代价是：
- 不能随机访问：
l[3]不存在，要从头走 3 步（O(n)）； - 每个节点额外两个指针：8 或 16 字节开销；
- 内存不连续：每个节点单独
new，散落在堆的各处。
二、为什么 list 常常"理论快、实际慢"
这是 STL 选型最重要的认知，没有之一：
// 各插入 100 万个元素，然后遍历
std::list<int> l;
for (int i = 0; i < 1000000; ++i) l.push_back(i);
std::vector<int> v;
v.reserve(1000000);
for (int i = 0; i < 1000000; ++i) v.push_back(i);- list 的每个
push_back都new一个节点——100 万次堆分配； - vector 一次
reserve后零分配； - 遍历时：vector 顺序读连续内存，每读一次都命中缓存行；list 要跟着指针跳，每跳一次可能就是一次 cache miss——每次 miss 大约慢几十到几百纳秒。
结果：list 遍历可能比 vector 慢 3~10 倍，尽管 list 的插入"理论"是 O(1)。这就是本站性能主线反复强调的：缓存局部性 > 理论复杂度（见 L3 缓存与局部性）。
经验法则：默认 vector，真的需要"频繁在中间插入删除 + 不在乎遍历慢"才用 list。很多场景其实用 deque 或 vector + 排序更划算。
三、deque：双端队列
#include <deque>
std::deque<int> d;
d.push_back(1); // 尾插 O(1)
d.push_front(0); // 头插 O(1)——vector 做不到
d[2]; // 还能随机访问 O(1)！
for (int x : d) { /* ... */ }deque（double-ended queue）的特点：
- 头尾插入都是 O(1)（vector 头插是 O(n)）；
- 支持随机访问
d[i]O(1)； - 底层是"若干块连续内存"拼起来的，不是整块连续——所以比 list 缓存友好得多，又比 vector 多了头插能力。
| vector | deque | list | |
|---|---|---|---|
| 尾插 | O(1) | O(1) | O(1) |
| 头插 | O(n) | O(1) | O(1) |
| 随机访问 | O(1) | O(1) | O(n) |
| 中间插入 | O(n) | O(n) | O(1) |
| 内存连续 | 整块 | 分块 | 每节点独立 |
| 缓存友好 | 最好 | 好 | 差 |
四、怎么选
| 需求 | 选谁 |
|---|---|
| 默认、未知 | vector |
| 头尾都要插、偶尔随机访问 | deque |
| 频繁中间插入删除、不遍历 | list |
| 只要栈/队列语义 | stack / queue（40 篇） |
| 大小固定 | std::array（34 篇） |
一句话总结选型：vector 是万金油，deque 是"两头都要能插"的 vector，list 只在"中间插入删除是刚需"时用——且用之前想清楚遍历代价。
五、和 C 对比
| 对比项 | C | C++ |
|---|---|---|
| 链表 | 手写节点 + 指针 + 边界管理 | std::list 现成 |
| 双端队列 | 手写循环数组 | std::deque |
| 内存管理 | 手动 new/free 每个节点 | 容器自动 |
| 迭代器失效 | 无概念 | 插入/删除有讲究（38 篇） |
C 里写链表是经典练习（节点结构体、插入删除函数、防内存泄漏），C++ 用 std::list 一行声明——但**"为什么默认不用 list"这个认知，是 C 程序员转型最该补的一课**。
六、与本站主线衔接
- 缓存局部性如何决定容器实际性能，见 L3 缓存与局部性；
- 迭代器失效规则（list 插入不失效、vector 扩容全失效），见 迭代器与范围 for；
- 下一篇：set / map——有序关联容器。
一句话总结
list 双向链表：已知位置插入/删除 O(1)，但内存分散、遍历可能比 vector 慢 3~10 倍；deque 双端队列：头尾插入都 O(1)、还能随机访问，是"两头都要能插"的 vector；选型记住 vector 打底、deque 补头尾、list 只在中间插入是刚需时上——理论复杂度永远比不过缓存局部性。
上一篇：std::array 与 C 数组 下一篇：set / map