std::deque::push_back/front的复杂度要求

Question

由于几天前的这个问题，关于std::deque::push_back/push_front的复杂度要求和实际的std::deque实现一直困扰着我。

先前的问题表明，这些操作需要具有O(1)的最坏情况复杂度。 我验证了这在中确实是这样的：

来自23.3.3.4 deque modifiers，参考insert、push/emplace front/back

复杂性：复杂性与插入的元素数量成线性关系，加上到deque开头和结尾的距离中较小的一个。 在deque的开头或结尾插入单个元素始终需要恒定的时间，并导致对T的构造函数的单个调用。

这与通过operator[]等的索引的O(1)复杂度要求相结合。

问题在于实现并不严格符合这些要求。

在msvc和gcc方面，std::deque实现是一个阻塞数据结构，由指向（固定大小）块的动态数组的指针组成，其中每个块存储一定数量的数据元素。

在最坏情况下，push_back/front等操作可能需要分配额外的块（这是可以接受的-固定大小分配是O(1)），但也可能需要调整块指针的动态数组大小-这是不好的，因为这是O(m)，其中m是块数，最终是O(n)。

显然，这仍然是摊销的O(1)复杂度，并且由于通常m << n，因此在实践中速度会非常快。 但似乎符合性存在问题？

此外，我不明白如何设计一个数据结构，它严格满足push_back/front等和operator[]的O(1)复杂度要求。 您可以有一个块指针的链表，但这不能给您所需的operator[]行为。 它是否可以实现？

- Darren Engwirda

---

相关（但并未真正回答）：https://dev59.com/Nm015IYBdhLWcg3w9wl1 - Nate Kohl

@NateKohl：是的，完全正确——对于那个问题的答案似乎证实了你无法严格满足所有的复杂性要求... - Darren Engwirda

Answer 1

在C++11 FDIS中，我们可以读到：

23.2.3序列容器[sequence.reqmts]

16/ 表101列出了一些类型的序列容器提供的操作，而其他类型则没有。实现应为所有“容器”列中显示的容器类型提供这些操作，并应实现它们以 平摊常数时间 进行。

其中表101被命名为 “可选序列容器操作”，并且将deque用于push_back和push_front操作。

因此，在你引用的段落中似乎更像是一个轻微的遗漏。也许值得提交一个缺陷报告？

请注意，单个构造函数调用仍然保持不变。

- Matthieu M.

---

这个问题最近似乎引起了一些讨论，可以参考以下链接：https://dev59.com/c2oy5IYBdhLWcg3wUcf_#8628035 和 https://dev59.com/eGoy5IYBdhLWcg3wUcZL - Darren Engwirda

@DarrenEngwirda：感谢提供意见 :) 我认为真正的问题是没有人知道如何实现一个满足标准要求的 deque，只能近似处理... 而我也不知道。随机访问 / O(1) push / 保留引用三位一体对我来说太难以管理了，即使有分摊 O(1) push 的算法。 - Matthieu M.

这个答案中的标准参考有些误导，因为它并不是惟一限制复杂度的地方。按照同样的条款，可以看出索引std::vector仅需要花费摊销时间常量，但在其他地方也明确表示，对于任何单个实例都必须保持恒定时间。同样地，对于std::deque<T>::push_front，详细条目（在我的副本中为23.3.3.4:3）表示始终需要花费恒定时间，正如OP中引用的那样，这显然覆盖了23.2.3:16中所说的内容。 - Marc van Leeuwen

Answer 2

我怀疑块指针的重新分配是以几何递增的大小进行的 - 这是 std::vector 的常见技巧。我认为这在技术上是 O(log m)，但正如您所指出的，m << n，所以从实际意义上讲，这并不影响实际结果。

- Mark Ransom

---

我知道你的意思，但标准实际上并没有太多的灵活性，要求始终实现恒定时间。也许可以修订标准？ - Darren Engwirda

实际上，几何级数增长使其摊销为O(1)（就像vector一样）。 - Matthieu M.