选对容器，编程事半功倍！——C++序列容器选择指南

你有没有遇到过这种情况：写程序时，需要存一堆数据，但又不知道用哪种“盒子”来装最合适？就像出门旅行，要根据天数、行李多少、拿取习惯来选箱子：小背包、拉杆箱、双肩包、编织袋……没有最好，只有最合适。在C++里，序列容器就是一套“箱子”，它们负责帮你存储、管理一系列元素，但各有各的脾气。今天我们就来认识它们——array、vector、deque、list，学会根据需求挑出最趁手的那一个。

什么叫序列容器？它们用来干什么？

简单说，序列容器就是按顺序存放数据的东西。你可以往里面加东西、删东西、取东西。C++里最常用的四种序列容器分别是：

array：固定大小的小箱子（比如药盒，7天药量固定）
vector：能自动变大的大箱子（比如书包，装不下了能胀大）
deque：两头都能开的箱子（比如行李箱，从上面和下面都能掏东西）
list：可以随时拆拼的链条箱（比如火车车厢，中间加一节或去掉一节都很容易）

它们都来自STL（标准模板库），学会选对容器，你的程序会跑得更快、写起来更轻松。

四大家族特性大比拼

先看一张总表，心里有个数：

特性	array	vector	deque	list
大小	固定（编译时确定）	动态可变	动态可变	动态可变
内存布局	连续	连续	分块连续（逻辑连续）	非连续（节点分散）
随机访问	O(1)	O(1)	O(1)（稍慢）	不支持（只能遍历）
头部插入/删除	不支持	O(n)	O(1)	O(1)
尾部插入/删除	不支持	均摊O(1)	O(1)	O(1)
中间插入/删除	不支持	O(n)	O(n)	O(1)（需已知迭代器）
迭代器失效	不可能	插入可能使所有迭代器失效（扩容）	头尾操作不失效，中间插入/删除可能失效	除了被删除的节点，其他不失效
内存占用	最小（只有数据）	数据 + 少量容量预留	数据 + 中控结构和缓冲区碎片	数据 + 两个指针（双向）
特有算法	fill, swap	sort（通用）	sort（通用）	sort, splice, merge等
适用场景	大小编译期已知，无需改变	动态增长，主要尾部操作，需要随机访问	需要头尾操作，偶尔随机访问	频繁中间插入删除，无需随机访问

小贴士：O(1)就是“不管数据有多少，花的时间都一样”；O(n)就是“数据翻倍，时间也翻倍”。哪项操作常见，就选那项O(1)的容器。

逐一了解每个容器：特点+生活例子+代码

1. `array` —— 固定大小，永不超支

什么时候用：大小在写代码时就定死了，以后也不变。比如：一年12个月，一周7天，棋盘8×8，班级固定学号。

生活例子：像装鸡蛋的蛋托，一格一个，不能多不能少。鸡蛋多了放不下，少了空着浪费。

优点：速度最快，内存占用最小（和普通数组一样），有STL的接口（at、size等），可以整体赋值。

缺点：不能变大也不能变小。如果数据量可能变化，千万别用它。

#include <array>
using namespace std;

array<int, 7> week_days = {1,2,3,4,5,6,7}; // 固定7天，不能多也不能少
// week_days.size() 返回7
// 访问: week_days[0] 或 week_days.at(0)

2. `vector` —— 万能选手，99%的情况选它没错

什么时候用：大部分时候。尤其是需要随机访问（用下标很快），并且主要在尾部添加/删除。比如学生成绩动态增多、游戏中的角色列表。

生活例子：一个能伸缩的书包，书放不下时会自动变大一点。但如果你要从书包中间抽出一本书，后面的书都要往前挪（很慢），或者往书包最前面塞一本书，后面的书都要往后挪（也很慢）。所以最好只从顶部（尾部）拿或放。

优点：连续内存，缓存友好（计算机处理连续数据超快），访问极快，自动扩容。

缺点：头部和中间插入删除很慢（要移动后面所有元素）。扩容时可能复制所有元素（偶尔会卡一下）。

#include <vector>
using namespace std;

vector<int> scores;      // 初始为空
scores.push_back(95);    // 尾部添加，O(1)
scores.push_back(87);
scores.push_back(92);
// scores = [95, 87, 92]
cout << scores[1];       // 输出87，随机访问O(1)
scores.insert(scores.begin() + 1, 100); // 在中间插入，后面的往后移，O(n)

扩容小知识：当vector空间不够时，它会申请一块更大的新内存（通常是当前容量的2倍），然后把所有元素复制过去，再释放旧内存。所以偶尔一次插入会很慢，但平均下来仍然很快（均摊O(1)）。

3. `deque` —— 两头操作的能手

什么时候用：需要频繁在头部和尾部操作。比如一个双端队列（排队时可以从前面走，也可以从后面加人），或者“滑动窗口”算法中需要在两端操作。

生活例子：一个两头都能打开的行李箱。你可以在箱子顶部放衣服，也可以在箱子底部塞鞋子。但如果你要翻箱子中间的东西，就要先把上面或下面的东西拿出来（随机访问虽然快，但不如vector连续）。

优点：头尾插入删除都是O(1)；支持随机访问（虽然稍微慢一点点）。

缺点：内存不是一整块，而是分成很多小块，对缓存不太友好；中间插入删除仍然是O(n)。

#include <deque>
using namespace std;

deque<int> dq;
dq.push_back(10);   // 尾部添加，O(1)
dq.push_front(20);  // 头部添加，O(1)
// dq = [20, 10]
cout << dq[0];      // 输出20，随机访问O(1)

对比：如果你只需要尾部操作，用vector更好；如果头尾都需要，用deque更平衡。

4. `list` —— 插入删除的艺术家

什么时候用：需要频繁在任意位置（尤其是中间）插入和删除，并且不关心随机访问（不需要用下标取元素）。比如一个待办事项列表，你经常要在中间加一项或删一项。

生活例子：一列火车车厢，每节车厢之间用挂钩连接（双向链表）。你可以随时在中间加一节车厢（只需改几个挂钩），也可以随时拆掉一节（同样很快）。但如果你想直接坐进第5节车厢，你需要从车头一节一节走过去（不能跳）。

优点：任意位置插入删除都是O(1)（只要你有那个位置的迭代器）；其他迭代器不会失效。

缺点：不能随机访问（只能用循环遍历）；每个元素额外存两个指针（内存开销大）；遍历慢（因为内存不连续）。

#include <list>
using namespace std;

list<int> my_list = {1, 2, 4, 5};
auto it = my_list.begin();
advance(it, 2);            // 走到第3个位置（指向4）
my_list.insert(it, 3);     // 在4前面插入3，O(1)
// my_list = [1, 2, 3, 4, 5]
my_list.erase(it);         // 删除刚才的4（注意it指向的元素变了），O(1)

如何决定用哪个？—— 决策流程图（文字版）

问自己几个问题：

大小在写代码时就已经固定，并且以后不改？
- 是 → array（最轻量，就像一次性任务）
- 否 → 继续往下
需要通过下标快速访问任意元素吗？
- 是（即需要随机访问）→ 继续
- 否 → 跳到问题5
你主要从哪一端操作？
- 仅尾部操作（push_back/pop_back）→ vector（最快）
- 头尾都频繁操作 → deque（两端都是O(1)）
- 中间也要频繁操作 → 矛盾来了：需要随机访问，但中间插入删除vector/deque都是O(n)。怎么办？
  - 如果随机访问更重要，忍受中间操作的慢 → 仍然用 vector
  - 如果中间操作更重要，放弃随机访问 → 选 list（但你会失去随机访问，只能用迭代器遍历）
（不需要随机访问）你实际的操作模式？
- 中间插入删除频繁 → list（O(1)插入删除）
- 只有头尾操作 → 如果只尾部操作，vector也可以；但deque两端均衡，推荐 deque
- 偶尔需要随机访问？ 其实deque也支持随机访问，所以可能deque更灵活

一句话总结：

默认 vector

头尾都要操作用 deque

中间要频繁插入删除且不要随机访问用 list

大小固定用 array

新手最容易犯的错误 ❌

错误1：滥用 `list`

很多初学链表的人觉得“插入快”，就无脑用list。结果发现遍历特别慢、内存占用大，而且没法用下标随机访问。实际上在大多数编程题中（比如统计、排序、随机访问），vector比list快很多倍。记住：除非你确定频繁中间插入删除且数据量很大，否则先用 vector。

错误2：忽视 `deque` 的中间操作性能

有些同学看到deque头尾快，就以为它中间也快。其实它在中间插入/删除也是O(n)，因为要移动元素。它和vector在中间操作上一样慢。

错误3：频繁调用 `list.size()` 导致性能问题

C++11之前，某些实现（如GCC）的list::size()是O(n)的，因为要遍历整个链表数元素个数。虽然C++11标准强制为O(1)，但为了保险，检查是否为空用empty()而不是size()==0。

错误4：在需要随机访问时强行用 `list`

比如你要用下标 list[i]，发现编译错误，然后改成遍历。如果经常这样，程序会慢得让人抓狂。

完整可运行示例：谁是速度之王？

下面用C++跑一个性能小测试，看看四种容器在尾部插入、头部插入、随机访问上的表现。你可以复制到自己的编译器上跑一跑，感受差异。

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <chrono>   // 用于计时
#include <numeric>  // iota
using namespace std;
using namespace chrono;

int main() {
    const int N = 100000;  // 十万个元素

    // ---------- 测试尾部插入 ----------
    auto start = high_resolution_clock::now();
    vector<int> v;
    for (int i = 0; i < N; ++i) v.push_back(i);
    auto end = high_resolution_clock::now();
    auto vec_time = duration_cast<milliseconds>(end - start).count();
    cout << "vector尾部插入" << N << "次: " << vec_time << "ms" << endl;

    start = high_resolution_clock::now();
    deque<int> dq;
    for (int i = 0; i < N; ++i) dq.push_back(i);
    end = high_resolution_clock::now();
    auto dq_time = duration_cast<milliseconds>(end - start).count();
    cout << "deque尾部插入" << N << "次: " << dq_time << "ms" << endl;

    start = high_resolution_clock::now();
    list<int> li;
    for (int i = 0; i < N; ++i) li.push_back(i);
    end = high_resolution_clock::now();
    auto list_time = duration_cast<milliseconds>(end - start).count();
    cout << "list尾部插入" << N << "次: " << list_time << "ms" << endl;

    // ---------- 测试随机访问求和 ----------
    start = high_resolution_clock::now();
    long long sum_v = 0;
    for (int i = 0; i < N; ++i) sum_v += v[i];
    end = high_resolution_clock::now();
    cout << "vector随机访问求和: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    start = high_resolution_clock::now();
    long long sum_dq = 0;
    for (int i = 0; i < N; ++i) sum_dq += dq[i];
    end = high_resolution_clock::now();
    cout << "deque随机访问求和: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    // list没有随机访问，无法测试，跳过

    // ---------- 测试头部插入10000次 ----------
    start = high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) v.insert(v.begin(), i); // 1万次
    end = high_resolution_clock::now();
    cout << "vector头部插入10000次: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    start = high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) dq.push_front(i);
    end = high_resolution_clock::now();
    cout << "deque头部插入10000次: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    start = high_resolution_clock::now();
    for (int i = 0; i < 10000; ++i) li.push_front(i);
    end = high_resolution_clock::now();
    cout << "list头部插入10000次: " << duration_cast<milliseconds>(end - start).count() << "ms" << endl;

    return 0;
}

运行结果大致趋势（不同电脑可能不同）：

vector 尾部插入最快，随机访问最快；但头部插入巨慢。
deque 尾部插入略慢于vector，头部插入很快，随机访问比vector慢一点。
list 尾部插入因为每次要分配节点，稍慢；头部插入也很快；但无法随机访问。

小实验：你可以把数据量改成100万，观察差别更明显。

Python也有类似的选择

Python中，最常用的序列容器是 list（类似vector）和 collections.deque（类似deque）。Python没有内置链表（除非自己写），所以中间插入通常用list配合insert，但速度慢，必要时可以用deque或array模块。

这里给一个Python版的小测试，帮助你理解：

import time
from collections import deque

N = 100000

# 尾部插入
v = []
start = time.perf_counter()
for i in range(N):
    v.append(i)
print("list尾部插入: {:.2f}ms".format((time.perf_counter()-start)*1000))

dq = deque()
start = time.perf_counter()
for i in range(N):
    dq.append(i)
print("deque尾部插入: {:.2f}ms".format((time.perf_counter()-start)*1000))

# 随机访问求和
start = time.perf_counter()
s = 0
for i in range(N):
    s += v[i]
print("list随机访问求和: {:.2f}ms".format((time.perf_counter()-start)*1000))

start = time.perf_counter()
s = 0
for i in range(N):
    s += dq[i]
print("deque随机访问求和: {:.2f}ms".format((time.perf_counter()-start)*1000))

# 头部插入10000次
v2 = []
start = time.perf_counter()
for i in range(10000):
    v2.insert(0, i)
print("list头部插入10000次: {:.2f}ms".format((time.perf_counter()-start)*1000))

dq2 = deque()
start = time.perf_counter()
for i in range(10000):
    dq2.appendleft(i)
print("deque头部插入10000次: {:.2f}ms".format((time.perf_counter()-start)*1000))

你会发现：Python的list头部插入超慢（因为要移动所有元素），而deque头部插入飞快。

总结与下一步学习

黄金法则：默认选 vector，除非你明确知道某个容器更适合。
常用组合：
- 只需要尾部：vector
- 头尾都需要：deque
- 中间频繁插入删除且不用下标：list
- 大小固定：array
进阶思考：如果你既要随机访问又要频繁中间插入，可以考虑“分段”数据结构（如deque+vector），或者使用关联容器（如set、map）——但那是另一个话题了。

学会了这些容器，你就有了一个趁手的工具箱。下一站可以学习关联容器（set、map），它们用树结构组织数据，插入和查找都很快。或者看看容器适配器（stack、queue、priority_queue），它们是在已有容器上“加个盖子”实现的特殊结构。

记住：没有完美的容器，只有最适合当前问题的容器。当你写代码前多想一想“我主要做什么操作”，就能少踩很多坑，写出又快又优雅的程序。

序列容器的比较与选择策略