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

Question

我读到将项目添加到 std::vector 末尾的时间复杂度是摊销常量，而在 std::deque 顶部和底部插入项目的时间复杂度是 constant.Since 这两个容器有一个随机访问迭代器，因此访问任何索引处的元素是常量。如果我有这些事实，请告诉我 wrong.My 问题是，如果访问 std::vector 或 std::deque 中的元素是常量，那么为什么通过擦除 O 删除元素的时间复杂度是(n).这里的答案之一 here 指出通过擦除删除元素是 O(n)。我知道 erase 删除了起始迭代器和结束迭代器之间的元素所以答案基本上意味着它的 O(n) 取决于两个迭代器之间的元素数以及从 [=18= 中删除单个元素] 在任何索引中都将为零？

Answer 1

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

Answer 2

删除元素确实是 O(n) 不是因为您必须做些什么才能找到要删除的元素，而是因为您必须对所有元素做些什么 after 它。这些元素需要向下滑动以填充空槽。

因此，平均而言，擦除将在矢量的一半处删除一个元素，因此您必须移动大约一半的元素。因此 O(n)。最好的情况是，您擦除最后一个元素 - 无需滑动。最坏的情况是，您擦除第一个元素 - 然后必须移动每个个其他元素。

Answer 3

std::vector 和 std::deque 有点不同，C++98 和 C++11 也不同。

std::vector

std::vector::erase() 的复杂度与擦除范围的长度和范围末尾与容器末尾之间的元素数量成线性关系（因此从末尾擦除一个元素需要常数时间）。

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

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

...

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

C++14 草案 N4140 [vector.modifiers] 内容为：

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

所以你看到 C++11/14 实现通常更有效，因为它执行移动赋值而不是复制赋值，但复杂度保持不变。

std::deque

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

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

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

Complexity: The number of calls to the destructor is the same as the number of elements erased, but the number of the calls to the assignment operator is at most equal to the minimum of the number of elements before the erased elements and the number of elements after the erased elements.

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

Complexity: The number of calls to the destructor is the same as the number of elements erased, but the number of calls to the assignment operator is no more than the lesser of the number of elements before the erased elements and the number of elements after the erased elements.

因此，在 C++98 和 C++11/14 中也是一样的，除了 C++11 可以在移动赋值和复制赋值之间进行选择（这里我看到标准中有些不一致，因为措辞没有提到像 std::vector 这样的移动分配 - 可能是另一个问题的原因）。

另请注意措辞中的 "at most" 和 "no more"。这允许实现比线性更有效，尽管实际上它们是线性的 (DEMO)。

Answer 4

通过这种方式时间复杂度=范围长度+移位长度(n - 范围结束)

    vector<int> it = (vector<int>::iterator) &vec[pos];
    vec.erase(it, it+length);

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

Time complexity of removing items in vectors and deque

c++

vector

deque

c++98

std::vector

std::deque