Greetings, I am going to write an overhead 2D game, but with a fixed 3D camera. I had considered using ID3DXSprite, but it's strictly 2D, and doesn't support world coordinates. Anyway, I've written my own sprite engine that contains a dynamic vertex and index buffer. The player may call onBegin()/onEnd(), just like ID3DXSprite, and Draw(...) within them. Now, I have the system rendering just fine, however I've come accross an issue with sorting my quads by texture. Basically the system goes through the following steps for each Draw(...) call: 1) Create a CSpriteInstance object and fill in its parameters such as texture, world matrix, and color. Add this object to a list. Then, within the onEnd(...) function: 1) Sort the list by texture 1) Loop through each instance 2) while we're on the same texture, add a quad to the dynamic buffers. Otherwise, flush the buffer, and set the new texture. So, this implimentation runs quite fast, except when I try to sort the list. Instead of 60fps, it gets cut to 30fps, while drawing about 500 quads. I tried using std::list::sort(), but quickly found out what a terrible idea that is; Next I tried std::multimap or the data structure, and it works twice as fast as the std::list (30fps), but still didn't reach the unsorted 60fps. What's a more efficient (and preferably easy to code) method of accomplishing this task? Thanks

Hey,

I used std::sort(...) and the speed hit isn't nearly as much.
I think it'll be fine,
thanks.

I'm confused. If the sorting version of whatever isn't as fast as the unsorted, why are you sorting?

Hey, thanks Jacob Roman, I'll check out the code =D

Is that 30 fps in a release build? Did you try adjusting optimization settings?

You might want to try using a map(or hash table) of vectors, and doing something like TheMap[TextureID].push_back(ThisThingy)
You could even use the last few frames to know about how big each vector needs to be to help avoid unneeded allocations.
Using a list or map directly to store the items will likely result in the data being spread all over the place, which is very bad for cache coherency. Using a vector would be better, but you need things divided by the texture ID which means a map makes sense. Having a map that does the dividing and a vector that does the actual storing seems like a win-win situation, as long as you don't have too many texture IDs. If practically every object uses it's own texture, using a nested structure like this would just increase overhead.

Thanks guys, you've helped a ton. I'm considering using a map with vectors as Extrarius proposed.