0

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.

Danh
  • 5,916
  • 7
  • 30
  • 45
Vanessa Larralde
  • 81
  • 1
  • 5
  • 1
    Pretty sure they’re both unreliable. Do this: https://stackoverflow.com/questions/3938838/erasing-from-a-stdvector-while-doing-a-for-each – Ry- Nov 23 '16 at 03:17
  • Why are they unreliable? I'd rather stick to my option if it's correct. However, I'm not sure why it would not be correct (other than the need to assign `i=vect.erase(i)` to prevent the iterator from being invalidated. – Vanessa Larralde Nov 23 '16 at 11:37

1 Answers1

4

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.

Danh
  • 5,916
  • 7
  • 30
  • 45
  • @Danh Not only by standard wording. Since vector storage is guaranteed to be contigious, iterators are often implemented as simple memory pointers to vector storage. If in result of element deletion, storage is shrinked (and, thus, reallocated), all existing iterators will turn into a mere dangling pointers. – Dmitry Nov 23 '16 at 04:06
  • 2
    @Dmitry It's not shrinked until `shrink_to_fit` is called – Danh Nov 23 '16 at 04:13
  • @Danh Oh, geez, didn't know that! I was under impression that vector manages it's storage both ways automatically. Gotta go make some corrections into my own code now. :) – Dmitry Nov 23 '16 at 04:30
  • And would that be fixed by just assigning `vect.erase(i)` to the iterator? This way: `i=vect.erase(i)` or would my code still be wrong after that? – Vanessa Larralde Nov 23 '16 at 11:14
  • @VanessaLarralde It will be ok then, but the complexity will be O(n^2) instead of O(n) of remove-and-erase idiom – Danh Nov 28 '16 at 04:12