Delete and add elements to vector inside main loop

Question

I searched before but couldn't find any answers. I am somewhat new to c++, so hopefully this question won't be too stupid.

I am trying to add and remove elements in a vector, in my case populated with particles during a big update or drawing loop over all particles. For example remove some particles because they died, but also add a few other ones because one particle collided with an object and I want to show a small particle burst at the point of collision. I made this simple test code in a demo file to get to the bottom of the problem.

I think the problem is since I delete and add particles the iterator pointer becomes invalid. Deletion works, but when I add a few random ones I get a null pointer. the code below is somewhat verbose, I know I should use iterators with begin() and end() but I had the same problem with those, and played with the code a bit, trying more javascript array style looping because I am more familiar with that.

void testApp::drawParticles()
{

    int i=0;
    int max = particles.size();
    vector<Particle*>::iterator it = particles.begin();

    while ( i < max ) {

        Particle * p = particles[i];

        if ( ofRandom(1) > .9 ) {
            it = particles.erase(it);
            max = particles.size();
        } else {
            ofSetColor(255, 255, 0);
            ofCircle( p->x, p->y, p->z, 10);

            if ( ofRandom(1) < .1 ) addSomeNewOnes();
            i++;
            it++;
        }
    }


}

void testApp::addSomeNewOnes()
{
    int max = ofRandom(4);

    for ( int i=0; i<max; i++ ) {
        Particle * p = new Particle();
        p->x = ofRandom( -ofGetWidth()/2, ofGetWidth()/2 );
        p->y = ofRandom( -ofGetHeight()/2, ofGetHeight()/2 );
        p->z = ofRandom( -ofGetHeight()/2, ofGetHeight()/2 );
        particles.push_back( p );
    }
}

score 6 · Accepted Answer · answered Jun 15 '12 at 16:19

6

Every time you insert in to a vector, the iterators to it are potentially invalidated. You cannot do this:

if ( ofRandom(1) < .1 ) addSomeNewOnes();
it++

Because after the call to addSomeNewOnes(), it is invalid.

You can use the iterator returned by a call to vector::insert, but in your case that would mean re-engineering your code.

This is something you might want to do, anyway, as your code is a bit kludgy.

answered Jun 15 '12 at 16:19

John Dibling

99,718
31
186
324

1

I ended up just redoing my code and doing my insertion after the loop was done and not mess with the main loop iterators – Thomas Traum Jun 16 '12 at 11:14

scorpiodawg · Answer 2 · 2012-06-18T19:38:47.947

1

You could loop at it from the end, which should allow you to delete your current (since you're only deleting off of the end) and add new ones which get added to the end:

Vector<Particle*>::iterator it = particles.end();

while (iter != particles.begin()) {

    Particle * p = *iter;

    if ( ofRandom(1) > .9 ) {
        particles.erase(iter);
    } else {
        ofSetColor(255, 255, 0);
        ofCircle( p->x, p->y, p->z, 10);

        if ( ofRandom(1) < .1 ) addSomeNewOnes();
    }
    iter--;
}

If you are not adding, based on the info here, iterators in STL are stable so you should be able to iterate forwards and still be able to achieve the same result.

edited Jun 18 '12 at 19:38

answered Jun 15 '12 at 16:22

scorpiodawg

5,612
3
42
62

that one doesn't work for me... when i run this I still get a null pointer. my compiler also complains about the `while (*iter) ` as not being able to convert to bool. so if I use `while (*iter != particles.begin()` I am back to the old problem – Thomas Traum Jun 16 '12 at 11:05
I corrected the loop condition (it should be ``iter != particles.begin()`` and not ``*iter != particles.begin()``). Can you try now? Also, it would be helpful if you can add the compiler error/output to a [gist](https://gist.github.com/) or pastebin somewhere. – scorpiodawg Jun 18 '12 at 19:40

score 0 · Answer 3 · edited May 23 '17 at 10:32

0

Iterators are invalidated in some cases when the underlying data changes.

You'll have to break out of the loop and start again.

You should be able to do that by wrapping your whole drawParticles function in a while(notDone) loop, and setting notDone to true when you're done modifying the vector.

Here's another SO question with the rules: Iterator invalidation rules

edited May 23 '17 at 10:32

Community

1
1

answered Jun 15 '12 at 16:17

gcochard

11,408
1
26
41

score 0 · Answer 4 · answered Jun 15 '12 at 16:21

it = particles.erase(it);

will return an iterator pointing to the new location of the element following the one erased. If the one erased happens to be the last one, it will point to particles.end(). it++ on "end" is an error.

Also, if:

if ( ofRandom(1) < .1 ) addSomeNewOnes();

evaluates to true and addSomeNewOnes() is called, as others have said, that will also invalidate the iterator.

score 0 · Answer 5 · answered Jun 15 '12 at 16:26

Are you inserting and deleting at the location of the iterator? If so, insert and erase return iterators which will be valid, and you can use those. Something like:

std::vector<T>::iterator i = v.begin();
while ( i != v.end() ) {
    if ( someCondition ) {
        i = v.erase( i );
    } else {
        ++ i;
    }
}

is a more or less standard idiom.

For random insertions and deletions, you have to work with indexs, which you update according to the number of elements inserted or deleted, and whether the insertion or deletion was in front of or behind the current position.

score 0 · Answer 6 · answered Jun 15 '12 at 16:35

There's an easy way to make this work correctly without worrying about invalidation rules: just build a new vector for the next iteration.

typedef vector<Particle*> ParticleVector;

// modifies the particle vector passed in 
void testApp::drawParticles(ParticleVector &particles)
{
    ParticleVector next;
    next.reserve(particles.size()); // seems like a reasonable guess

    for (auto it = particles.begin(); it != particles.end(); ++it)
    {
        Particle *p = *it;

        if (ofRandom(1) > .9) {
            // don't copy to the next cycle
            delete p;
        } else {
            // copy to the next cycle
            next.push_back(p);

            ofSetColor(255, 255, 0);
            ofCircle(p->x, p->y, p->z, 10);

            if (ofRandom(1) < .1)
                addSomeNewOnesTo(next);
        }
    }
    particles.swap(next);
}

Note how much easier it is to refactor like this when you're not using globals, btw.

void testApp::addSomeNewOnesTo(ParticleVector &particles)
{
    int max = ofRandom(4);

    for ( int i=0; i<max; i++ ) {
        Particle * p = new Particle();
        p->x = ofRandom( -ofGetWidth()/2, ofGetWidth()/2 );
        p->y = ofRandom( -ofGetHeight()/2, ofGetHeight()/2 );
        p->z = ofRandom( -ofGetHeight()/2, ofGetHeight()/2 );
        particles.push_back( p );
    }
}

score 0 · Answer 7 · answered Jun 15 '12 at 16:40

0

On another note : Isn't there a memory leak in your implementation? You are using

vector<Particle*>  particles

and also using particles.erase(). Wont that just delete your pointer to Particle,and not created object?

answered Jun 15 '12 at 16:40

Arvind

466
3
9

Delete and add elements to vector inside main loop

7 Answers7