What STL container to perform removal of elements in between?

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 Parti开发者_运维技巧cle from my own ParticleContainer
        }   
    }
}

---

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

---

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.

---

Assuming that you don't need direct indexing (operator[]) and you're just normally iterating over the containers, list sounds just fine. You can even use splice to move the list nodes in constant time with no memory allocation or deallocation.

---

Sounds like std::list is the way to go. This is assuming that you definitely want to iterate over the list while removing objects from the middle. Note that most other containers will invalidate iterators when you remove from the middle; std::list does not. Additional suggestions:

• If you care about space (a lot), you might try Boost.Intrusive
• If you're willing to use a nonstandard container, give slist (singly linked list; gcc supports this) a try -- it will save space, save you some (small) runtime cost when removing elements, since you're reducing the number of pointers that have to be updated. This is compared with a std::list, which is doubly linked.

---

I am not understanding entirely, but;

• a set of particle pointers could prove worthy of the task too. insertion log(n) removal log(n)

• if you are mostly iterating the locality might have a large impact (I am not sure how efficient stl lists are in this respect, but stl vectors are a certainly better at this) and it could be worth flagging instead of removing