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();
}

Answer 2

Why not use a priority queue? That way you won't have to iterate over all active particles.

edit: on second thought: I'm not so sure this would actually work, depending on your algorithm (which I admittedly didn't completely understand.) If you are changing that lifetime-value while the entries are in the container, a queue might not work at all.

If you, however, don't change that value (e.g. you set the time the particles expire when inserting them, and then just check the first entry against the current time) I still think this is your best option. (Please note that the priority queue is just an adapter that uses std::vector internally by default.)

edit2: regarding your edit. I would suggest to not store a "lifetime" value with each particle (which gets constantly decreased until it is not positive anymore), but instead store a timestamp that represents when the particle should be removed. When initializing the particle, just calculate when the particle expires (by adding your random "lifetime" to the current time). This value would not change over the lifetime of your particle. When determining whether to remove a particle, just check if the current time is larger than the expiration timestamp.