std :: deque :: push_back / front的复杂性要求 [英] Complexity requirements for std::deque::push_back/front
问题描述
由于几天前的这个问题，一些事情一直在告诉我关于 std :: deque :: push_back / push_front 与实际 std :: deque 。
上一个问题的结果是这些操作需要具有 O（1） 最坏情况下的复杂性。我验证了 c ++ 11 中的确如此：
复杂性：插入元素的复杂度是线性的，加上
的复杂度较小的距离到开始和结束的deque。在deque的开始或结束处插入单个
元素总是需要常量时间，
会导致单个调用T的构造函数。
这与 O（1）复杂性要求结合，通过 operator [] 等。
问题是实现不能严格满足这些要求。
对于 msvc 和 gcc code> std :: deque 实现是一个阻塞的数据结构，由一个指向（固定大小）块的动态数组组成，其中每个块存储多个数据元素。
在最坏的情况下， push_back / front等可能需要分配一个额外的块是 O（1）），但它也可能要求块指针的动态数组的大小调整 - 这不是很好，因为这是 O （m）其中 m 是块的数量，在一天结束时 O / code>。
显然，这仍然是摊销 O（1）复杂性， c $ c> m < n 它在实践中会很快。但是似乎有一个符合的问题吗？
另外，我看不到你如何设计一个严格满足<$ c $ push_back / front等和运算符[] 。你可以有一个链接的块指针列表，但这不会给你所需的 operator [] 行为。
在C ++ 11 FDIS中，我们可以看到：
23.2.3序列容器[sequence.reqmts]
16 / 表101列出了为某些类型的序列容器提供的操作，而不是其他类型的序列容器。实施应为容器列中显示的所有容器类型提供这些操作，并实现它们以便采用摊销的常量时间。
其中表101 命名为可选序列容器操作并列出 deque push_back 和 push_front 操作。
似乎更像是你引用段落中的一点点遗漏。或许值得一个缺陷报告？
请注意，对构造函数的单个调用仍然有效。
As a result of this question from a few days ago there are a few things that have been bugging me about the complexity requirements for std::deque::push_back/push_front vs the actual std::deque implementations out in the wild.
The upshot of the previous question was that these operations are required to have O(1) worst case complexity. I verified that this was indeed the case in 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.
This is combined with the O(1) complexity requirement for indexing, via operator[] etc.
The issue is that implementations don't strictly satisfy these requirements.
In terms of both msvc and gcc the std::deque implementation is a blocked data structure, consisting of a dynamic array of pointers to (fixed size) blocks, where each block stores a number of data elements.
In the worst case, push_back/front etc could require an extra block to be allocated (which is fine - fixed size allocation is O(1)), but it could also require that the dynamic array of block pointers be resized - this is not fine, since this is O(m) where m is the number of blocks, which at the end of the day is O(n).
Obviously this is still amortised O(1) complexity and since generally m << n it's going to be pretty fast in practice. But it seems there's an issue with conformance?
As a further point, I don't see how you can design a data structure that strictly satisfies both the O(1) complexity for both push_back/front etc and operator[]. You could have a linked-list of block pointers, but this doesn't give you the desired operator[] behaviour. Can it actually be done?
In the C++11 FDIS, we can read:
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.
Where Table 101 is named Optional sequence container operations and lists deque for the push_back and push_front operations.
Therefore, it seems more like a slight omission in the paragraph you cited. Perhaps worth a Defect Report ?
Note that the single call to a constructor still holds.
这篇关于std :: deque :: push_back / front的复杂性要求的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
