c++ - std::vector::erase 的时间复杂度

Question

我找到了一种方法，可以从 STL vector 中删除元素及其值 here :

vec.erase(remove(vec.begin(), vec.end(), value), vec.end());

现在我想知道这种方法的效率如何，这意味着它在大 O 表示法中的时间复杂度。

Answer 1

vec.erase(删除(vec.begin(), vec.end(), value), vec.end());

在这种情况下，remove 会压缩 vector 开头与要删除的值 (value) 不同的元素，并将迭代器返回到该范围之后的第一个元素。然后删除删除元素。

所以这使得这个操作复杂度为 O(n)。