std::vector::erase 的时间复杂度

Question

我找到了一种从 STL 向量中删除元素及其值的方法：

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

现在我想知道这个方法的效率如何，即它的时间复杂度（以 Big O 表示法）。

Answer 1

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

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

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