CODEWITHSUNDEEP
c++stdvector
Tomas Andrle
Tomas Andrle

Reputation: 13354

Is this a valid way of removing items from of std::vector?

Here's my code for updating a list of items in a vector and removing some of them:

std::vector<Particle*> particles;

...

int i = 0;
while ( i < particles.size() ) {
    bool shouldRemove = particles[ i ]->update();
    if ( shouldRemove ) {
        delete particles[ i ];
        particles[ i ] = particles.back();
        particles.pop_back();
    } else {
        i++;
    }
}

When I find an item that should be removed, I replace it with the last item from the vector to avoid potentially copying the rest of the backing array multiple times. Yes, I know it is premature optimization...

Is this a valid way of removing items from the vector? I get some occasional (!) crashes somewhere around this area but can't track them down precisely (LLDB fails to show me the line), so I would like to make sure this part is OK. Or is it... ?

UPDATE: I found the bug and indeed it was in another part of my code.

Upvotes: 4

Views: 204

Answers (4)

inkooboo
inkooboo

Reputation: 2944

Yes, this is a valid way. But if it is not a performance bottleneck in your program then it's better to use smart pointers to manage the lifetime of Particle objects.

Upvotes: 3

Phil H
Phil H

Reputation: 20141

You are iterating over an STL vector, so use iterators, it's what they're for.

std::vector<Particle*>::iterator particle = particles.begin();
while ( particle != particles.end() ) {
    bool shouldRemove = particle->update();
    if ( shouldRemove ) {
        particle = particles.remove(particle); //remove returns the new next particle
    } else {
        ++particle;
    }
}

Or, even better, use smart pointers and the erase/remove idiom. Remove_if itself does as you describe, moving old members to the back of the vector and returning an iterator pointing to the first non-valid member. Passing this and the vector's end() to erase allows erase to erase all the old members as they are in a contiguous block. In your scenario, you would have to delete each before calling erase:

auto deleteBegin = std::remove_if(
  particles.begin(), particles.end(),
  [](Particle* part){ return part->update();}));
for(auto deleteIt = deleteBegin; deleteIt != particles.end(); ++deleteIt)
    delete *deleteIt;
std::erase(deleteBegin, particles.end());

Or pre C++11:

bool ShouldDelete(Particle* part) {
     return part->update();
}

typedef vector<Particle*> ParticlesPtrVec;

ParticlesPtrVec::iterator deleteBegin = std::remove_if(
    particles.begin(), particles.end(), ShouldDelete);
for(ParticlesPtrVec::iterator deleteIt = deleteBegin; 
         deleteIt != particles.end(); ++deleteIt)
    delete *deleteIt;
std::erase(deleteBegin, particles.end());

Then test the whole code for performance and optimise wherever the actual bottlenecks are.

Upvotes: 1

Russ Freeman
Russ Freeman

Reputation: 1580

Take a look at std::remove_if.

Also, might be good to use a shared pointer as it may make life easier :-)

typedef std::shared_ptr< Particle > ParticlePtr;

auto newend = std::remove_if( particles.begin(), particles.end(), [](ParticlePtr p) {return p->update();} );
particles.erase( newend, particles.end() );

Upvotes: 1

Šimon T&#243;th
Šimon T&#243;th

Reputation: 36433

I don't see any direct issue in the code. You are probably having some issues with the actual pointers inside the vector.

Try running valgrind on your code to detect any hidden memory access problems, or switch to smart pointers.

Upvotes: 0

Related Questions