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?

Answer 1

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!