erase() 是在 std::vector 线性时间操作吗？

Question

第 http://www.cplusplus.com/reference/vector/vector/erase/ 页说

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

因此，如果我要删除一个元素，比方说，从某个长度为 n (n>j) 的向量中删除索引为 j 的元素 - 它是常量还是线性的 (O(n) )?

或者，如果我在 Jth 元素之后有 p 个元素，那么它将是有序的 O(p) - 我说得对吗？

Answer 1

根据您提供的link：

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving)

这意味着当从std::vector中删除N=1个元素时。在您的情况下，它将对等于 1 的析构函数进行 N 次调用。然后它将进行 M 移动操作，在您的情况下等于 (n-j-1) 。所以它是线性的而不是常数。

所以std::vector::erase的复杂度是：O(Deleted_Items_Count) + O(Moved_Items_Count).

你的情况：1*Destructor_Time + (n-j-1)*Moving_Time

为了在常数时间内从向量中删除项目，您可以从向量的尾部删除它们（例如std::vector::pop_back）

所以如果你想要一个不重要的排序的恒定时间擦除：

auto linear_erase=[](auto& v, const size_t index){
    std::swap(v[index], v.back());
    v.pop_back();
};

Answer 2

从向量中删除 N 个元素需要 O(N) 的时间复杂度，因为应用程序必须迭代 M 个元素，并调用每个元素的析构函数，然后复制其余元素到通过销毁已擦除元素而产生的间隙。

因此，如果我们有一个包含 N 个元素的向量，并且我们从范围 (p,q] 中删除元素，那么销毁范围将花费 O(q-p) 时间复杂度，您可以说是O(1)，因为p和q是常量。那么你将不得不 copy/move 范围 (q,N] 。因为 N-q 是线性的，所以时间复杂度是 O(N).

一起我们得到 O(N) + O(1) = O(N)

当然，如果你删除一个以数组末尾结束的范围，复杂度是O(1)，因为没有元素到copy/move。

Answer 3

我在SO上了解到，标准是最好的参考。

来自 23.3.11.1/1 [vector.overview]:

A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

因此，在这种情况下 erase 既不是常数也不是线性时间。
这主要取决于您正在执行的操作类型：

如果你在向量的末尾擦除，它是常数，
否则是线性的。

erase() 是在 std::vector 线性时间操作吗？

Is erase() in std::vector linear time operation?

c++

vector

erase