C / C++ / 系统课时
vector、deque、list 怎么选
vector、deque、list 怎么选
面对“顺序存一批元素”这个需求,vector、deque 和 list 都能完成,但它们擅长的访问与修改模式完全不同。选择容器时,重点不是记住谁“更快”,而是判断是否需要随机访问、双端操作、中间插入,以及良好的内存局部性。
学习目标
- 能从随机访问、首尾操作和中间插入三个维度比较
vector、deque与list - 理解连续存储、分段存储和链式节点对内存局部性的影响
- 能根据实际操作模式选择合适的顺序容器,而不是只看单个复杂度
先看三种容器的核心差异
vector 的元素连续存储,支持常数时间随机访问,遍历时通常也最有利于 CPU 缓存。尾部追加通常是摊还常数时间,但在头部或中间插入元素时,需要移动后续元素。
deque 支持常数时间随机访问,同时擅长在首尾两端插入和删除。它通常采用分段存储,不保证所有元素位于一整块连续内存,因此局部性一般不如 vector,但适合频繁的双端操作。
list 是双向链表,不支持下标随机访问。已知插入位置的迭代器时,插入和删除本身是常数时间;但如果先要从头查找第 N 个位置,查找过程仍然是线性时间。每个节点通常独立分配,也会带来额外指针和较弱的缓存局部性。

用表格快速做第一轮筛选
| 需求 | vector |
deque |
list |
|---|---|---|---|
随机访问 c[i] |
支持,O(1) | 支持,O(1) | 不支持 |
| 尾部插入/删除 | 通常很合适,摊还 O(1) | 很合适,O(1) | O(1) |
| 头部插入/删除 | O(n) | 很合适,O(1) | O(1) |
| 已知位置后中间插入/删除 | O(n) | O(n) | O(1) |
| 内存局部性 | 最好 | 较好但非整体连续 | 较弱 |
| 单个元素额外开销 | 低 | 有分段管理开销 | 通常较高,节点含链接信息 |
用同一组操作感受差别
下面的完整程序分别完成“尾部追加、头部插入、访问第三个元素”三个动作。vector 和 deque 可以直接随机访问,而 list 必须通过迭代器向前移动。
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
int main() {
std::vector<int> v{20, 30};
std::deque<int> d{20, 30};
std::list<int> l{20, 30};
v.push_back(40);
d.push_back(40);
l.push_back(40);
// vector 没有 push_front,只能在 begin() 位置插入并移动后续元素。
v.insert(v.begin(), 10);
d.push_front(10);
l.push_front(10);
std::cout << "vector third = " << v[2] << '\n';
std::cout << "deque third = " << d[2] << '\n';
auto it = l.begin();
std::advance(it, 2); // list 只能沿链表移动到第三个元素。
std::cout << "list third = " << *it << '\n';
}预期输出
vector third = 30
deque third = 30
list third = 30这段程序说明的是接口和访问方式,不代表三种操作的真实耗时相同。容器性能还要结合数据规模、元素类型、内存分配和实际访问模式评估。
一个实用的选择顺序
优先考虑 vector:大多数顺序数据都适合它,尤其是需要频繁遍历、下标访问、排序,或要把数据交给要求连续内存的接口时。
当业务明确需要频繁从头尾两端压入和弹出,同时仍希望随机访问时,再考虑 deque。典型场景包括双端队列、滑动窗口和某些任务调度结构。
只有在“经常拿着已有迭代器在中间插入或删除”,并且不依赖随机访问与连续内存时,list 才更可能体现优势。不要因为“链表插入是 O(1)”就默认选择它;遍历成本、缓存未命中和节点分配开销往往同样重要。