std::vector::erase 的时间复杂度 [英] Time Complexity of std::vector::erase

问题描述

我找到了一种从 STL 向量中删除元素的方法我的值 此处:

I've found a way to remove an element from an STL vector my its value here:

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

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

Now I'd like to know how efficient this method is, meaning its time complexity in Big O notation.

推荐答案

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

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

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

In this case remove compacts the elements that differ from the value to be removed (value) in the beginning of the vector and returns the iterator to the first element after that range. Then erase removes the elements.

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

So this makes this operation O(n).

这篇关于std::vector::erase 的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！