c++中的std::deque是什么_c++双端队列与vector的比较【STL】-C++-PHP中文网

c++中的std::deque是什么_c++双端队列与vector的比较【STL】

穿越時空

发布： 2025-12-22 14:47:13

原创

933人浏览过

std::deque是C++ STL中支持头尾O(1)增删和O(1)随机访问的分段连续序列容器，内存不连续，迭代器稳定，适用于滑动窗口、任务队列等需频繁头尾操作的场景。

c++中的std::deque是什么_c++双端队列与vector的比较【stl】

std::deque（double-ended queue，双端队列）是 C++ STL 中的一种序列容器，支持在**头部和尾部高效地插入与删除元素**，同时也能像数组一样支持随机访问（O(1) 时间复杂度）。它底层通常由多个固定大小的内存块（如数组段）组成，通过映射表管理，兼顾了两端操作的效率和中间访问的可行性。

deque 的核心特性

• 支持 push_front()、pop_front()、push_back()、pop_back()，所有这些操作平均时间复杂度为 O(1)（摊还）
• 支持下标访问 operator[] 和 at()，随机访问是 O(1)
• 迭代器不是真正意义上的指针，但保证支持 +=、+、- 等算术运算（即“随机访问迭代器”）
• 元素在内存中**不连续**，因此不保证所有元素存储在同一块内存区域中
• 不会因插入/删除导致已有迭代器、引用或指针失效（除非对应位置被删）；但 push_front/push_back 可能使指向首/尾的迭代器失效（具体取决于实现，一般仅影响端点迭代器）

deque 与 vector 的关键区别

• 内存布局：vector 内存连续，deque 分段连续（多段小数组）
• 两端插入/删除：vector 在头部插入（insert(begin(), x) 或 push_front 模拟）是 O(n)；deque 天然支持 O(1) 头尾操作
• 扩容机制：vector 扩容需重新分配+拷贝，可能使所有迭代器失效；deque 扩容只需新增一段内存，对大部分已有元素的迭代器无影响
• 缓存局部性：vector 更友好（连续访问快），deque 跨段访问可能引发更多 cache miss
• 空间开销：deque 额外维护映射结构（如 map 数组），内存占用略大，且不易精确预估容量

什么时候该用 deque 而不是 vector

• 需要频繁在**头部添加或移除元素**（例如实现滑动窗口、任务队列、撤销栈）
• 需要稳定迭代器——在动态增删过程中，仍希望多数迭代器保持有效
• 数据量较大且无法预估增长方向（头/尾都可能扩展），又不想反复 realloc vector
• 不依赖极致的遍历性能，也不需要 & 取地址后做指针运算（因内存不连续）

简单示例对比

// vector 模拟 push_front 效率低
std::vector v = {2,3};
v.insert(v.begin(), 1); // O(n)，所有元素右移

// deque 天然高效
std::deque d = {2,3};
d.push_front(1); // O(1)，无移动

基本上就这些。deque 不是 vector 的替代品，而是互补工具——选谁，关键看你的操作模式：重头尾增删，选 deque；重连续存储和遍历，选 vector。