Archived

This topic is now archived and is closed to further replies.

Sorting std::list<>'s

This topic is 5004 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

Hi, I''ve got a list of Game Objects that I''d like to store, based on an ID, so all the objects of one type get drawn before all objects of another type (to lower texture changes). I''ve got an integer identifier member on my GameObject class, m_ObjectType. Now, the question I have is this : How do I sort my std::list according to this member variable. Do I need to write some sort of template comparator or something? And I should only need to sort on insertion, right? Thanks $£¥ We scratch our eternal itch A twentieth century bitch We are grateful for Our Iron Lung

Share this post


Link to post
Share on other sites
I'm not sure if I know what you mean, but you can use the sort() algorithm:
mylist.sort()

The less-than operator (<) must be overloaded to use it.

[edited by - Goldfish on April 3, 2004 12:16:23 PM]

Share this post


Link to post
Share on other sites
Will that work? Considering the fact that I'm storing a list of pointers, will it not attempt to sort the list by the pointer's value (the memory location of the object)?.

If I overload the < operator for my GameObject class, will it use this when attempting to sort the list, as opposed to the pointer?

I hope this is the way to sort lists of objects. If it is, this will be just another example of just how useful and logical I've found the STL to be.

I'll try that.

Thanks

$£¥

We scratch our eternal itch
A twentieth century bitch
We are grateful for
Our Iron Lung

[edited by - slyterence on April 3, 2004 12:51:33 PM]

Share this post


Link to post
Share on other sites
You can give the sort function a functor which is used to compare the objects. However, like you said, you want to sort on insert.

Can you use a vector instead? Then you can use lower_bound to perform an O(log(n)) sorted insert. With list it will be O(n).

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
You can give the sort function a functor which is used to compare the objects. However, like you said, you want to sort on insert.

Can you use a vector instead? Then you can use lower_bound to perform an O(log(n)) sorted insert. With list it will be O(n).

Well, the insert on the vector will be O(n)

You should look into a set, if you want to keep your elements sorted.

(edit: or map, if you want to access them by a key)

[edited by - sjelkjd on April 3, 2004 2:20:27 PM]

Share this post


Link to post
Share on other sites
Magmai : Yes, as far as I can see it is possible for me to use a vector. Currently I instantiate all instances of the game-objects at level-start (When the level loader parses the level file), so it''s not the end of the world if the vector has to regrow a couple of times at program start. I could even figure out how many objects I''m going to need and just reserve this amount of space.

A map is out, because I have more than one instantiation of a specific gameobject (all instances will have the same key), but I guess I could use a multimap - I''ve used a couple in other places in my game.

I have to consider removal time as well though, because when GameObjects (basically, enemy planes) get killed, I have to remove them from the container.

So basically : Which of set/map/list/vector is best suited to sorting objects based on some integer with the best possible speed compromise for insertion and removal (though speed isn''t a huge problem on insert, much more so on removal).

Also considering that I doubt I''ll (at present) have more than 40-100 objects in this list, not numbers in the 100 000''s.

And I''d still need to know how to use this lower_bound you mentioned...

Thanks for taking the time to reply.

$£¥

We scratch our eternal itch
A twentieth century bitch
We are grateful for
Our Iron Lung

Share this post


Link to post
Share on other sites