   Orderless list in STL?
  I'm using this in my (2D) particle engine for maintaining lists of particles. Since the particle engine does not need to do any depth sorting, all I need from the iteration is to touch every particle in the list along the way. However, since particles will be dying and respawning frequently, I need a structure which has fast insertions and removals.At this point, linked lists might seem natural. However, since order doesn't matter, I thought that an array would be faster because of continuity and because O(1) time can be achieved if you simply swap with the last item and remove. Is there any STL structure which has this behavior? I currently do this by iterating through a vector using an index instead of a regular iterator because I run into all sorts of bounds errors when I use an iterator.   
Quote:Original post by Guru2012I'm using this in my (2D) particle engine for maintaining lists of particles. Since the particle engine does not need to do any depth sorting, all I need from the iteration is to touch every particle in the list along the way. However, since particles will be dying and respawning frequently, I need a structure which has fast insertions and removals.At this point, linked lists might seem natural. However, since order doesn't matter, I thought that an array would be faster because of continuity and because O(1) time can be achieved if you simply swap with the last item and remove. Is there any STL structure which has this behavior? I currently do this by iterating through a vector using an index instead of a regular iterator because I run into all sorts of bounds errors when I use an iterator.There are a couple of issues involved here, for example what exactly your container is storing and how particles are being managed in general. Could you provide some more info? For example:- Whether the container stores particle objects or (possibly smart) pointers to particle objects- How 'hefty' the particle class is- If pointers are being used, whether the particles are being repeatedly new'ed and deletedAnd anything else you think might be relevant.   ;Quote:Original post by Guru2012Is there any STL structure which has this behavior? I currently do this by iterating through a vector using an index instead of a regular iterator because I run into all sorts of bounds errors when I use an iterator.It seems to me that you're already using the best container for the job.The only thing that concerns me is these "bounds errors". Iterators wouldn't give errors unless there was a reason, and using indexes to avoid the warnings without knowing the cause of the warnings is a bit dangerous. Would you care to elaborate on the code that was causing the problems?   ;Quote:Original post by iMalcThe only thing that concerns me is these "bounds errors". Iterators wouldn't give errors unless there was a reasonSmells like iterator invalidation to me.   ;  Particles are defined as structs, which are kept in a global "pool." The container (the particle system) requests pointers to unused particles from the pool when creating new ones and returns dead and no longer used particles to the pool. The particle class itself contains the following code:class NPParticle{public:VEC2 current;VEC2 previous;bool treatAsLine;float radius;unsigned int typesMask;unsigned int bodyIndex;bool isDead;};struct Particle{    NPParticle p;    float energy;    VEC2 v;};The particle system's container stores pointers to the particles. The update routine merely iterates through each particle, decrements the energy and updates the positions. The NPParticle struct is used because NPParticle is the data container my collision detection uses. Particle contains that and additional information the particle system itself needs.What I'm looking for is something which can exhibit the behavior here:0|1|2|3|4|5Remove at index 2:0|1|5|3|4I recognize that my design choice with NPParticle is not ideal. This was my first shot at collision detection, and at this point I feel that I would rather push on and finish this project than go back and spend more time on the collision detection, on which I have already spent months.   ;Quote:Original post by iMalcThe only thing that concerns me is these "bounds errors". Iterators wouldn't give errors unless there was a reason, and using indexes to avoid the warnings without knowing the cause of the warnings is a bit dangerous. Would you care to elaborate on the code that was causing the problems?Here's what I was doing when I got the errors:std::vector<Particle*> particles;...for ( std::vector<Particle*>::iterator i = particles.begin(); i != particles.end(); ++i ){    if ( ParticleIsDead(*i) )    {   particlePool->Free( *i );   *i = particles.back();   particles.pop_back();   --i; // because erasing means you have to iterate over the same spot    }    else    {   // update code...    }}Debugging showed that the problem was when the very first particle in the list was deleted, which meant that i was at 0 when --i was called, leaving an index of -1 which is invalid. At the beginning of the next iteration, ++i would supposedly set i back to 0, so that the end state would still be valid.I tried to fix this by using an integer for i instead, since an integer, unlike an iterator, is allowed to be an invalid index temporarily (in the moment between --i and ++i). The resulting code looks like this:std::vector<Particle*> particles;...Particle* tempParticlePtr;for ( int i = 0; i < particles.size(); ++i ){    tempParticlePtr = particles;    if ( ParticleIsDead( tempParticlePtr ) )    {   particlePool->Free( tempParticlePtr );   particles = particles.back();   particles.pop_back();   --i; // because erasing means you have to iterate over the same spot    }    else    {   // update code...    }}Which does the same thing. If there are errors in my code, it's because I adapted the code to remove some of the typenames which would have made this snippet more confusing.   ;  I'm not a c++ pro, but based on your description it seems a std::list<> is not an unreasonable choice. I also agree with the above poster that although accessing by index is certainly an option for vectors, you shouldn't do so just to sweep incorrect iterator behavior under the rug; the latter is most likely a sign that your iterator code is incorrect and needs to be fixed.If for some reason you prefer to use a vector, since you're only storing raw pointers, the 'swap and pop' solution might also be a reasonable option.   ;   particles.pop_back();   --i; // because erasing means you have to iterate over the same spotThat's going to be a problem when you erase the first particle in the container.I suggest:std::vector<Particle*>::iterator i = particles.begin();while( i != particles.end() ){    if ( ParticleIsDead(*i) )    {   particlePool->Free( *i );   *i = particles.back();   particles.pop_back();    }    else    {   // update code...   ++i;    }};  Sweet. That works. I wonder why I never thought of that.   ;Quote:Original post by Guru2012Sweet. That works. I wonder why I never thought of that.Because you haven't seen (roughly) the same problem posted here 200 times? [grin]In a similar vein, check out the return value of container.erase(). Same kind of deal.   