c++ - std::vector 中的 erase() 是线性时间操作吗？

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) 的 vector 中使用索引 j - 它是常量还是线性的( O(n))?

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

Answer 1

从 vector 中删除 N 元素将花费 O(N) 的时间复杂度，因为应用程序必须迭代 M 元素，并调用每个元素的析构函数，然后将其余元素复制到通过销毁已删除元素而创建的间隙中。

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

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

当然，如果删除以数组末尾结束的范围，复杂度为 O(1)，因为没有要复制/移动的元素。