Vector erase function in for loop is not erasing vector of classes properly

Question

I have a simple for loop:

for (int i = 0; i < c.numparticles; i++)
{
    if ( labs((noncollision[i].getypos())) > 5000 )
    {
        noncollision.erase (noncollision.begin()+i);
    }
}

Where noncollision is a vector of class particle. In this specific example, any noncollision which has a ypos greater than 5000 should be erased. I have been working with a noncollision size of 6, of which 2 have ypos much greater than 5000. However, this for loop is only erasing one of them, completely ignoring the other. My suspicion is that because noncollision is a vector of classes, that this classes is somehow protected, or causes the array function to act differently? Here is my declaration for noncollision, and for particle:

vector<particle> noncollision;

class particle{
private:
int xpos;
int ypos;
int xvel;
int yvel;
bool jc; // Has the particle just collided?
public:
etc....
};

Could anyone explain why this is happening, and how to rectify it? Do I somehow need to set up an 'erase function' for the particle class?

Just think of what you are asking it to do, what happens when you `erase` an element with the indices into the container... — David Rodríguez - dribeas, Aug 06 '13 at 14:48

Lightness Races in Orbit · Accepted Answer · 2013-08-06T14:57:35.497

If you have two candidate elements next to each other (say, at i=5 and i=6), then you jump over the second, because you just erased the one at i=5... then the second becomes the new i=5 but you increment i to get i=6 on the next loop.

You need to fix your loop to properly support the fact that you're simultaneously removing elements from the same container over which you're iterating.

Typically you'd use actual iterators (rather than a counter i), and vector::erase conveniently returns a new iterator for you to use in the next iteration:

vector<particle>::iterator it = noncollision.begin(), end = noncollision.end();
for ( ; it != end; ) { // NB. no `++it` here!
    if (labs(it->getypos()) > 5000) {
       // erase this element, and get an iterator to the new next one
       it  = noncollision.erase(it);

       // the end's moved, too!
       end = noncollision.end();
    }
    else {
       // otherwise, and only otherwise, continue iterating as normal
       it++;
    }
}

However, quoting Joe Z:

Also, since erase can be O(N) in the size of a vector, you might (a) benchmark the loop using reverse iterators too, (b) consider copying the not-erased elements into a fresh vector as opposed to deleting elements out of the middle, or (c) using a list<> instead of a vector<> if deleting from the middle is a common operation.

Or, if you're lazy, you could also just reverse your iteration order, which preserves the sanctity of your counter i in this specific case:

for (int i = c.numparticles-1; i >= 0; i--) {
    if (labs(noncollision[i].getypos()) > 5000) {
        noncollision.erase(noncollision.begin()+i);
    }
}

Just be careful never to change i to an unsigned variable (and your compiler is probably warning you to do just that — i.e. to use size_t instead — if c.numparticles has a sensible type) because if you do, your loop will never end!

+1 Using iterators is a lot more c-plus-plus-ish than using `begin()+i` :-) — Sergey Kalinichenko, Aug 06 '13 at 14:41
Also, since `erase` can be O(N) in the size of a vector, you might (a) benchmark the loop using reverse iterators too, (b) consider copying the not-erased elements into a fresh vector as opposed to deleting elements out of the middle, or (c) using a `list<>` instead of a `vector<>` if deleting from the middle is a common operation. — Joe Z, Aug 06 '13 at 14:43
Hmmm.... `end` is invalidated on the first `erase()`, but that's easily overlooked. — SteveLove, Aug 06 '13 at 14:51

score 2 · Answer 2 · answered Aug 06 '13 at 14:37

However, this for loop is only erasing one of them, completely ignoring the other.

This is because you are going front to back. When your code erases an item at, say, index 6, the item that was previously at index 7 is at the index 6 now. However, the loop is going to skip index 6 after i++, thinking that it has already processed it.

If you go back-to-front, the problem will be fixed:

for (int i = c.numparticles-1; i >= 0; i--)
{
    if ( labs((noncollision[i].getypos())) > 5000 )
    {
        noncollision.erase (noncollision.begin()+i);
    }
}

SteveLove · Answer 3 · 2013-08-06T14:53:20.667

It looks like you're suffering from "Invalidated Iterator" syndrome, although in this case it's the index that's the problem.

Are the 2 elements you want to erase next to each other?

The problem is that erasing an element from a vector causes the remaining underlying elements to be copied to a new location (unless you erase the last element), and the number of elements in the vector is reduced by one.

Since you're using indexing into the vector, you're not falling foul of the first problem (which is iterators being invalidated), but:

you will never check the element immediately after the one you just erased
your indexing will spill off the end of the vector (undefined behaviour)

Modifying any sequence you're inspecting in the same loop is a bad idea. Have a look at remove_if for a better way. This algo puts all the matching elements at the end of the vector, and returns you an iterator to the first one that was moved, allowing you to remove them all in one go safely.

Vector erase function in for loop is not erasing vector of classes properly

3 Answers3

Linked