35、deque 容器的扩容机制

1. deque 的底层数据结构

deque（双端队列）的底层实现通常由分块连续内存和中央控制结构组成。具体结构如下：

• 分块存储：元素被存储在多个固定大小的内存块（称为缓冲区）中，每个缓冲区可容纳多个元素（例如 512 字节的块）。
• 中央控制数组：使用一个动态数组（称为 map）管理所有缓冲区的指针，该数组的中间位置通常指向第一个缓冲区，前后保留空间以支持双向扩容。

2. 扩容机制

当在 头部 或 尾部 插入元素时：

1. 当前缓冲区未满：直接插入元素，时间复杂度 $O(1)$。
2. 当前缓冲区已满：
   • 分配新缓冲区：在头部插入时，若第一个缓冲区已满，则在 map 数组的前端分配新缓冲区；在尾部插入时，若最后一个缓冲区已满，则在 map 数组的末端分配新缓冲区。
   • 更新中央控制数组：若 map 数组容量不足，会像 vector 一样扩容（但频率较低），例如分配更大的 map 数组并将原有指针复制到新数组的中间位置。

3. 性能特点

• 头尾操作高效：插入/删除仅需操作缓冲区，无需移动其他元素。
• 随机访问支持：通过计算索引所在缓冲区和偏移量，实现 $O(1)$ 访问。
• 中间操作低效：插入/删除需移动元素，时间复杂度为 $O(n)$。

4. 与 vector 的对比

特性	deque	vector
头尾插入/删除	$O(1)$	尾部 $O(1)$，头部 $O(n)$
中间插入/删除	$O(n)$	$O(n)$
扩容代价	仅分配新缓冲区	全量复制元素
内存连续性	逻辑连续，物理分块	完全连续

5. 示例代码：deque 的扩容行为

#include <deque>
#include <iostream>int main() {std::deque<int> dq;for (int i = 0; i < 10; ++i) {dq.push_back(i);std::cout << "Size: " << dq.size() << ", 内存块数量估算: " << (dq.size() + 512 / sizeof(int) - 1) / (512 / sizeof(int)) << std::endl;}return 0;
}