C++ STL deque底层结构揭秘 双端队列实现原理

deque高效实现双端操作因其分段连续内存结构，由中控器管理多个固定大小缓冲区，逻辑上构成连续序列。①插入删除时无需整体扩容，仅分配新缓冲区，两端操作时间复杂度为常数级；②随机访问需两次寻址，效率略低于vector；③迭代器为复杂类对象，记录缓冲区边界及中控器指针，支持跨缓冲区跳转；④中间操作仍需移动元素，效率较低。

C++ STL 中的 deque（双端队列）之所以能高效地在两端进行插入和删除操作，是因为它的底层数据结构并不是简单的连续内存块，而是由多个固定大小的缓冲区组成。这种设计让它既保留了数组的部分优点，又避免了频繁扩容带来的性能问题。

分段式连续内存结构

deque 的核心实现是通过一个“中控器”（map）来管理多个小块连续内存（称为缓冲区或块）。每个缓冲区通常大小固定（默认一般是 512 字节或者根据元素类型调整），这些缓冲区本身不一定是连续的，但逻辑上它们构成一个连续的序列。

你可以把 deque 想象成一本书的目录加上很多张独立的纸页。目录记录了每一页的位置，而每一页上写满了数据。当你想访问第 N 个元素时，先通过目录找到对应的页，再在那页里找具体位置。

• 这种方式让 deque 在头部或尾部添加元素时几乎不需要移动大量数据。
• 也正因为如此，deque 的随机访问效率略低于 vector，因为每次访问都可能涉及两次寻址。

支持快速插入删除的机制

由于 deque 的内部结构是分段的，它可以在前后端快速分配新的缓冲区，从而实现高效的 push_front 和 push_back 操作。

举个例子：

• 当当前缓冲区的头部没有空间时，deque 会尝试在前面分配一个新的缓冲区。
• 如果前面也没有空间容纳新缓冲区指针，则扩展“中控器”来容纳更多缓冲区。

这样做的好处是：

• 插入操作的时间复杂度仍然是常数级别的（摊销后）
• 不需要像 vector 那样频繁重新分配整个内存块并复制数据

不过要注意的是，中间位置的插入和删除仍然需要移动元素，所以这部分效率并不如两端操作那么高。

内存管理与迭代器实现

为了支持随机访问，deque 的迭代器不是普通的指针，而是一个更复杂的类对象。这个迭代器不仅要记录当前指向的元素位置，还要知道当前所在的缓冲区、缓冲区的边界等信息。

当迭代器递增跨越当前缓冲区的边界时，它会自动跳转到下一个缓冲区，保持逻辑上的连续性。

• 迭代器内部通常包含四个指针：当前元素指针、当前缓冲区起始、结束位置，以及指向“中控器”的指针。
• 这种设计使得 operator[] 和 at() 等操作也能以对数时间复杂度完成。

小结

deque 的实现本质上是在性能和灵活性之间做了权衡。它不像 vector 那样简单直接，但胜在更适合频繁在两端操作的场景。理解其底层结构有助于我们在使用时做出更合适的选择。

基本上就这些。