C++中std::deque详解和实战工程代码示例

std::deque（双端队列）是 C++ 标准库中的一个序列容器，与 std::vector 类似，但它支持从头部和尾部高效地插入和删除元素。它底层采用分段连续空间实现，兼具灵活性与性能。

一、基本特性

特性	描述
随机访问	支持下标访问（`operator[]`、`at()`）
快速头尾操作	`push_front` 和 `push_back` 效率高，优于 `vector` 的头部插入
分段存储结构	非一块连续内存，适合频繁的插入删除场景
迭代器失效规则	插入删除可能导致部分迭代器失效，需小心

二、使用注意事项（易错点）

1. 与 `vector` 的差异

std::deque 并不保证所有元素在一块连续内存中存储，不能通过 &deque[0] 获取整个数组地址。
不适合与 C 风格 API 一起使用（比如 memcpy(&deque[0], ...) 可能导致未定义行为）。

2. 迭代器失效

插入或删除任意位置的元素都会使所有迭代器失效，不同于 vector 只在 reallocation 时失效。

std::deque<int> dq = {1, 2, 3, 4};
auto it = dq.begin();
dq.push_front(0); // it 现在已失效！

3. 频繁中间插入性能低

插入/删除位于中间位置的元素效率低，需移动大量元素。
如需频繁中间插入，建议使用 std::list。

4. 容量管理

没有 capacity() 函数（不像 vector），不能预留空间，使用方式略有不同。

5. 对象构造开销

每次插入都可能涉及对象构造和移动，注意对象拷贝开销。

三、常用操作代码示例

示例 1：基本使用

#include <iostream>
#include <deque>int main() {std::deque<int> dq;dq.push_back(1);   // 尾部插入dq.push_front(0);  // 头部插入dq.push_back(2);for (int val : dq)std::cout << val << " ";  // 输出：0 1 2dq.pop_front();  // 删除头部dq.pop_back();   // 删除尾部std::cout << "\nFront: " << dq.front();  // 输出：1std::cout << "\nBack: " << dq.back();    // 输出：1
}

示例 2：模拟滑动窗口（典型应用）

#include <deque>
#include <vector>
#include <iostream>std::vector<int> maxSlidingWindow(const 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();   // 保持单调性dq.push_back(i);if (i >= k - 1)result.push_back(nums[dq.front()]);}return result;
}

四、实际应用场景

场景	使用原因
滑动窗口算法	快速删除/插入头尾元素
限长队列（日志、缓存）	自动弹出旧元素，控制内存
多线程任务队列（需加锁）	支持双端插入，配合 `mutex` 使用
状态机缓冲器	记录有限长度状态序列

五、工程应用实战

下面是两个典型 std::deque 实战场景的完整示例代码，适合用于滑动窗口最大值算法和限长队列（比如日志或缓存）实现。

示例一：滑动窗口最大值（单调队列优化）

用于处理如：[1,3,-1,-3,5,3,6,7]，滑动窗口大小 k=3 时，每个窗口内的最大值。

功能说明：

保持一个单调递减队列（deque中存下标）。
窗口滑动时移除已滑出的元素。
每次窗口满了就将最大值加入结果。

示例代码：

#include <iostream>
#include <vector>
#include <deque>std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {std::deque<int> dq;std::vector<int> result;for (int i = 0; i < nums.size(); ++i) {// 移除滑出窗口的元素if (!dq.empty() && dq.front() <= i - k)dq.pop_front();// 保持队列单调递减（移除小于当前值的）while (!dq.empty() && nums[dq.back()] < nums[i])dq.pop_back();dq.push_back(i);  // 存下标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;auto result = maxSlidingWindow(nums, k);std::cout << "滑动窗口最大值：";for (int val : result)std::cout << val << " ";  // 输出：3 3 5 5 6 7std::cout << std::endl;
}

示例二：限长队列（固定大小缓存或日志）

模拟一个最大容量为 N 的队列，插入新元素时若超过容量，自动从头部弹出旧元素。

功能说明：

封装成 LimitedQueue<T> 模板类
支持 push()，pop()，size()，front()，back() 等基本操作

示例代码：

#include <iostream>
#include <deque>template <typename T>
class LimitedQueue {
public:LimitedQueue(size_t capacity) : max_size(capacity) {}void push(const T& value) {if (dq.size() >= max_size)dq.pop_front();  // 超出容量，弹出旧元素dq.push_back(value);}void print() const {for (const auto& item : dq)std::cout << item << " ";std::cout << "\n";}size_t size() const { return dq.size(); }private:std::deque<T> dq;size_t max_size;
};int main() {LimitedQueue<int> q(5);  // 最多保存 5 个元素for (int i = 1; i <= 10; ++i) {q.push(i);std::cout << "插入 " << i << " 后队列内容：";q.print();}
}

输出示例：

插入 1 后队列内容：1 
插入 2 后队列内容：1 2 
插入 3 后队列内容：1 2 3 
插入 4 后队列内容：1 2 3 4 
插入 5 后队列内容：1 2 3 4 5 
插入 6 后队列内容：2 3 4 5 6 
插入 7 后队列内容：3 4 5 6 7 
...

六、与其他容器对比

特性	`vector`	`deque`	`list`
随机访问	✅	✅	❌
快速尾部插入	✅（均摊常数）	✅	✅
快速头部插入	❌（O(n)）	✅	✅
中间插入/删除	❌（慢）	❌（稍快）	✅（快）
内存连续性	✅	❌（分段）	❌