为什么在 std::deque 末尾或开头插入或删除元素的复杂度是常量 O(1)？

Question

根据C++ 标准std::deque 是这样的

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

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

Answer 1

如果超出向量的容量并且我们在末尾或开头插入一些内容，则不能保证整个向量不会被重新分配，所以我们有 0(N/M) 实际上是 0(N)，不是吗？（N 是双端队列的大小）。

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

标准规定：

[container.requirements.general]
-2- 本条款中的所有复杂性要求仅根据所包含对象的操作数量来说明。

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