Vector gets iterated more times than size()

Question

I've got this piece of code:

for (std::vector<Marker>::iterator it = markers.begin(); it != markers.end(); ++it) {
    if (it->getDots().size() < 3) {
        markers.erase(it);
    }
}

In one of test inputs (the app does image analysis) I get a segfault. I tried to debug the code (to no avail) and noticed one thing. When asking gdb to p markers.size() i receive $9 = 3. So I would expect the loop to iterate three times, but surprisingly it does it (at least) 5 times. In fifth iteration there's a segfault. What I also noticed is that it's not the dereference of *it (here it->) that causes the error. It's specifically it->getDots(), which is a simple getter.

I write in C++ very rarely, so it might be some simple mistake, but neither my debugging, nor googling brought any solution. Could you help?

I'd like to emphasize, that on various different inputs (slightly different images) this function works properly, so it's even harder for me to trace the bug down.

You are a victim of [iterator invalidation](http://stackoverflow.com/questions/3747691/stdvector-iterator-invalidation). — Mahesh, Aug 10 '13 at 18:27
Can't believe there are so many examples on the internet about iterator operations, like "iterator->doSomething()", but almost nobody includes a warning about this special situation, which could be quite common, as removing things from a collection seems quite a basic operation. But also my bad, I should've read the documentation more carefully. Thank you guys! — Wojtek, Aug 10 '13 at 18:46

score 6 · Accepted Answer · answered Aug 10 '13 at 18:28

vector::erase invalidates all iterators pointing to the element being erased, and all elements that follow. So it becomes invalid, and ++it expression on the next loop iteration exhibits undefined behavior.

The best way to code this logic is with erase-remove idiom.

score 3 · Answer 2 · answered Aug 10 '13 at 18:27

3

The problem is this line:

markers.erase(it);

The iterator is invalidated. But that's okay, erase returns a valid iterator:

auto it = markers.begin();
while(it != markers.end())
{
    if(it->getDots().size() < 3) {
        it = markers.erase(it);
    }
    else ++it;
}

answered Aug 10 '13 at 18:27

nikolas

8,707
9
50
70

Did exactly this, because I like to keep things verbose, especially in C++ (in which I'm not an expert). It may be a bit more time consuming (for the processor), but my vectors are at most 9 elements, so not too much performance impact. – Wojtek Aug 10 '13 at 18:41

Mats Petersson · Answer 3 · 2013-08-10T18:30:07.327

2

You need to update it when you erase:

it = markers.erase(it);

since erase will "change" the vector, and your current it is no longer valid (and only do it++ if when you didn't erase it).

However, the more common way to do this is to use this type of construction:

markers.erase(std::remove(markers.begin(), markers.end(), number_in), markers.end());

edited Aug 10 '13 at 18:30

answered Aug 10 '13 at 18:26

Mats Petersson

126,704
14
140
227

Unless he has C++ (and can use lambda), this requires that he define a separate function or functional object for his condition (and use `remove-if`). This may or may not be justified, depending on the rest of his application. (In my experience, if you need the test once, you'll usually need something similar elsewhere, and it's usually worth the effort to define the functional object.) Of course, if he has C++11, lambda solves the problem elegantly. – James Kanze Aug 10 '13 at 18:53

Vector gets iterated more times than size()

3 Answers3