一、vector 的头插之痛（用数据说话）

先看看问题到底有多大：

#include <iostream>
#include <vector>
#include <deque>
#include <ctime>
using namespace std;

int main() {
    const int N = 100000;

    // ① vector 头部插入
    vector<int> v;
    clock_t t1 = clock();
    for (int i = 0; i < N; i++) v.insert(v.begin(), i);   // 每次都往最前面塞
    clock_t t2 = clock();
    cout << "vector 头插 " << N << " 次：" << (double)(t2 - t1) / CLOCKS_PER_SEC << " 秒" << endl;

    // ② deque 头部插入
    deque<int> d;
    clock_t t3 = clock();
    for (int i = 0; i < N; i++) d.push_front(i);          // ★ 就是这一句
    clock_t t4 = clock();
    cout << "deque  头插 " << N << " 次：" << (double)(t4 - t3) / CLOCKS_PER_SEC << " 秒" << endl;
    return 0;
}

典型的输出（你的机器上数字会不同，但差距的量级会一样）：

vector 头插 100000 次：3.85 秒
deque  头插 100000 次：0.002 秒

差了三个数量级。 原因很简单：

• vector 头插：insert(begin(), ...) 要把已有元素全部往后挪一格，每次 O(n)，n 次就是 O(n²)。
• deque 头插：在最前面那块的空位里放进去就行，每次 O(1)。

这就是"选容器"这件事的真实含义——不是风格问题，是算法复杂度问题。同样的需求，选错容器，慢一千倍。

二、deque 的内存长什么样

vector：一整块连续内存，快满时申请一块更大的，整体搬过去。

vector:  [ 0 | 1 | 2 | 3 | 4 | 5 | 空 | 空 ]
           ^begin()                     ^end()     头插 → 全体右移

deque：维护一张"块目录"（中控数组），每个格子指向一块连续内存。数据从两端"往两头长"。

            中控数组
        ┌────┬────┬────┬────┐
        │    │ ●  │ ●  │    │
        └────┴─┬──┴─┬──┴────┘
               │    │
        ┌──────▼─┐ ┌▼──────┐
        │ 5  6  7│ │ 8  9  │      ← 每块内部仍是连续数组
        └────────┘ └───────┘
         ▲头插在这儿加块        ▲尾插在这儿加块

既能 push_front 也能 push_back —— 两头都不用搬家

这就解释了三件事：

一句话：deque = vector 的随机访问能力 + 两端的 O(1) 出入 + 一点点"多次查表"的代价。

三、deque 的操作：和 vector 几乎一样，多两个

#include <iostream>
#include <deque>
#include <string>
using namespace std;

void show(const char *title, const deque<string> &d) {
    cout << title << " [size=" << d.size() << "]：";
    for (size_t i = 0; i < d.size(); i++) cout << d[i] << " ";
    cout << endl;
}

int main() {
    deque<string> d;

    // ── ① 两头加（这是 deque 的存在理由）────
    d.push_back("B");        // 尾加
    d.push_back("C");
    d.push_front("A");       // ★ 头加（vector 做这个要搬家）
    d.push_front("最前面");  // ★ 再来一个
    show("两头加之后", d);

    // ── ② 两头删 ────────────────────────
    d.pop_front();           // ★ 删头（vector 没有这个！）
    d.pop_back();            // 删尾
    show("两头各删一个后", d);

    // ── ③ 随机访问 ──────────────────────
    cout << "d[0] = " << d[0] << "，d.at(1) = " << d.at(1) << endl;
    cout << "front() = " << d.front() << "，back() = " << d.back() << endl;

    // ── ④ 中间操作：和 vector 一样要搬家 ──
    d.insert(d.begin() + 1, "插进来");
    show("中间插入后", d);

    d.erase(d.begin());      // 参数是迭代器
    show("erase(begin()) 后", d);

    // ── ⑤ 遍历：三种写法同 vector ────────
    cout << "范围 for：";
    for (const string &s : d) cout << s << " ";
    cout << endl;

    cout << "size=" << d.size() << "，empty()=" << (d.empty() ? "空" : "非空") << endl;
    return 0;
}

看到什么算成功：

两头加之后 [size=4]：最前面 A B C 
两头各删一个后 [size=2]：A B 
d[0] = A，d.at(1) = B
front() = A，back() = B
中间插入后 [size=3]：A 插进来 B 
erase(begin()) 后 [size=2]：插进来 B 
范围 for：插进来 B 
size=2，empty()=非空

和 vector 的差别只是一张表：

注意最后两行：这是 deque 与 vector 的本质分界—— ① deque 没有 capacity() 和 reserve()：它不靠"一整块"，所以"预留容量"这个动作它不需要。 ② deque 的数据不是一整块：所以别指望 deque 能和 C 风格接口对接（那些老函数要的是"一个连续数组"）。要跟老代码/系统调用对接时，vector 才对。

四、动手 Demo：一个"双向排队"的售票系统

任务：模拟两个入口的排队。前门排的人先服务（FIFO 队列），后门来的人可以插到队头（VIP）。

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
    deque<string> line;

    // 普通顾客从后门来（排在队尾）
    line.push_back("顾客甲");
    line.push_back("顾客乙");
    line.push_back("顾客丙");

    // VIP 从特别通道来（插到队头）
    line.push_front("VIP·张总");

    cout << "当前排队（从队头到队尾）：";
    for (const string &s : line) cout << s << " ";
    cout << endl;

    // 开始服务：总是服务队头
    cout << "-- 开始服务 --" << endl;
    while (!line.empty()) {
        cout << "正在服务：" << line.front() << "（剩下 " << line.size() - 1 << " 人）" << endl;
        line.pop_front();
    }
    cout << "全部服务完毕，empty()=" << (line.empty() ? "true" : "false") << endl;
    cout << "回头看：queue 的完整形态就是 deque 的两端操作 + 只许从一头进出。" << endl;
    return 0;
}

看到什么算成功：

当前排队（从队头到队尾）：VIP·张总 顾客甲 顾客乙 顾客丙 
-- 开始服务 --
正在服务：VIP·张总（剩下 3 人）
正在服务：顾客甲（剩下 2 人）
正在服务：顾客乙（剩下 1 人）
正在服务：顾客丙（剩下 0 人）
全部服务完毕，empty()=true
回头看：queue 的完整形态就是 deque 的两端操作 + 只许从一头进出。

"只许从一头进、另一头出"就是数据结构里的队列（queue）——用 deque 做它是最自然的（标准库的 std::queue 默认就是拿 deque 当底层的）。"只许一头进出"就是栈（stack）——那个默认用 vector 或在 deque 上限制也行。

五、什么时候用 deque：一张决策表

几个现实里的 deque 用例： - 滑动窗口（比如"最近 10 条消息"）—— 加新的在尾、淘汰旧的在头； - 任务队列（一边收任务、一边发任务）； - BFS 广度优先搜索（图算法里要的"队列"，就是它）； - 撤销/重做（undo/redo） —— 两头的操作栈。

标准库的一个冷知识：std::stack（栈）和 std::queue（队列）默认的底层容器都是 deque（栈也可以指定用 vector）。"容器适配器"就是"拿一个容器，只暴露一部分操作"——就像上面 Demo 里我们手写的那样。

30 秒实验

1. 把 13.1.1 的实验反过来做：把本节开头的对比程序里 deque 改成 vector 的 push_back（尾插）→ 两者就差不多了（尾插对两个容器都是 O(1)）。说明 deque 的优势只在"头"。
2. 验证"中间还是慢"：把 d.push_front(i) 改成 d.insert(d.begin() + d.size() / 2, i)（往正中间插）→ 时间回到秒级。中间插入对任何容器都一样慢（除了 list）。
3. 试 capacity：写一句 d.capacity() → 编译不过（'class std::deque<int>' has no member named 'capacity'）。这是 deque 与 vector 最直接的语法差异。
4. 试 sort：sort(d.begin(), d.end()); → 能编译能运行（deque 的迭代器是随机访问的，满足 sort 的要求）。对比 13.1.3 的 list，那里这就编译不过。

常见误区

1. "deque 就是加强版 vector，那就都用 deque"——不是。vector 有一整块连续内存，所以遍历时的缓存命中率高（CPU 预取友好），实战里vector 遍历通常比 deque 快。默认还是 vector；确实两头都动才换 deque。
2. "deque 也不能和 C 数组对接？可是我写过 &d[0] 啊"——&d[0] 语法上能编译，但语义是错的：它只指向第一块的开头，&d[0] + 100 很可能跑到别的块去了。要连续内存，请用 vector。
3. "deque 也有 reserve"——没有。deque 没有 capacity / reserve / shrink_to_fit。
4. "push_front 比 push_back 慢"——基本一样（都是 O(1)），只是头部要挂新块的概率稍高，实际几乎无感。
5. "deque 的内存一定比 vector 省"——相反，通常略多：它要额外维护那张块目录，而且每块末尾常常有没用上的空隙。空间换时间，老规矩。
6. "迭代器失效的规则和 vector 一样"——不一样，要分开记：
7. vector：扩容时全部失效；push_back 不安全时也可能全部失效。
8. deque：中间 insert / erase → 全部失效；两端 push/pop → 只失效被删的那个指针（其他迭代器仍然有效，但 end() 可能变）。 记这两条的目的很实际：删元素时别继续用旧的迭代器。稳妥做法：it = v.erase(it)（用返回值）。

• ☐ 下一节（13.1.3 链表类模板）

相关笔记

• 向量类模板（含实例01） —— 上一节：默认选择 vector
• 链表类模板 —— 下一节：中间插入的专家，也是三个盒子对比的收尾
• 序列容器 —— 三个盒子的性格总表
• 随机访问迭代器 —— 为什么 deque 也能 sort
• 指针 —— 链表靠指针串起来的底层
• 🔷 C++基础 · 索引 —— 全课路线图