标准说:
A deque is a sequence container that supports random access iterators (27.2.7). In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time.
然而,它也在同一个条款中说:
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: The copy constructor of type
vector<vector<int>>
has linear complexity, even though the complexity of copying each containedvector<int>
is itself linear. — end example ]
这是否意味着在
deque<int>
开头的插入被允许花费线性时间,只要它不会对已经在双端队列中的 int
和新的 int
执行超过恒定数量的操作对象被插入?例如,假设我们使用“大小为 K 个 vector 的 vector ”来实现双端队列。似乎我们在开头每插入 K 次,就必须在开头添加一个新的大小为 K 的 vector ,因此必须移动所有其他大小为 K 的 vector 。这意味着开始时插入的时间复杂度分摊为 O(N/K),其中 N 是元素总数,但 K 是常数,所以这只是 O(N)。但似乎这是标准允许的,因为移动大小为 K 的 vector 不会移动它的任何元素,并且“复杂性要求”是“仅根据操作数量来说明”对包含的
int
对象.标准真的允许这样做吗?或者我们应该将其解释为具有更严格的要求,即对所包含对象的恒定操作次数加上恒定的额外时间?
最佳答案
For example, suppose that we implement a deque using a "vector of size-K vectors".
那不会是一个有效的实现。在
vector
前面插入使容器中的所有指针/引用无效。 deque
要求在前插入时不使任何指针/引用无效。但让我们暂时忽略它。
But it seems that this is allowed by the Standard, because moving a size-K vector doesn't move any of its elements, and the "complexity requirements" are "stated solely in terms of the number of operations" on the contained int objects.
是的,那是允许的。确实,
deque
的真实实现与那并没有太大不同(尽管出于明显的原因,他们不使用 std::vector
本身)。 deque
的大纲实现是一个指向块的指针数组(前后都有增长空间),每个块包含最多 X 个项目以及指向下一个/上一个块的指针(使单元素迭代更快)。如果在前面或后面插入足够多的元素,则块指针数组必须增长。这将需要一个相对于
deque
中的项目数量呈线性时间的操作。 ,但实际上并不对项目本身进行操作,因此它不算数。该规范没有说明该操作的复杂性。如果没有此规定,我不确定
deque
的独特功能集是否存在。 (快速前/后插入和随机访问)将是可以实现的。
关于c++ - std::deque 实际上在开始时有恒定时间插入吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61089809/