• Advertisement
Sign in to follow this  

Best STL Container for my cause?

This topic is 2302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

I'm having a problem deciding which container would be best for me for my purposes.
I'm currently working on a particle engine using C++ and SDL's primitive shape functions, everything's working pretty good, and I've been using a vector so far, but when I get to around 700 particles, the game starts to give really big pauses between frames, tracing down using the console and cout messages brought me to the conclusion that the arson is the erasing method I use for outdated particles.

Particles on this engine have a certain uptime since creation, and once that is up, they are to be deleted like so:
for(unsigned int i = 0; i < parList.size(); ++i){
if(SDL_GetTicks() - parList.start >= (Uint32)parList[
i].time){
parList.erase(parList.begin()+i);
--i;
}
}


Problem is, the erase method of a vector is not random acess, to my understanding, and once the time comes for it to kick in, if the number of particles it should be deleting at one time is too big, it will hang the program(The noticable number this will start happening at is 40).
Trying to switch to a container that had better performance for erasing elements, I went back to a list, but then remembered that iterating through 700 objects on a list is even worse practice here.

I tried looking up a bit on Google, but actually defining this question with a sum of words isn't really simple and gave no useful results.

So I'm turning to the experts here in the question, which STL container is best suited for constant iteration of the container(With no need for random access) AND random element erasing with the best performance?

Which container is typically used to manage particles in other games?

Thanks alot for the help to come!

Share this post


Link to post
Share on other sites
Advertisement
vector is probably the best choice.

Instead of doing an erase, do a "swap and pop" - swap the item you want to remove with the last item in the vector, then decrease the vector's size by one. This will avoid a lot of unnecessary copying and such to preserve particle order. Another option is to use a pool - just keep all the particles you can possibly have in the vector all the time, and store a boolean flag on each one that indicates if it should be considered "live" or not.

Share this post


Link to post
Share on other sites
Oh? I thought that the actual official implementation of the erase method is the swap and pop thing, atleast that's what I recall seeing somewhere before, maybe I'm wrong.

As for the 2nd suggestion, this isn't really that advance an engine, I don't have possible particles or any particle pool at all, I just create them on the fly with a few user determined options that need to be processed at runtime to keep it generic, such as speed, color, creation time, etc. That would require a larger pool than the actual active particles most of the time, unless I'm misinterpreting the meaning of the pool term.

I'll try the swap and pop method and get back with an answer, thanks alot =)

Share this post


Link to post
Share on other sites
The standard requires that vector::erase() preserve order of elements, so it can't be swap-and-pop by default. Some implementations may do this (and therefore violate the contract), or offer additional functions like unordered_erase(), but these are generally speaking outside the realm of standard C++.

Share this post


Link to post
Share on other sites

Oh? I thought that the actual official implementation of the erase method is the swap and pop thing, atleast that's what I recall seeing somewhere before, maybe I'm wrong.

No, the vector keeps its elements in order. Swapping and popping would change the order of the elements. Erase doesn't swap and pop. But if you don't care too much about order, than swapping and popping is the more efficient solution.

[edit]

Aw snap, ninja'd

Share this post


Link to post
Share on other sites
I just tried it, and it works out fantastic!
Thank you very much, that has been a very useful tip =)

Also thanks for the tidbit about the workings of it, I'll make sure to keep it in mind. And no, with the particle vector I don't really need any order of the objects at all, so it works out great.

Thanks alot for the help.

Share this post


Link to post
Share on other sites
Hidden

I'm having a problem deciding which container would be best for me for my purposes.


I've been using a vector so far, but when I get to around 700 particles ... the erase method of a vector is not random acess, to my understanding, and once the time comes for it to kick in, if the number of particles it should be deleting at one time is too big, it will ...


Correct.

Good choice, a vector is the container you should generally choose by default until you have requirements that say not to.


Always remember the underlying data type of the container.

A std::vector is basically a fancy smart array. Erasing an item is slow since everything beyond it must be shifted forward. Erasing the way you are doing it is even worse since you cause multiple shifts.


Two containers that allow faster deletion from the middle are list (which does have some performance concerns for iteration) and deque (which is basically a list of vectors, it operates in pages). A list is effectively a linked list, which means you are constantly following pointers. On a PC with a big CPU cache this usually isn't a big issue. Those do introduce slower iteration, but depending on your usage pattern may be options.


You can still keep with the vector class with a few minor changes. That would be my recommendation.

One option would be to add a variable to the items marking it as active or inactive; only process active items. That way you never need to delete items from your array. That would be my first preference for a particle system.

Another option may be smarter about removal. Instead of deleting from the middle many times, instead do a single removal from the end. Swap your item from your current entry with the entry at end of the array, then note that the end has moved forward one slot. This will accumulate all your 'dead' items at the end of the array. Track that as the dead zone at the back of the vector. When you are done iterating through your list, use a single erase to get rid of the dead zone at the end of the vector.

If you choose the second option, there is already a built-in set of functions to help. The algortihm function "remove_if()" will do exactly that. It does have a higher performance cost because preserves order, if that is important to you. First call remove_if() to push the unused items to the end, and call erase() to remove them from the container.


Share this post


Link to post
Why is it "swap and pop" instead of "copy the last one on this one and pop"? I don't care what the popped element is...

Share this post


Link to post
Share on other sites

Why is it "swap and pop" instead of "copy the last one on this one and pop"? I don't care what the popped element is...

Because it rhymes :) But yeah,you're right. In reality, there's no sense in copying the element to the back of the array if you're just going to pop it.

Share this post


Link to post
Share on other sites

Why is it "swap and pop" instead of "copy the last one on this one and pop"? I don't care what the popped element is...
[/quote]
It is called swap and pop because you use std::swap to move the element to the end. For primitive/small/simple types the difference between a swap and a copy is probably negligible (but perhaps slightly slower - profile!). If you had a vector of long std::string instances, standard containers, or other complex types that specialise std::swap: then swapping and popping is clearly more efficient.

Share this post


Link to post
Share on other sites
Well, with C++11 and rvalue references you have move and pop.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement