C++ deque

在 C++ 中，std::deque 是英文 “double-ended queue” 的缩写，中文叫做 “双端队列”，通常读作 “deck”。简单来说，它就像一条两头都敞开的通道，既支持使用下标 [] 访问任意位置的元素，又能直接在序列的头部和尾部两端增删数据。

相比之下，前面学过的 std::vector 只适合在尾部追加或删除元素。如果频繁往 vector 最前面插入数据，后面的元素都要整体往后挪动。因此，当我们需要经常在序列首尾两端进出数据时，使用 std::deque 会比 vector 合适得多。

C++ deque 的创建与访问

使用 std::deque 之前，我们需要先在代码开头引入 <deque> 头文件。

语法：

#include <deque>

std::deque<元素类型> 变量名 = {元素1, 元素2, ...};

说明：

与固定长度的 std::array 不同，std::deque 的元素个数是动态变化的，在程序运行过程中可以随时增加或减少。如果不写初始值，比如直接写 std::deque<int> dq;，就会创建一个空的双端队列。它的常用操作如下表所示。

示例 1：创建与访问 deque

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

int main() {
    std::deque<std::string> colors = {"red", "green", "blue"};

    std::cout << colors.size() << '\n';
    std::cout << colors.front() << '\n';
    std::cout << colors.back() << '\n';
    std::cout << colors.at(1) << '\n';

    colors[1] = "yellow";    // 修改下标为 1 的元素
    for (const std::string& color : colors) {
        std::cout << color << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

3
red
blue
green
red yellow blue

分析：

在这个例子中，我们定义了一个包含 3 个字符串的 deque 容器 colors。其中，colors.front() 和 colors.back() 分别用来获取排在最前面的 "red" 和排在最后面的 "blue"。

同时，std::deque 的下标同样从 0 开始计算，支持直接读写任意位置的元素。其中 [] 不做边界检查，而 at() 会在下标越界时直接抛出异常报错，这一点与 vector 和 array 完全一致。

在 deque 两端添加和删除元素

std::deque 最鲜明的特点，就是支持在序列的 “头部” 和 “尾部” 两端直接增删数据，不需要我们手动搬动其他元素。

1. 在头部和尾部添加元素

在 C++ 中，向 deque 头部插入元素使用 push_front()，向尾部追加元素使用 push_back()。

语法：

容器名.push_front(元素);
容器名.push_back(元素);

说明：

从英文名字上就很容易记住：push 是 “推入” 的意思，front 表示 “前面”，back 表示 “后面”。前面学过的 std::vector 只有 push_back()，没有提供 push_front()，而 std::deque 两个都有。

示例 2：在两端添加元素

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

int main() {
    std::deque<std::string> dq = {"长沙", "武汉"};

    dq.push_front("广州");    // 在头部插入元素
    dq.push_back("北京");     // 在尾部追加元素

    std::cout << dq[0] << ' ' << dq[1] << '\n';
    for (const std::string& s : dq) {
        std::cout << s << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

广州 长沙
广州 长沙 武汉 北京

分析：

dq.push_front("广州"); 这句代码表示将 "广州" 插入到序列的最前面，紧接着执行的 dq.push_back("北京"); 则把 "北京" 追加到了最后面。

这里小伙伴们要注意一个细节：当新元素插入到头部后，原本排在下标 0 位置的 "长沙" 会自动往后顺移变成下标 1，新加进来的 "广州" 则成为新的下标 0。也就是说，deque 的下标并不是固定绑在某个元素身上的，而是会随着头部元素的增删动态变化。

2. 删除头部和尾部元素

与添加操作相对应，删除 deque 头部元素使用 pop_front()，删除尾部元素使用 pop_back()。

语法：

容器名.pop_front();
容器名.pop_back();

说明：

调用这两个函数时有一个初学者容易忽略的细节：pop_front() 和 pop_back() 的返回值类型都是 void，只负责把元素删掉，不会返回被删掉的值。如果删除前还需要用到该元素的值，我们需要先调用 front() 或 back() 把它保存下来，再执行删除操作。

示例 3：删除两端的元素

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

int main() {
    std::deque<std::string> dq = {"广州", "长沙", "北京"};

    std::string first = dq.front();    // 保存头部元素
    std::string last = dq.back();      // 保存尾部元素

    dq.pop_front();                    // 删除头部元素
    dq.pop_back();                     // 删除尾部元素

    std::cout << "已移除：" << first << "、" << last << '\n';
    std::cout << "剩余：" << dq.front() << '\n';
    return 0;
}

运行结果如下。

已移除：广州、北京
剩余：长沙

分析：

上面代码中，我们先通过 front() 和 back() 把首尾的城市名存进变量里，随后调用 dq.pop_front() 移除了头部的 "广州"，调用 dq.pop_back() 移除了尾部的 "北京"，容器里最终只剩下中间的 "长沙"。

由于 pop_front() 和 pop_back() 没有返回值，平时写代码时千万不要把它们放在等号右边去给变量赋值。如果写成下面这样，编译时就会直接报错：

std::string first = dq.pop_front();    // pop_front() 无返回值

deque 与 vector 的区别

std::deque 和 std::vector 都是支持下标 [] 访问的动态序列容器，而且都能直接配合 <algorithm> 头文件中的 std::sort() 等通用算法使用。它们的主要区别在于底层内存的组织方式。

• std::vector（单块连续内存）：所有元素紧挨在一整块连续内存中，按下标访问和从头到尾遍历的速度非常快。但如果在最前面插入或删除元素，后面的所有元素都要整体挪动位置，开销很大，所以 vector 没有提供 push_front() 和 pop_front()。
• std::deque（分段连续内存）：底层由多段定长内存块拼接而成，不要求所有元素挤在同一块连续内存里。这种结构让它在头部和尾部都能直接扩充或移除元素，不需要搬动中间的数据，不过按下标访问和遍历的速度比 vector 略慢一点。

因此在实际开发中，如果主要是在尾部追加、按下标访问或顺序遍历，我们默认优先使用 std::vector。如果需要频繁在序列首尾两端增删元素，则优先选择 std::deque。此外，后面要学习的栈 std::stack 和队列 std::queue，底层默认也都是基于 std::deque 来实现的。