deque 内部机制

定义与作用

std::deque（double-ended queue，双端队列）是一种分段数组——元素并非连续存储在一块内存中，而是分布在多个固定大小的块中，通过中控器（map of pointers）管理。支持 O(1) 两端增删和 O(1) 随机访问。

#include <deque>
std::deque<int> dq{1, 2, 3};
dq.push_front(0);   // O(1) 头部插入
dq.push_back(4);    // O(1) 尾部插入
int x = dq[2];      // O(1) 随机访问（两次间接跳转）

对比	vector	deque
内存布局	连续单块	分段多块
头部增删	O(n)	O(1)
尾部增删	摊销 O(1)	O(1)
随机访问	O(1) 直接	O(1) 两次跳转
扩容行为	整块重分配+移动	分配新块，中控器扩容
迭代器失效	扩容时全失效	仅被操作块附近失效

核心原理

分段数组结构

典型块大小：GCC 512 字节（64 个 int），MSVC 16 字节或元素大小。

push_front 与 push_back 过程

完整示例

示例一：飞翔科技任务调度队列

场景说明：白歌用 deque 实现飞翔科技的动态任务调度器，新紧急任务插入前端，普通任务追加尾端。

#include <iostream>
#include <deque>
#include <string>

struct Task {
    int id;
    std::string name;
    int priority;  // 值越大越紧急

    Task(int i, std::string n, int p)
        : id(i), name(std::move(n)), priority(p) {}
};

class TaskScheduler {
public:
    // 紧急任务：插入前端
    void addUrgent(Task t) {
        tasks_.push_front(std::move(t));
        std::cout << "[紧急] 任务#" << tasks_.front().id
                  << " 插入队首\n";
    }

    // 普通任务：追加末端
    void addNormal(Task t) {
        tasks_.push_back(std::move(t));
        std::cout << "[普通] 任务#" << tasks_.back().id
                  << " 追加队尾\n";
    }

    // 取最高优先级任务（简单遍历）
    Task popHighest() {
        auto best = tasks_.begin();
        for (auto it = tasks_.begin(); it != tasks_.end(); ++it) {
            if (it->priority > best->priority) best = it;
        }
        Task result = std::move(*best);
        tasks_.erase(best);
        return result;
    }

    void print() const {
        std::cout << "队列 [";
        for (size_t i = 0; i < tasks_.size(); ++i)
            std::cout << tasks_[i].name << "|";
        std::cout << "]\n";
    }

    size_t size() const { return tasks_.size(); }

private:
    std::deque<Task> tasks_;
};

int main() {
    TaskScheduler scheduler;

    scheduler.addNormal({1, "飞翔科技-日报统计", 2});
    scheduler.addNormal({2, "飞翔科技-日志归档", 1});
    scheduler.addUrgent({3, "飞翔科技-支付异常-紧急", 9});
    scheduler.addNormal({4, "飞翔科技-缓存预热", 3});
    scheduler.addUrgent({5, "飞翔科技-数据库连接池耗尽", 10});

    scheduler.print();
    std::cout << "队列大小: " << scheduler.size() << "\n";

    // 按优先级弹出
    std::cout << "\n--- 按优先级执行 ---\n";
    while (scheduler.size() > 0) {
        Task next = scheduler.popHighest();
        std::cout << "执行: " << next.name
                  << " (优先级: " << next.priority << ")\n";
    }
}

预期输出：

[普通] 任务#1 追加队尾
[普通] 任务#2 追加队尾
[紧急] 任务#3 插入队首
[普通] 任务#4 追加队尾
[紧急] 任务#5 插入队首
队列 [飞翔科技-数据库连接池耗尽|飞翔科技-支付异常-紧急|飞翔科技-日报统计|飞翔科技-日志归档|飞翔科技-缓存预热|]
队列大小: 5

--- 按优先级执行 ---
执行: 飞翔科技-数据库连接池耗尽 (优先级: 10)
执行: 飞翔科技-支付异常-紧急 (优先级: 9)
执行: 飞翔科技-缓存预热 (优先级: 3)
执行: 飞翔科技-日报统计 (优先级: 2)
执行: 飞翔科技-日志归档 (优先级: 1)

逐段分析：

push_front / push_back 都 O(1)，deque 天生适合双端操作
随机访问 tasks_[i] 支持 O(1) 遍历
与 vector 不同：deque 在两端增删不导致已有元素移动

示例二：deque vs vector 前端插入性能对比

场景说明：小崔在代码评审中因使用 vector 做前端插入被白歌指出性能问题。

#include <iostream>
#include <chrono>
#include <deque>
#include <vector>

int main() {
    const int N = 100000;

    // vector 前端插入：O(n) 每次
    {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> v;
        for (int i = 0; i < N; ++i)
            v.insert(v.begin(), i);  // 每次都移动所有元素
        auto elapsed = std::chrono::duration<double, std::milli>(
            std::chrono::high_resolution_clock::now() - start).count();
        std::cout << "vector push_front x " << N << ": "
                  << elapsed << " ms\n";
    }

    // deque 前端插入：O(1) 每次
    {
        auto start = std::chrono::high_resolution_clock::now();
        std::deque<int> dq;
        for (int i = 0; i < N; ++i)
            dq.push_front(i);  // O(1)
        auto elapsed = std::chrono::duration<double, std::milli>(
            std::chrono::high_resolution_clock::now() - start).count();
        std::cout << "deque  push_front x " << N << ": "
                  << elapsed << " ms\n";
    }
}

预期输出（典型）：

vector push_front x 100000: 452.3 ms
deque  push_front x 100000: 1.2 ms

逐段分析：

vector 前端插入：每次 O(n) 移动 → 总 O(n²) ≈ 50 亿次元素移动
deque 前端插入：每次 O(1) 分配或定位 → 总 O(n)
性能差距约 400 倍

易错场景与面试考点

易错场景

1. deque 随机访问比 vector 慢

// deque 的 operator[] 需要两次间接跳转（中控器 → 块）
// 遍历大量数据时 vector 的缓存局部性更好

2. 插入/删除中间元素

// deque 在中间插入元素时，会选择移动较少元素的一侧
// 但依然 O(n)，不如 list 的 O(1)

3. 迭代器失效

std::deque<int> dq{1, 2, 3, 4, 5};
auto it = dq.begin() + 2;
dq.push_front(0);  // 可能导致所有迭代器失效（取决于实现）
dq.pop_back();     // 可能导致 end() 附近失效

面试考点

考点	要点
内存结构	分段数组 + 中控器，非连续存储
vs vector	前端 O(1) vs O(n)，随机访问更慢
块大小	GCC 512B，MSVC 16B 或元素大小
push_front	deque 独有，vector 无
迭代器类型	随机访问迭代器（但比 vector 复杂）
适用场景	双端增删为主、不宜大量随机遍历