c++11 - 为什么在 std::deque 的末尾或开头插入或删除元素的复杂性是常数 O(1)？

Question

根据 C++ standard std::deque 有点像

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

如果是这样，在末尾或开头插入或删除元素怎么可能是常数 O(1)？如果超过了向量的容量并且我们在末尾或开头插入了一些东西，就不能保证整个向量不会被重新分配，所以我们有 0(N/M) 实际上是 0(N)，不是吗？ (N 是双端队列的大小)。

Answer 1

If the capacity of the vector exceeded and we insert something at the end or beginning there is no guarantee the the entire vector is not reallocated, so we have 0(N/M) that actually is 0(N), isn't it? (N is the size of the deque).

是的，但不需要复制/移动元素来重新分配该向量，只需将指向数组的指针移动到新存储。

标准规定:

[container.requirements.general]
-2- All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.

因此，存在 N/M 个指针副本这一事实不计入 O(1) 复杂度要求。并且由于指针上的那些操作非常便宜，因此这些操作的性能在实践中不成问题。 deque需要为每插入的 M 个元素分配一个新页面，但它永远不需要重新分配现有页面并移动每个现有元素，因此它避免了对向量的最昂贵的操作，因此不需要向量的指数增长来使双端队列便宜。