为什么在std :: Deque常数O(1)的末尾或开始时插入或去除元素的复杂性

Question

根据c 标准std :: deque，

std::vector<std::array<T, M> *>

如果是这样，如何在末端或开始时插入或去除元素是恒定的O（1）？如果矢量的能力超过了，并且我们在最后插入了某些内容，则不能保证整个向量不是重新分配的，所以我们有0（n/m）实际上是0（n），不是吗？（n是Deque的大小）。

Answer 1

如果矢量的能力超过了，并且我们在末尾插入了某些内容，则不能保证整个向量不是重新分配的，因此我们有0（n/m）实际为0（n），isn't？（n是Deque的大小）。

是的，但是不需要复制/移动元素以重新分配该向量，只需要将阵列的指针移至新存储。

标准状态：

[Container.Requirentess.general]
-2-本条款中的所有复杂性要求仅根据包含对象的操作数量陈述。

因此，在O（1）复杂性要求中不计算指示器的N/M副本。而且，由于这些指针的操作非常便宜，因此这些操作的性能在实践中不是问题。deque需要为插入的每个M元素分配一个新页面，但是它绝对不需要重新分配现有页面并移动每个现有元素，因此它可以避免对向量上的最昂贵的操作，因此不需要向量的指数增长来使Deques廉价使Deques廉价降低。

Answer 2

通过从指针向外分配的中间来实现前面插入的摊销常数复杂性。

。

例如，如果我们有一个带有3个节点的Deque，则每个节点最多可容纳4个元素，我们可能会将其向量分配为8个指针：

[ nil, nil, nil, N1*, N2*, N3*, nil, nil ]

在这里N1和N3本身可能部分填充：

N1: [ nil, nil, nil, 1 ]
N2: [ 2, 3, 4, 5 ]
N3: [ 6, 7, nil, nil ]

当我们在Deque上push_front时，第一个N1填充在正面，然后将其他节点分配并添加到指针的向量中。一旦指针的向量在正面填充，任何其他push_front就会导致指数扩展，而在前面分配了其他空间：

[ N1*, N2*, N3*, N4*, N5*, N6*, nil, nil ]
  |                         `---------------------------------------
  `-----------------------------------v                             v
[ nil, nil, nil, nil, nil, nil, nil, N0*, N1*, N2*, N3*, N4*, N5*, N6*, nil, nil ]

此指数增长策略实现了deque::push_front和deque::push_back的O（1）摊销复杂性，其原因是vector::push_back具有O（1）摊销复杂性。