6

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
        }   
    }
}
Goles
  • 11,599
  • 22
  • 79
  • 140
  • 3
    For a sequential container, always start out with `std::vector`. Then profile, and if container operations are a problem, try another container. [Usually you will find yourself sticking with `std::vector`.](http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001) – sbi Mar 10 '11 at 19:34
  • The problem with the "constant time" and std::list is that the constant is large! With a std::vector the time is variable, but small. Your choice! :-) – Bo Persson Mar 10 '11 at 19:53

5 Answers5

13

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();
}
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • I think the correct term is _amortized constant time_, but, yeah, start out with `std::vector` and only change after profiling shows improvements when using another container. [However, I doubt you will find this often.](http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort/5057001#5057001) – sbi Mar 10 '11 at 19:35
  • 3
    Better would be to use `std::swap(v[i], v.back()); v.pop_back();`, because `swap` is non-throwing, constant time, and cheap (for all non-idiotic implementations of `swap`). – GManNickG Mar 10 '11 at 20:12
  • Hey there, I edited my post. What's the cost of resizing the vector on one element ?. Of course it's better than removing an element in between, but still, if I do it often, do you think the performance will suffer too much ? ( I'll have to profile though ) – Goles Mar 10 '11 at 20:15
  • @Mr.Gando, appending a single element takes amortized constant time. In a typical implementation, reallocation doubles the capacity of the vector so its only needed every time the number of elements doubles. – Fred Foo Mar 10 '11 at 20:24
  • Brilliant! I've been digging around for a quick, efficient (constant time) way to remove an element via random access. Thanks! – Joel Feb 23 '12 at 00:44
  • I think the OP wanted the ability to push on the front of the container as well as constant time erasure from the middle. I would use this solution on `std::deque` to get constant push_front. – emsr Apr 23 '13 at 18:36
  • @emsr: but if amortized constant time is good enough, then this will work, as long as iteration is done in reverse. – Fred Foo Apr 23 '13 at 19:01
5

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.

user634618
  • 3,573
  • 1
  • 24
  • 17
  • I edited my post, the lifetime value doesn't change, but it's not the same for all the particles. A particle life time does depend on a random "range" value, eg: 5.0 seconds +- range(0.0, 0.5) ( where range gives a random number between the given parameters ) – Goles Mar 10 '11 at 20:14
  • yes, but it seems you could determine the "expiration date" at insertion time, by just adding your (random) lifetime to the current time, and then store the result. (the expiration date doesn't change after being initialized until the particle is removed from the container). the priority queue would make sure all particles inside are weakly ordered, so you just have to pop entries until the top "expiration date" is in the future. – user634618 Mar 10 '11 at 20:25
0

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.

Mark B
  • 95,107
  • 10
  • 109
  • 188
  • Hey there, I edited my post, it would be great if you think your reply still applies :). – Goles Mar 10 '11 at 20:17
0

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.
phooji
  • 10,086
  • 2
  • 38
  • 45
0

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

Ronny Brendel
  • 4,777
  • 5
  • 35
  • 55