CODEWITHSUNDEEP
c++c++11erase
Vanessa Larralde
Vanessa Larralde

Reputation: 81

c++11: Erase multiple occurrences from vector. Which is best practice?

I understand that erase moves the iterator forward automatically, so when removing multiple occurrences I need to avoid this so I can compare contiguous elements. That's why I usually do:

auto i = vect.begin();
while (i!=vect.end())
   if (*i==someValue)
        vect.erase(i);
   else
      ++i;

But I was wondering if I could also do it with a for loop, like this:

for (auto i=vec.begin(); i!=vec.end(); ++i)
   if (*i==someValue){
      vec.erase(i);
      --i;
}

The --i part looks a bit weird but it works. Would that be bad practice? Bad code? Be prone to errors? Or it's just right to use either option?

Thanks.

Upvotes: 0

Views: 849

Answers (1)

Danh
Danh

Reputation: 6016

Use Remove and Erase idiom:

auto new_end = std::remove(v.begin(), v.end(), some_value);
v.erase(new_end, v.end());

That above code has complexity of O(n) and it can be executed in parallel if there're no data race from C++17 with 

template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt remove( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, const T& value );

or with parallelism TS

Your code has a problem because from vector.modifiers#3

Effects: Invalidates iterators and references at or after the point of the erase

The standard said that iterator is invalidated

However, in reality, most of implementations keep the iterator point to the old node, which is now the end if it was the last element or the next element, then your code has complexity of O(n2) because it will loop n times and take n more for shift the data. It also can't be executed in parallel.

Upvotes: 4

Related Questions