std::deque::push_back/front 的复杂性要求 [英] Complexity requirements for std::deque::push_back/front

问题描述

由于几天前的这个问题，有关于 std::deque::push_back/push_front 与实际 std::deque 实现的复杂性要求的一些事情一直困扰着我.

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.

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

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:

来自 23.3.3.4 的双端队列修饰符，指的是插入、推送/放置前/后

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

复杂度:复杂度与插入的元素数加上到双端队列的开头和结尾的距离较小.插入单个双端队列开头或结尾的元素总是花费恒定的时间，并且导致对 T 的构造函数的一次调用.

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[] 等

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.

就 msvc 和 gcc 而言，std::deque 实现是一个阻塞的数据结构，由一个动态的指针数组组成到(固定大小)块，其中每个块存储许多数据元素.

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.

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

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).

显然这仍然是摊销的 O(1) 复杂性，因为通常 m <<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?

另外一点，我看不出如何设计一个严格满足 push_back/front 等 的 O(1) 复杂性的数据结构和 operator[].你可以有一个块指针的链表，但这并没有给你想要的 operator[] 行为.真的可以做到吗?

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?

推荐答案

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

In the C++11 FDIS, we can read:

23.2.3 序列容器 [sequence.reqmts]

16/ 表 101 列出了为某些类型的序列容器提供的操作，而不是为其他类型的容器提供的操作.实现应为容器"列中显示的所有容器类型提供这些操作，并应实现它们以占用摊销常数时间.

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.

其中Table 101 被命名为可选序列容器操作，并为push_back 和 列出dequepush_front 操作.

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屋！