possible inconsistency in std::vector while erasing an element

Question

while debugging a vector, I see an inconsistency. Assume the following code which tries to remove an entry from a vector which has only one element

#include <iostream>
#include <vector>
std::vector<int> v;
void myremove(int);
int main()
{
  v.push_back(10); 
  std::cout << "10 pushed back\n";
  myremove(10);
  std::cout << "done :)\n";
  return 0;
}

void myremove( int a )
{
  std::vector<int>::iterator it = v.begin();
  int counter = 0;
  for ( ; it != v.end(); it++ ) {
    std::cout << "iterating for " << counter << " times and vector size is " << v.size() << "\n";
    if ( a == (*it) ) {
      v.erase(it);
      std::cout << "removed " << a << "\n";
    }
    ++counter; 
  }
}

This is what I see in the output:

 $ g++ test.cpp 
 $ ./a.out | more
 10 pushed back
 iterating for 0 times and vector size is 1
 removed 10
 iterating for 1 times and vector size is 0
 iterating for 2 times and vector size is 0
 iterating for 3 times and vector size is 0
 iterating for 4 times and vector size is 0
 iterating for 5 times and vector size is 0
 iterating for 6 times and vector size is 0
 ....
 ....
 iterating for 33790 times and vector size is 0
 Segmentation fault

What I understand is that when the element is removed the size will become 0, however the iterator moves one step and still it tries to reach the end but he doesn't know that he has already passed the end point.

Can someone explain more what is going on and how to avoid that?

http://stackoverflow.com/questions/8597240/how-to-delete-an-element-from-a-vector-while-looping-over-it — themel, Apr 12 '13 at 14:23

hmjd · Answer 1 · 2013-04-12T14:29:31.293

6

After the call to erase() the iterator it is invalidated:

Iterators and references to the erased elements and to the elements between them and the end of the container are invalidated.

Set it to the return value of erase() instead and only increment if no removal occured:

while (it != v.end())
{
    if ( a == (*it) )
    {
        it = v.erase(it);
        std::cout << "removed " << a << "\n";
    }
    else
    {
        ++it;
    }
}

where the return value of erase() is:

iterator following the last removed element.

Instead of hand coding a loop to erase elements you could use std::remove_if() instead:

v.erase(std::remove_if(v.begin(),
                       v.end(),
                       [](const int i) { return i == 10; }),
        v.end());

edited Apr 12 '13 at 14:29

answered Apr 12 '13 at 14:21

hmjd

120,187
20
207
252

Have you test that? Still I get the same output – mahmood Apr 12 '13 at 14:25
"Set it to the return value of erase() instead" - and compare `it` and `v.end()` just after it, otherwise you may increment iterator, pointed to the end of the vector. – awesoon Apr 12 '13 at 14:25

score 4 · Accepted Answer · 2013-04-12T18:13:14.227

4

When you erase

v.erase(it);

your iterator is not valid anymore. You have to use the returned iterator from erase. Erase gives you an iterator pointing to the element that followed the element erased by the call. And you have to break the loop if you erased the last element before the loop increments it.

it = v.erase(it);
if(it == v.end())
    break;

Suggestion: you can go ahead and change the for loop to a while loop. And increment the iterator explicitly (i.e. only when you have not erased anything. If you have erased the iterator is kind of incremented already).

Like this

while(it != v.end()) {
    if ( a == (*it) ) 
      it = v.erase(it);
    else
      ++it; 
}

edited Apr 12 '13 at 18:13

answered Apr 12 '13 at 14:21

Have you test that? Still I get the same output – mahmood Apr 12 '13 at 14:25
@mahmood I have fixed it. take a look. – Apr 12 '13 at 14:29
Micro-optimization: use `++it` instead of `it++`. – Mr.C64 Apr 12 '13 at 18:10

score 0 · Answer 3 · answered Apr 12 '13 at 14:21

0

Every insert and erase invalidates all iterators for the container. The methods return the ONLY valid iterator after inserting/erasing.

answered Apr 12 '13 at 14:21

Danstahr

4,190
22
38

No. Erase only invalidates iterators starting at the point of erasure to the end. And insert only invalidates all iterators if the new size is greater than the current capacity. Otherwise only iterators starting from the point of insertion are invalidated. – Benjamin Lindley Apr 12 '13 at 14:25
And what about containers that aren't sorted, such as unordered_set and unordered_map? In general, you never know if the previous iterator is valid or not and therefore you should always throw other iterators away and use the returned one. – Danstahr Apr 12 '13 at 14:28
That's a fine policy. My only point is that the statement in your answer is wrong. The standard makes certain guarantees about when iterators are invalidated, and your statement contradicts those guarantees. – Benjamin Lindley Apr 12 '13 at 14:33
You're right, our lecture slides lie. However, behavior of the iterators depend a lot on the container. For instance, list iterators aren't invalidated at all. – Danstahr Apr 12 '13 at 14:39
Yes, that is true. My comment only refers to `std::vector`, which this question is about. However, `std::vector`, of all the standard containers, has the strictest invalidation rules, which for the most part, it shares with `std::basic_string`. That is to say, for any other standard container besides vector or string, it is even less often the case that iterators are invalidated. And in some, as you pointed out, iterators are never invalidated (unless the object the iterator points to is actually destroyed). – Benjamin Lindley Apr 12 '13 at 14:47

score 0 · Answer 4 · answered Apr 12 '13 at 14:21

In the documentation of std::vector::erase :

Iterator validity

Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

You erasing an element in your loop (which depends on an iterator) is making everything berserk. that's pretty much it !

score 0 · Answer 5 · answered Apr 12 '13 at 14:23

0

When you call erase function the iterator is no more valid iterator, and when you increment the invalid iterator you will get spurious results.

answered Apr 12 '13 at 14:23

shofee

2,079
13
30

score 0 · Answer 6 · edited May 23 '17 at 12:23

The mistake is that you expect, after doing an erase on an iterator, that this iterator will still be in a consistent state. This is not the case, and your code illustrate precisely the situation when this occurs.

The semantic of your function is to remove all the elements of the vector equal to a. You can achieve the same result by filtering the vector. See that question for this point:

How to make std::vector from other vector with specific filter?

possible inconsistency in std::vector while erasing an element

6 Answers6