std::deque 在队列前端插入时如何实现 O(1) 时间复杂度？

Question

C++中的

std::deque

内部使用了分段数组，那么在

deque

前面插入时如何保持O(1)的时间复杂度呢？

分段数组将大数组分解为较小的数组，但在分段数组的前面插入也可能是一项耗时的任务。我不确定

std::deque

如何保持 O(1) 时间。还是需要分段大小的时间？

Answer 1

按算法将元素添加到双端队列的前面是

O(1)

，如果您使用分段数组，请遵循伪

push_front

过程：

尝试将元素添加到段数组的前段，需要
```
O(constant) = O(1)
```
时间（移动或复制
```
push_front
```
的参数）。如果前段没有剩余空间，请继续步骤 2。
要在分段数组的前面插入一些内容，当第一个段已经满时，我们需要一个新段：分配新段，需要
```
O(constant) = O(1)
```
时间。继续步骤 3。
将新分配的段链接到段数组，
```
O(1)
```
一次，只是简单的链表链接操作。继续步骤 4。
将元素添加到新分配的段中，仍然是
```
O(1)
```
。

因此，这一切加起来就是

O(1)