(I've replaced the gt and lt signs with brackets in this post) How can I use the STL (list) sort functions to sort a list of pointers to objects (rather than sorting the pointers themselve, which is useless) ? I'm using (list) to store pointers to my sprite objects, and have overridden the sprite objects' (,),== and != operators, but all I can get (list).sort to do is sort the pointers. Here's the declaration I'm using for the list... list(CEntity *) m_pUnitList; If anyone could provide a small snippet to help me on my way I'd be grateful. What am I trying to do ? Basically I want to re-sort all screen objects based on their Y coordinate for a top-down style game. Thanks Edited by - gorgar on 7/24/00 10:34:29 PM Edited by - gorgar on 7/24/00 10:35:43 PM

First off, sorting a list is going to be slow. You may want to define your own wrapper to force all insertions to be "in place". or consider using a set. That being said, you need to define an operator that compares pointers by dereferencing them.

struct cmpCEntity {
bool operator()(const CEntity *a,const CEntity *b) const {
return ((*a) < (*b));
}
};

This will call your overloaded comparison operator, you can now pass this as a template param.

set m_pUnitList;

Note that now inserts and deletes are now logrithmic, but you were eating O(NlogN) with each sort so we''re still ahead. Iterators still work exactly the same as in list.

For a tile based game, consider dramatically reducing the number of hights that tiles may occupy and keeping each "level" in it''s own vector with another vector of pointers to these vectors. Each level vector can have 2D coords with the usual [z*width+x] scheme. Moving a tile from one level to the next (changing it''s height) just requires coping one entity (or pointer) from one vector to the other. It all depends on how many tiles you want to be able to stack.

oops, damm html

set(CEntity *,cmpCEntity) m_pUnitList;

replace ()''s with angle brakets.

I was pretty sure when I started that this whole approach was inefficient and could be done better, so let me pose this question instead...

What is the best approach to sorting a maximum of 64 sprites each frame, based on the Y position of each sprite ?

I assume that by Y you mean the height of the sprite, such that
two sprites that overlap on the screen must be drawn in order of
increasing Y. If no two sprites can have the same height, or you
don''t care I would just keep a single list of all sprites in
sorted order, swapping only when a sprite changes Y value. Note
that just using set on only 64 objects means that inserts and
deletes only take 5 "ops" and you could have 128 sprites for 6
"ops" so we don''t really care that much. Giving each sprite a
pointer to the highest sprite it occludes will speed things up a
bit, and scale to large numbers of sprites much better.

The other way of doing this is rather than have a strict
Y/Height, have several "priorities" of sprites. something along
the lines of Ground,Items,Dead_Critters,Critters,Flying. Our
Hero gets drawn at the Critters Priority, and when you kill a bat
the bat gets demoted from Flying to Dead_Critters.

That's a really interesting problem, and there are a couple of steps.

First of all, to sort the sprites at all, you'll have to have a comparison function. I assume the Sprite class has its y-coord as a non-public member. So you'll need to make a public function that specifies whether one sprite has a greater coordinate than another:

class Sprite{private:  int x, y; // coordinatespublic:  bool yLess (const Sprite& rhs) const  {    return y < rhs.y;  }  bool xLess (const Sprite& rhs) const  {    return x < rhs.x; // allows you to sort by x as well  }};  

Now, in order to use STL's sorting functions, you need to form a predicate, which was shown by a previous poster. I'll show it here with my new class functions:

class PSpriteYLessPred{public:  bool operator () (const Sprite* lhs, const Sprite* rhs) const  {    return lhs.yLess (rhs);  }};  

(note: I've never used anything other than a reference to a pointer here. If you start to get weird errors, use a reference to a pointer instead of the pointer as arguments. I assume this works because this is what the previous poster submitted).

It appears from your post that you have all of your sprites in a list. They should be kept in a list if you are keeping iterators around pointing to each sprite, and intend on deleting them using the iterators later. If not, you probably want a different kind of container.

Regardless, I'll assume they're in a list. You have two choices: use list::sort, which is a sort optimized for linked lists (but still not the best sort), or you can copy the pointers to a vector and sort them there. Experimentation is probably the only way to figure out which way is better, but I'll show both:

// sort the listspriteList.sort (PSpriteYLessPred);// copy to a vector & sort thatvector&ltSprite*> sortVec (spriteList.begin (), spriteList.end ());// note--I've never gotten that constructor to work, but I think// that's a Microsoft STL implementation bug.  The STL spec// says that should work.  If it doesn't, do this:vector&ltSprite*> sortVec (64);copy (spriteList.begin (), spriteList.end (), sortVec.begin ());// now sortsort (sortVec.begin (), sortVec.end (), PSpriteYLessPred); 

Kinda fast & loose with the code there, there might be a bug or two, but that's the idea. Good luck.

Edited by - Stoffel on July 25, 2000 1:32:24 PM

olp-fan, you have just stepped in one of the one of the big hazards of oop. Just because you can overload say [] does not mean that access will still be constant when you do list . Of course, you shouldn't add too much magic to operators, but you cannot always trust this. <br><br>In this case gorgar has already overloaded the comparisons for<br>his sprites(correctly, good use of op overloading). The problem<br>is, he had a list of pointers to these objects. There is no way<br>for a class to overload pointer comparison. This is one of the<br>reasons that STL provides a template param for a prefix class to<br>act as the comparitor. <br><br>Note that I originally suggested using set instead of list, as set is always sorted(it's usually some form of balanced tree). In this case the prefix class works fine. To perform a quicksort<br>(and have it work well) you need random access to the data to find your pivot. STL proviedes this for any class that can get away with random_access_iterators as it's begin() and end().<br><br>thus coping a list to a vector, and then sorting that would work.<br>you would be better off using vectors instead of lists for the whole thing in this case though. You don't need insertion, because you are going to reorder when you sort anyway.<br><br>Plus you will want to use a Radix sort in any event, as long as your key's are ints you can blow quicksort out of the water any day of the week. However, we only have ~64 objects to sort, so anything we do is going to be fast. set works, and has a worst case of 5 pointer traversals on insert/delete. <br><br>the seprate priority lists also works, is faster, and adds some extra structure to the game that might come in usefull later. The priority lists could also be vectors as we don't care about the order of sprites in each priority so you aren't chaising pointers like you are with list. it's also more memory efficient.<br> <br><br>Edited by - Grib on July 25, 2000 3:02:13 PM

olp-fan:
how do you decide what < means with a Sprite? If you look at my code, I gave xLess and yLess, because they''re both valid comparisons.

One of the dangers of operator overloading is that it can obfuscate code. If I have a string class, it''s obvious what < means (alphabetically before). If I have a time class, it''s obvious what < means (chronologically before). However, if I have a sprite class, or a vector class, or an imaginary number class, it is NOT obvious what < means. Therefore you shouldn''t overload operator < in these cases.

Well, I want to thank you all for the replies you''ve posted - I''ve got plenty to think about now, and plenty of things to try. I''m going to run some timing tests and see which approach performs better.
So much to do, so little time...