Time Complexity of std::vector::erase

问题:

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());

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

回答1:

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

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.

So this makes this operation O(n).

回答2:

The C++11 standard specifies in [vector.modifiers]/4:

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

In particular, erasing elements at the end is quite cheap since all that is done is destroying the elements to be erased, so the time complexity of the erase-call should be linear in terms of the number of occurrences of value inside vec - which corresponds to Θ(n) in Big-Oh-Notation. The complexity of the whole expression is still linear since remove has linear complexity in terms of the length of the range it is applied to. If the size of vec is described by the variable m we have Θ(n + m) for the complete expression which equals O(m) (since n < m and m + n < 2m, O(2m) = O(m))

回答3:

It could be anything as the complexity of the destructures is unknown

But assuming it is constant then it will be O(n)

回答4:

O(N) since you are walking through each element of your vector.