C++的std::deque有什么用_C++双端队列容器的内部实现与适用场景

std::deque采用分段连续存储，支持首尾O(1)插入删除和O(1)随机访问，适用于两端频繁操作且需索引访问的场景，性能介于vector和list之间。

std::deque（double-ended queue）是C++标准模板库（STL）中的一种序列容器，支持在两端高效地插入和删除元素。它结合了数组的快速访问特性和链表的部分灵活性，是一种非常实用的数据结构。

内部实现原理

std::deque 的底层实现通常采用“分段连续”存储方式，而不是像 std::vector 那样使用单块连续内存。

具体来说，deque 内部维护一个“块数组”（map of chunks），每个块是一段固定大小的连续内存空间。这些块用来存放实际的元素。当在前端或后端插入元素时，deque 会自动分配新的内存块并链接到已有结构中。

这种设计带来的好处包括：

立即学习“C++免费学习笔记（深入）”；

• 首尾插入删除高效：在头部和尾部添加或移除元素的时间复杂度为 O(1)，摊还成本低。
• 支持随机访问：通过重载 [] 操作符和迭代器，可以像数组一样按索引访问元素，时间复杂度为 O(1)。
• 无需整体搬移：扩容时不像 vector 需要复制所有元素，减少了性能开销。

不过由于内存不是完全连续的，deque 的迭代器比 vector 更复杂，通常是封装指针的类对象，用于跨块跳转。

标签： c++ 双端队列 前端 后端