std::deque 是 C++ 标准模板库（STL）中的一个双端队列（Double-ended Queue）容器。它是一种动态数组，允许快速地在序列的两端插入和删除元素，同时支持随机访问。
特点
-
双端操作
支持在队列头部和尾部快速插入和删除元素，复杂度为 O(1)。 -
随机访问
提供与std::vector类似的随机访问功能，支持operator[]和at()方法。 -
动态扩展
不像std::vector使用连续内存块，std::deque使用一系列的小内存块组成。它可以高效地动态扩展，而不需要像std::vector那样重新分配和拷贝。 -
迭代器有效性
插入或删除不会使其他元素的迭代器失效，除非操作的是两端。 -
性能
在两端插入、删除时性能优于std::vector，但中间插入或删除性能略逊于std::vector。
常用接口
构造函数
#include <deque>
std::deque<int> d1; // 默认构造空 deque
std::deque<int> d2(5, 10); // 创建 5 个值为 10 的元素
std::deque<int> d3{1, 2, 3}; // 使用列表初始化
std::deque<int> d4(d3.begin(), d3.end()); // 从迭代器范围初始化
元素访问
std::deque<int> d = {1, 2, 3, 4};
std::cout << d[0] << std::endl; // 访问第一个元素 (不检查越界)
std::cout << d.at(1) << std::endl; // 访问第 2 个元素 (检查越界)
std::cout << d.front() << std::endl; // 返回第一个元素
std::cout << d.back() << std::endl; // 返回最后一个元素
修改操作
std::deque<int> d;
d.push_back(1); // 尾部插入 1
d.push_front(2); // 头部插入 2
d.pop_back(); // 移除尾部元素
d.pop_front(); // 移除头部元素d.insert(d.begin() + 1, 3); // 在指定位置插入 3
d.erase(d.begin()); // 移除指定位置的元素
d.clear(); // 清空所有元素
大小操作
std::deque<int> d = {1, 2, 3};
std::cout << d.size() << std::endl; // 返回元素个数
std::cout << d.empty() << std::endl; // 判断是否为空
排序
#include <algorithm>
std::deque<int> d = {4, 1, 3, 2};
std::sort(d.begin(), d.end()); // 对 deque 排序
遍历
for (auto it = d.begin(); it != d.end(); ++it) {std::cout << *it << " ";
}
for (int val : d) { // 基于范围的循环std::cout << val << " ";
}
应用场景
-
双端操作的场景
适用于需要在头尾频繁插入或删除的场景，例如滑动窗口问题。 -
替代
虽然std::queuestd::queue是基于std::deque实现的，但如果需要随机访问或对队列内容排序，可以直接使用std::deque。 -
缓存系统
由于支持两端高效操作，std::deque常用于实现 LRU 缓存等机制。
举例：
#include <deque>
#include <iostream>int main() {std::deque<int> dq = {10, 20, 30};dq.push_front(5); // 头部插入dq.push_back(40); // 尾部插入std::cout << "Deque: ";for (int v : dq) {std::cout << v << " ";}std::cout << std::endl;dq.pop_front(); // 移除头部dq.pop_back(); // 移除尾部std::cout << "After pops: ";for (int v : dq) {std::cout << v << " ";}return 0;
}
输出：
Deque: 5 10 20 30 40
After pops: 10 20 30
和 std::vector 的对比
