Jump to content
  • Advertisement
Sign in to follow this  
DrValkyer

Sorting classes in STL lists?

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

I am using a STL linked list which uses a custom class as an element type. I was wondering that is it possible to sort those elements somehow using STL sort function? For example if I had this kind of class : class element_type { private: int type; int number; string text; public: element_type(int t, int n, string t) { type=t; number=n; text=t; } }; Then I add some elements to the list : list<element_type*> class_list; class_list.push_back(new element_type(2,555,"The neighbour of the Beast")); class_list.push_back(new element_type(1,666,"The Beast")); class_list.push_back(new element_type(3,777,"The yet another neighbour of the Beast")); Finaly lets sort the list : class_list.sort(); So what happens?? Actually nothing, I think. So is it possible to use this sort function? For example to sort these elements according their type variable (1,2,3), or do I have to make a custom sort function?

Share this post


Link to post
Share on other sites
Advertisement
Hmm, I think the original std::sort() should not work with linked lists. That's why linked lists have their own sort(). Of course I am not sure about this.

Share this post


Link to post
Share on other sites
You need to create a custom sort function that sorts based on whatever criteria you need. Chances are the sort thats happening in your example is just sorting the pointers using the default(probably less than) comparison, which is pretty useless.

I think std::sort should work fine with lists. Usually when a container has its own member function for doing something like sorting it's because it can probably do it more efficiently by taking into account the design of the container that it's a part of. I always prefer the container version though, and list.sort() can take a predicate which is what you need to give it.

Share this post


Link to post
Share on other sites
I'd give you an example using the code you've provided, but I'm posting from my flatmate's computer and haven't coded C++ recently enough to be confident of giving you something compilable. Read the example from the article I linked - you can use std::sort.

Share this post


Link to post
Share on other sites
Quote:
Original post by jeff0
Isn't it easier to just overload the less-operator?!

http://www.msoe.edu/eecs/ce/courseinfo/stl/sort.htm


I believe that since his list is storing pointers just defining the operator isn't going to be enough. He needs to define a predicate that takes the element_type*, even if all it does is call the lessthan op on the dereferenced pointers.

Share this post


Link to post
Share on other sites
Your sort isn't working because it's comparing the pointers, not the objects pointed to.

std::list sort uses a different algorithm (probably merge sort which is O(nlog(n)) as opposed to quicksort etc. which are all O(n2)).

[Edited by - Nitage on May 9, 2006 8:31:25 AM]

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!