概述与特性
定义与核心特性
std::deque，中文常称作“双端队列”，是 C++ 标准库中的一种容器，专门用于在两端实现高效的插入与删除。两端高效插入删除是它的核心特性，配合 随机访问O(1) 能在需要两端和随机访问的场景提供良好性能。
与 std::vector 相比，deque 的内存布局为分块结构，不要求元素在内存中连续存放，这使得在两端扩展时更加灵活，同时也带来遍历时的缓存行为差异。访问时间复杂度为O(1)，但对中间位置的访问和修改通常仍然是线性时间，尤其是在大规模数据时。
基本用法与迭代
构造与访问
常用构造方式包括默认构造、从范围区间构造、以及从初始化列表构造。范围构造与初始化列表可以快速生成一个顺序容器。也支持指定大小并填充初值的构造形式，方便快速创建初始状态的双端队列。
访问元素的方法包括 front()、back()、at() 与 operator[]。at() 会在越界时抛出异常，而 operator[] 不进行边界检查，调用时需自行确保下标合法。随机访问能力使得按下标访问成为可能，适合需要快速检索的场景。
#include
#include int main() {std::deque dq{1, 2, 3, 4, 5};dq.push_front(0);dq.push_back(6);std::cout << "front=" << dq.front() << ", back=" << dq.back() << std::endl;std::cout << "dq[3]=" << dq[3] << std::endl;// 安全访问示例std::cout << "at(2) = " << dq.at(2) << std::endl;return 0;
}
此外，begin() 与 end() 提供的迭代器支持范围遍历，迭代器为随机访问迭代器，可使用下标运算和算术运算进行定位。
常见操作与性能
插入与删除
在两端进行插入与删除时，使用 push_front、push_back、pop_front、pop_back 都具有 O(1) 常数时间复杂度，适合实现双端队列的典型应用模式。
需要在中间位置进行插入或删除时，复杂度通常为 O(n)，因为需要移动位于该位置两端的元素以维持容器的序列性。这一点在设计时要考虑到性能影响，避免在大规模数据上频繁进行中间插入。
#include <deque>
#include <string>
#include <iostream>int main() {std::deque<std::string> dq;dq.push_back("apple");dq.push_front("banana");// 在中间插入auto it = dq.begin() + 1;dq.insert(it, "cherry");// 删除中间元素后仍可继续遍历dq.erase(it);for (const auto &s : dq) std::cout << s << ' ';std::cout << std::endl;return 0;
}
就地构造也很常用，emplace_front 与 emplace_back 可以在容器内部直接构造元素，避免不必要的拷贝与移动。
容量与遍历
容量、查询与遍历
通过 size() 可以获取当前元素个数，通过 empty() 判断是否为空，通过 clear() 清空全部元素。std::deque 的迭代器允许常规遍历与范围基循环，在遍历时应关注分块存储可能带来的缓存差异。
遍历示例展示了从两端向中间的访问模式，以及对迭代器的基本操作，帮助理解在实际编码中的使用方式。遍历性能通常受分块存储影响，但对大多数应用而言仍然高效。
#include <deque>
#include <iostream>int main() {std::deque<int> dq = {10, 20, 30, 40, 50};for (auto it = dq.begin(); it != dq.end(); ++it) {std::cout << *it << ' ';}std::cout << std::endl;return 0;
}
与其他容器的对比与应用场景
对比与选型
与 std::vector 相比，deque 不是连续内存块，在两端扩展时通常比向量更高效，但对局部性缓存的依赖更弱，可能影响对某些算法的缓存友好性。随机访问O(1) 的能力使其在需要快速下标访问时表现不错。
与 std::list 相比，deque 提供了随机访问，而 list 只有线性访问，但后者在中间插入/删除时可能具有较稳定的常数时间（不需要移动元素整块）。在需要两端高效增删且需要随机访问的场景，std::deque 常比 list 更合适；在需要稳定的指针引用和极端内存管理时，list 仍有优势。
#include <deque>
#include <vector>
#include <iostream>int main() {std::deque<int> dq = {1, 2, 3, 4, 5};// 将 deque 转换为向量，便于需要连续内存的场景std::vector<int> v(dq.begin(), dq.end());for (int x : v) std::cout << x << ' ';std::cout << std::endl;return 0;
}
