C++中std::deque基于分段数组，如何实现队首插入O(1)时间复杂度？

std::deque的核心结构不是简单的分段数组堆叠，而是由中控数组（map） + 多个固定大小的缓冲区构成：

• 中控数组是一个动态数组，每个元素指向一段连续的内存缓冲区（每个缓冲区大小固定，比如默认存512个元素，具体大小由实现决定）。
• 队首、队尾分别通过指针/迭代器定位到对应缓冲区的有效元素位置，同时每个缓冲区会记录自身的有效元素范围（比如起始索引、结束索引）。

队首插入的O(1)复杂度分两种场景实现：

1. 当前首缓冲区仍有空闲空间
   如果队首指针还没到当前缓冲区的起始位置（即缓冲区前面还有未使用的槽位），直接在队首指针的前一个位置构造新元素，然后将队首指针前移一位即可。这一步仅涉及指针移动和元素构造，完全是O(1)操作，没有任何数据拷贝。

2. 当前首缓冲区已无空闲空间
   此时会分配一个新的固定大小缓冲区，将其地址添加到中控数组的头部。这里中控数组的扩容是**均摊O(1)**的：因为中控数组通常按倍数（比如2倍）扩容，每次扩容的代价会分摊到后续多次操作中，单次扩容的影响可以忽略。新缓冲区作为新的首缓冲区，直接将新元素放到缓冲区的对应空闲位置，调整队首指针指向这个新元素即可，同样不需要移动任何已有元素，核心操作仍是O(1)。

需要明确的是：std::deque的队首插入是**均摊O(1)**时间复杂度，并非最坏情况下每次都是O(1)，但由于中控数组扩容频率极低，实际使用中几乎每次插入都是O(1)。它完全不会出现"分段大小级别的耗时操作"——因为不需要移动现有缓冲区的元素，仅需新增缓冲区或调整指针，这也是它和普通手动实现的分段数组的本质区别。

内容的提问来源于stack exchange，提问作者Vartika Singh