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

Question

由于几天前的这个问题,有一些事情一直困扰着我对于野外std::deque::push_back/push_front实际std::deque实施的复杂性要求.

上一个问题的结果是这些操作需要具有O(1)最差的案例复杂性.我确认这确实是这样的c++11:

从23.3.3.4 deque修饰符,参考insert,push/emplace前/后

复杂性:复杂性是插入元素数量的线性加上到双端队列开始和结束距离的较小者.在双端队列的开头或末尾插入单个元素总是需要恒定的时间并导致对T的构造函数的单个调用.

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

问题是实现并不严格满足这些要求.

在这两个方面msvc与gcc所述std::deque的实施是一个阻塞数据结构,由指针的动态阵列的至(固定大小)的块,其中每个块中存储有数量的数据元素.

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

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

作为进一步的点,我看不出你如何能设计一个数据结构,严格同时满足O(1)两个复杂性push_back/front etc和operator[].您可以拥有块指针的链接列表,但这并不能提供所需的operator[]行为.真的可以吗？

Answer 1

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

\n

\n

23.2.3 序列容器[sequence.reqmts]

\n

16/表 101 列出了为某些类型的序列容器提供的操作，但没有列出为其他类型的序列容器提供的操作。实现应为 \xe2\x80\x9ccontainer\xe2\x80\x9d 列中显示的所有容器类型提供这些操作，并应实现它们以便采用摊销常数时间。

\n

\n

其中表 101名为可选序列容器操作以及和操作deque的列表。push_backpush_front

\n

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

\n

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

\n