What STL container to perform removal of elements in between?

Question

I need to pick a container to hold pointers to a type I defined (Particle). I'm using a pre-allocated Particle Object Pool ( which contain objects pre-allocated on an std::vector ).

My Particle emitters ask the Particle Pool for particles when they need to emit, ( in order to avoid in-game Particle allocation ). When a Particle expires, it is returned to the Particle Object Pool.

As you can see, as I iterate through my Particle Reference Container (need to pick one) in order to update it, I will have to check which particles have expired (lifetime <= 0.0) and return them back to the Particles Pool, the expired particles could be at any position in the container.

I've been thinking about using std::list, here's why:

A list (AFAIK) provides constant time insertion at the beginning , and constant time removal at any point ( assuming you have iterated to that point ).

Any suggestions or improvements to my system in order to better accomodate your container suggestions are welcome.

EDIT:

To explain myself a bit better:

The life time of the particles in an emitter is not exactly the same, it depends on a range, for example, 5.0 seconds +- (0.0 to 0.5). This is in order to give the particles a randomness element, and looks quite better than all in fixed time.

Algorithm Pseudo code:

    // Assume typedef std::container_type<Particle *> ParticleContainer

void update(float delta)
{   
    ParticleContainer::iterator particle = m_particles.begin();   

    for(; particle != m_particles.end(); ++particle)
    {
        updateParticle(*particle, delta);         //Update the particle

        if ( (*particle)->lifeTime <= 0.0 )
        {
            ParticlePool.markAsFree(*particle);   //Mark Particle as free in the object Pool
            m_particles.remove(*particle);        //Remove the Particle from my own ParticleContainer
        }   
    }
}

Answer 1

I don't entirely follow your algorithm, but std::vector is required to provide amortized constant time push_back. It may also have better locality of reference when iterating.

If order doesn't matter, removal of any item is also a constant time operation:

template <typename T>
void remove(std::vector<T> &v, size_t i)
{
    std::swap(v[i], v.back());
    v.pop_back();
}