Ok, this may sound a bit stupid but how do I sort a bunch of particles stored in a STL list? I have the distance to the viewer which I calculate during frustum culling, so that’s given. The problem is the particles are stored in a “list” structure which does not have random itterator and therefore cannot be sorted with “sort” function. I could use “deque” or “vector” instead but that would present even more porblems because the particles are being constantly added and deleted. Does anyone know a good way to solve this? What’s the best data structure to use? Thanks.
You could walk the list and insert pointers to your particles in some sorted container, such as map<>.
Thanks, that seems to work.
If you refer to a particle system, there might be a possibility you don’t have to sort them to get ther correct result. A proper blendfunction might do the work for you.
You can sort a list using a variation of merge sort that is called straight radix sort.
You iterate through the list and put the particles in two lists, depending on one bit of the distance. Then you link the two lists together.
You do this for all bits of the distance from lowest order to highest order. When you have long integer distances you need only 32 iterations through the list to sort the particles.
This method is nearly as fast as merge sort and works on data that can only be accessed sequentially (like lists or tapes).