C++ 容器类 <deque>（深入浅出）

C++ 容器类 的核心优势与实用指南

在 C++ 的标准模板库（STL）中，deque 是一个非常实用且高效的容器类。它全称为 "double-ended queue"，即双端队列。如果你熟悉队列（queue）的概念，那么 deque 可以看作是它的增强版——不仅支持在队尾插入和删除元素，还允许在队头进行同样的操作。这种灵活性使得 deque 在很多算法和数据结构场景中表现出色。

对于初学者来说，deque 可能不如 vector 那样常见，但它在处理需要频繁在两端操作数据的场景时，性能远超传统数组或 vector。比如实现滑动窗口、任务调度、多线程缓冲区等，deque 都是理想选择。

在接下来的内容中，我会带你从基础用法到高级技巧，一步步掌握 C++ 容器类 <deque> 的使用方法。通过实际代码示例和详细注释，确保你不仅能“会用”，还能“懂原理”。

什么是 deque？它与 vector 有何不同？

deque 是一种序列容器，它支持在容器的前端和后端进行高效插入与删除操作。这与 vector 的设计哲学有本质区别。

vector 内部使用连续内存块存储元素，因此在尾部插入元素时效率很高（O(1)），但在头部插入或删除时，需要移动所有元素，时间复杂度为 O(n)，效率较低。而 deque 采用分段存储策略——它将数据划分为多个固定大小的块（通常称为“缓冲区”），每个块独立管理。这种设计让 deque 在两端操作时都能保持 O(1) 的时间复杂度。

你可以把 deque 想象成一条可以双向延伸的传送带：你既可以往左边加货物，也可以往右边加货物，而不需要重排整个传送带。这正是 deque 的核心优势。

创建数组与初始化

在使用 deque 之前，首先要包含头文件并正确声明变量。

#include <deque>
#include <iostream>

int main() {
    // 方法 1：创建一个空的 deque，存储 int 类型
    std::deque<int> dq1;

    // 方法 2：使用初始化列表创建并赋值
    std::deque<int> dq2 = {10, 20, 30, 40, 50};

    // 方法 3：指定大小和初始值
    std::deque<int> dq3(5, 99); // 创建 5 个元素，每个都是 99

    // 方法 4：从其他容器复制构造
    std::vector<int> vec = {1, 2, 3};
    std::deque<int> dq4(vec.begin(), vec.end());

    // 输出验证
    std::cout << "dq2: ";
    for (int val : dq2) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

注释说明：

• std::deque<int> 表示一个存储整数的双端队列。
• 初始化列表 {10, 20, ...} 是 C++ 11 引入的语法，简洁且直观。
• dq3(5, 99) 创建 5 个元素，值均为 99，适用于预设填充场景。
• dq4 从 vector 构造，展示了容器间的通用性。

常用操作：插入与删除

deque 支持多种插入和删除方式，以下是最常用的几个函数：

#include <deque>
#include <iostream>

int main() {
    std::deque<std::string> names;

    // 在队尾插入元素
    names.push_back("Alice");
    names.push_back("Bob");
    names.push_back("Charlie");

    // 在队头插入元素
    names.push_front("David");

    // 输出当前内容
    std::cout << "当前 deque 内容：";
    for (const auto& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    // 删除队尾元素
    names.pop_back();
    std::cout << "删除队尾后：";
    for (const auto& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    // 删除队头元素
    names.pop_front();
    std::cout << "删除队头后：";
    for (const auto& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    return 0;
}

注释说明：

• push_back()：在尾部添加元素，时间复杂度 O(1)。
• push_front()：在头部添加元素，同样 O(1)。
• pop_back() 和 pop_front() 分别移除尾部和头部元素。
• 使用范围 for 循环遍历，语法简洁，推荐在实际项目中使用。

随机访问与迭代器支持

虽然 deque 不像 vector 那样保证连续内存，但它仍然支持随机访问（通过下标）和迭代器遍历。

#include <deque>
#include <iostream>

int main() {
    std::deque<double> scores = {88.5, 92.0, 76.5, 95.3, 84.7};

    // 使用下标访问元素（类似数组）
    std::cout << "第 1 个元素：" << scores[0] << std::endl;
    std::cout << "第 3 个元素：" << scores[2] << std::endl;

    // 使用 at() 方法（更安全，会检查越界）
    try {
        std::cout << "第 10 个元素：" << scores.at(9) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "错误：下标越界！" << std::endl;
    }

    // 使用迭代器遍历
    std::cout << "使用迭代器遍历：";
    for (auto it = scores.begin(); it != scores.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

注释说明：

• scores[0] 是最简单的访问方式，但不检查边界。
• scores.at(9) 会抛出 std::out_of_range 异常，适合调试阶段使用。
• 迭代器 begin() 和 end() 提供了标准遍历接口，与 vector 一致。

实际案例：滑动窗口最大值

这是 C++ 容器类 <deque> 的经典应用场景之一。假设你需要在一个数组中找出每个长度为 k 的滑动窗口中的最大值。

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

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::deque<int> dq; // 存储下标，而非值
    std::vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的下标
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 移除所有小于当前元素的值的下标
        // 因为它们不可能成为最大值
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 将当前下标加入 deque
        dq.push_back(i);

        // 当窗口大小达到 k 时，记录最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::vector<int> ans = maxSlidingWindow(nums, k);

    std::cout << "滑动窗口最大值：";
    for (int val : ans) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

注释说明：

• 使用 deque 存储下标，避免重复比较。
• front() 始终指向当前窗口最大值的下标。
• pop_front() 移除过期下标，pop_back() 移除无用下标。
• 时间复杂度 O(n)，每个元素最多入队和出队一次。

性能对比与适用场景建议

总结建议：

• 如果你主要在尾部操作数据，优先用 vector。
• 如果需要频繁在两端插入/删除，deque 是更佳选择。
• 不要将 deque 用于需要频繁中间访问或大内存拷贝的场景。

结语

C++ 容器类 <deque> 是一个被低估但极其强大的工具。它结合了 vector 的随机访问能力和 list 的双端操作优势，在实际开发中有着广泛的应用。通过本篇文章，你应该已经掌握了 deque 的基本用法、性能特点以及典型应用场景。

记住：没有“最好”的容器，只有“最合适”的容器。当你面对一个需要高效两端操作的问题时，不妨试试 deque。它可能就是你代码性能提升的关键一步。

无论是初学者还是中级开发者，深入理解 deque 的工作机制，都将为你的 C++ 编程能力添砖加瓦。多写、多练、多调试，你一定能熟练驾驭这个强大的工具。