删除向量和双端队列中的项目的时间复杂度

Question

我已经读过,在a的末尾添加项目的时间复杂度std::vector是分摊的常量,并且在a的顶部和底部插入项目std::deque是常量.因为这两个容器都具有随机访问迭代器,因此访问任何索引处的元素是不变的.如果我有任何这些事实错误,请告诉我.我的问题是如果访问a中的元素std::vector或者std::deque是不变的那么为什么通过擦除O(n)去除元素的时间复杂度.这里的答案之一说明通过擦除元素是O(n).我知道擦除会删除起始迭代器和结束迭代器之间的元素,所以答案基本上意味着它O(n) 取决于两个迭代器之间的元素的数量,并且从任何索引中的vector/deque中删除单个元素将为零？

Answer 1

的事情是有点不同std::vector和std::deque,以及它们是用于C++ 98和C++ 11不同.

的std ::矢量

复杂性与std::vector::erase()擦除范围的长度和范围的末端与容器的末端之间的元素数量是线性的(因此从末尾擦除元素需要恒定的时间).

C++ 2003 [lib.vector.modifiers]读取:

iterator erase(iterator position);
iterator erase(iterator first, iterator last);`

...

复杂性:的析构函数T被调用的次数等于擦除的元件的数量的数量,但赋值运算符的T被称为的次数等于在向量元素的擦除元件后的数目的数目.

C++ 14草案N4140 [vector.modifiers]读取:

复杂性:的析构函数T被调用的次数等于擦除的元件的数量的数量,但该移动赋值运算符的T被称为的次数等于在向量元素的擦除元件后的数目的数目.

因此,您可以看到C++ 11/14实现通常更有效,因为它执行移动分配而不是复制分配,但复杂性保持不变.

的std ::双端队列

复杂度与std::deque::erase()擦除范围的长度和两个数字的最小值成线性关系:范围开始之前剩余元素的数量,以及范围结束后剩余元素的数量.因此,从开头或结束擦除元素需要恒定的时间.

C++ 2003 [lib.deque.modifiers]:

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

复杂性:对析构函数的调用次数与擦除的元素数相同,但对赋值运算符的调用次数最多等于擦除元素之前的元素数量和元素数量的最小值擦除后的元素.

C++ 14草案N4140 [deque.modifiers]/5:

复杂性:对析构函数的调用次数与擦除的元素数相同,但对赋值运算符的调用次数不超过擦除元素之前的元素数量和之后的元素数量中的较小者.擦除元素.

所以,它在C++ 98和C++ 11/14中是相同的,除了C++ 11可以在移动赋值和复制赋值之间进行选择(这里我看到标准中的一些不一致,因为措辞没有提到移动如此转让std::vector- 可能是另一个问题的原因).

还要注意措辞中的"最多"和"不再".这允许实现比线性更有效,但在实践中它们是线性的(DEMO).

Answer 2

擦除向量中的元素是 O(n)，因为一旦删除元素，您仍然需要移动所有连续元素以填充创建的间隙。如果一个向量有 n 个元素，那么在最坏的情况下你需要移动 n-1 个元素，因此复杂度是 O(n)。

Answer 3

删除元素确实O(n)不是因为要找到要删除的元素而要做的事情，而是由于您对之后的所有元素都必须做的事情。这些元素需要向下滑动以填充空白插槽。

因此，平均而言，“擦除”将占用向量中途大约一半的元素，因此您必须偏移大约一半的元素。因此O(n)。最好的情况是，删除最后一个元素-无需滑动。最坏的情况是，您擦除了第一个元素-然后必须移动所有其他元素。