deque高效实现双端操作因其分段连续内存结构，由中控器管理多个固定大小缓冲区，逻辑上构成连续序列。①插入删除时无需整体扩容，仅分配新缓冲区，两端操作时间复杂度为常数级；②随机访问需两次寻址，效率略低于vector；③迭代器为复杂类对象，记录缓冲区边界及中控器指针，支持跨缓冲区跳转；④中间操作仍需移动元素，效率较低。
C++ STL 中的
deque（双端队列）之所以能高效地在两端进行插入和删除操作，是因为它的底层数据结构并不是简单的连续内存块，而是由多个固定大小的缓冲区组成。这种设计让它既保留了数组的部分优点，又避免了频繁扩容带来的性能问题。
分段式连续内存结构
deque的核心实现是通过一个“中控器”（map）来管理多个小块连续内存（称为缓冲区或块）。每个缓冲区通常大小固定（默认一般是 512 字节或者根据元素类型调整），这些缓冲区本身不一定是连续的，但逻辑上它们构成一个连续的序列。
你可以把
deque想象成一本书的目录加上很多张独立的纸页。目录记录了每一页的位置，而每一页上写满了数据。当你想访问第 N 个元素时，先通过目录找到对应的页，再在那页里找具体位置。
立即学习“C++免费学习笔记（深入）”；
- 这种方式让
deque
在头部或尾部添加元素时几乎不需要移动大量数据。 - 也正因为如此，
deque
的随机访问效率略低于vector
，因为每次访问都可能涉及两次寻址。
支持快速插入删除的机制
由于
deque的内部结构是分段的，它可以在前后端快速分配新的缓冲区，从而实现高效的
push_front和
push_back操作。
举个例子：
- 当当前缓冲区的头部没有空间时，
deque
会尝试在前面分配一个新的缓冲区。 - 如果前面也没有空间容纳新缓冲区指针，则扩展“中控器”来容纳更多缓冲区。
这样做的好处是：
- 插入操作的时间复杂度仍然是常数级别的（摊销后）
- 不需要像
vector
那样频繁重新分配整个内存块并复制数据
不过要注意的是，中间位置的插入和删除仍然需要移动元素，所以这部分效率并不如两端操作那么高。
内存管理与迭代器实现
为了支持随机访问，
deque的迭代器不是普通的指针，而是一个更复杂的类对象。这个迭代器不仅要记录当前指向的元素位置，还要知道当前所在的缓冲区、缓冲区的边界等信息。
当迭代器递增跨越当前缓冲区的边界时，它会自动跳转到下一个缓冲区，保持逻辑上的连续性。
- 迭代器内部通常包含四个指针：当前元素指针、当前缓冲区起始、结束位置，以及指向“中控器”的指针。
- 这种设计使得
operator[]
和at()
等操作也能以对数时间复杂度完成。
小结
deque的实现本质上是在性能和灵活性之间做了权衡。它不像
vector那样简单直接，但胜在更适合频繁在两端操作的场景。理解其底层结构有助于我们在使用时做出更合适的选择。
基本上就这些。
