CODEWITHSUNDEEP
c++visual-studio
ilzxc
ilzxc

Reputation: 222

Manual control of iterator when erasing (and deleting) is necessary

In a particle system, once particles become old enough, they need to die. Since they are stored in an std::vector the approach that works rather well in XCode is:

for(std::vector<Particle*>::reverse_iterator iter = particles.rbegin(); iter != particles.rend(); ++iter) {  
    (*iter)->update();  
    if ( (*iter)->isDead() ) {
        delete (*iter);
        particles.erase( --iter.base() );  
    }  
}

After booting into Windows, and compiling in Visual Studio 2010, I found that it doesn't work: see here. As the answer itself states, this does not work for associative containers. What I find most frustrating here is that std::reverse_iterator and std::iterator behave differently:

I thought of using a forward std::iterator but iterating backwards, which is a terrible idea - but the very need for iterating backwards, really, is to ensure that the loop doesn't skip neighboring members of erased particles.

What makes sense to me, though, is not iterating if the .erase() call is made:

for( std::vector<Particle*>::iterator iter = particles.begin(); iter != particles.end(); ) {  
    (*iter)->update();  
    if ( (*iter)->isDead() ) {  
        delete (*iter);
        iter = particles.erase(iter);  
    } else {
        ++iter;
    }
}

This compiles, works, and doesn't seem to be a problem. The question, though, is:

Am I overlooking something that renders this a particularly stupid idea?

(I'm sure that iter will point at the correct next value by taking advantage of the .erase() function's return value, and it seems more readable to me than --iter.base() call.)

That parenthetical aside, a Russian saying that comes to mind is "One who's been burned on hot milk blows on cold water."

Upvotes: 3

Views: 187

Answers (3)

Christian Rau
Christian Rau

Reputation: 45948

In addition to the other answers (especially juanchopanza's), you can also do this with a single std::remove_if:

particles.erase(std::remove_if(particles.begin(), particles.end(), 
                               [](Particle *particle) -> bool {
                                   bool dead = p->isDead();
                                   if(dead)
                                       delete p;
                                   return dead;
                               }),
                particles.end());

(feel free to use a custom functor if C++11 lambdas are not available.)

This will work, since the possible duplication of an element will occur after the predicate was evaluated for it and it has already been deleted and therefore the predicate will still get invoked only once for each element in the vector and not for any possible duplicates. What the values after the new end iterator contain is completely irrelevant since we erase them afterwards and std::vector::erase doesn't try to delete anything at all.

EDIT: Another option of course would be to use smart pointers for the particles (in particular C++11's std::unique_ptrs or, if you are well read into the topic and perfectly understand what you are doing, std::shared_ptrs). This would at least free you from the need to manually manage their memory. In this case you could directly map the isDead method to the predicate function, without the need for a lambda at all (and you wouldn't need to modify the range inside the predicate, which is still a bit unidiomatic):

std::vector<std::unique_ptr<Particle>> particles;
...
particles.erase(std::remove_if(particles.begin(), particles.end(), 
                               std::mem_fn(&Particle::isDead)),
                particles.end());

EDIT: Though while we're at it, I cannot avoid asking you the question if those particles need to be allocated dynamically at all and if a std::vector<Particle> might in the end not work equally well (but it may very well be that you have a good reason to use pointers here).

Upvotes: 3

juanchopanza
juanchopanza

Reputation: 227418

I would use a two-pass solution:

1) delete elements and set to NULL:

void killParticle(Particle*& p)
{
  if ( p->isDead() ) {
    delete p;
    p = NULL;  
}  

std::for_each(particles.begin(), particles.end(), killParticle);

2) remove NULL elements using erase-remove idiom:

particles.erase(std::remove(particles.begin(), particles.end(), NULL), 
                particles.end());

Upvotes: 2

Xaqq
Xaqq

Reputation: 4386

Your second piece of code is good. This is also what I do when I need to remove elements from a list I'm iterating over.

AFAIK there's nothing wrong with "manual" control (ie, incrementing the iterator manually) when it's needed. And in your case, it seems needed.

I'm sure that iter will point at the correct next value by taking advantage of the .erase() function's return value, and it seems more readable to me than --iter.base() call.

I totally agree.

EDIT: As @n.m stated in comments, std::remove_if seems pretty adequate in your situation.

Upvotes: 3

Related Questions