c++ - std::deque::push_back/front 的复杂性要求

Question

由于 this几天前的问题 关于 std::deque::push_back/push_front 的复杂性要求，有几件事一直困扰着我与实际 std::deque野外实现。

上一个问题的结果是这些操作需要有 O(1)最坏情况的复杂性。我在 c++11 中验证确实是这种情况。 :

from 23.3.3.4 deque modifiers, refering to insert, push/emplace front/back

Complexity: The complexity is linear in the number of elements inserted plus the lesser of the distances to the beginning and end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to a constructor of T.

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

问题在于实现并不严格满足这些要求。

就两者而言msvc和 gcc std::deque实现是一个 block 数据结构，由指向(固定大小) block 的动态指针数组组成，其中每个 block 存储多个数据元素。

在最坏的情况下，push_back/front etc可能需要分配一个额外的 block (这很好 - 固定大小分配是 O(1) )，但它也可能需要调整 block 指针的动态数组的大小 - 这不好，因为这是 O(m)其中 m是 block 的数量，在一天结束时是 O(n) .

显然这仍然是摊销 O(1)复杂性，因为通常 m << n它在实践中会非常快。但似乎存在一致性问题？

作为进一步的观点，我看不出如何设计一个严格满足 O(1) 的数据结构。两者的复杂性 push_back/front etc和 operator[] .你可以有一个 block 指针的链表，但这不会给你想要的 operator[]行为。真的可以吗？

Answer 1

在C++11 FDIS中，我们可以读取:

23.2.3 Sequence containers [sequence.reqmts]

16/ Table 101 lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.

其中 表 101 被命名为 可选序列容器操作 并列出 push_back 和 的 deque push_front 操作。

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

请注意，对构造函数的单个调用仍然有效。