• Advertisement
Sign in to follow this  

Sorting classes in STL lists?

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


In this case: no, because the list contains pointers. Anyway, a functor is not difficult to write (and contrary to a function pointer, will probably be inlined).
class element_type 
{
public:
struct less_than_comparator : public std::binary_function<element_type*,element_type*,bool>
{
result_type operator(first_argument_type v0, second_argument_type v1)
{
// return something equivalent to v0 < v1
}
};
};

std::list<element_type*> list;
// fill list
list.sort(element_type::less_than_comparator());


HTH,

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel Deloget
Quote:
Original post by Nitage
std::list sort uses a different algorithm (probably merge sort which is O(nlog(n)) as opposed to quicksort etc. which are all O(n)).


Quicksort is O(nlogn) to O(n2)


Quicksort can only achieve O(nlogn) for random access containers. Quicksort is O(n2) for std::lists, or any other sequential access container (if you sort in place - obviously you can copy the whole container to a vector, then sort, but that might be very slow - or even impossible for large data sets).

Share this post


Link to post
Share on other sites
std::deque or std::vectors are often better than std::lists if you are aiming to do things like sorting on your data.

Next, std::sort runs fastest with functors instead of functions.

Boost and the STL have many helper templates and functions. If you wanted to roll your own:

template<typename less_functor>
struct deref_ptr_less {
less_functor l;
deref_ptr_less(less_functor l_):l(l_) {};
template<typename T, typename U>
bool operator()( T left, U right ) const {return l(*left, *right);};
};

struct default_less {
template<typename T, typename U>
bool operator()( T left, U right ) const {return left < right;};
};

template<typename less_functor>
deref_ptr_less<less_functor> deref_less( less_functor l ) {
return deref_ptr_less<less_functor>(l);
};

deref_ptr_less<default_less> deref_less() {
return default_less();
};


Now, your element_type will either have to override it's own operator<:

struct element_type {
// ...
bool operator<(element_type const& o) { /* ... */ };
};


or you will have to provide a custom functor:

struct custom_less {
bool operator()(const element_type& left, const element_type& right) const {
// ...
};
};


once that is done, and you are using deques or vectors, you can:


std::sort( myvec.begin(), myvec.end(), pointer_less( custom_less() ) );
// or, if you just want to call operator< on the elements:
std::sort( myvec.begin(), myvec.end(), pointer_less() );


Alternatively, I'm relatively sure that std::list.sort can accept a sorting functor. This would be:


mylist.sort( deref_less( custom_less() ) );
// or, if you just want to call operator< on the elements:
mylist.sort( deref_less() );


Lastly, as I mentioned, using boost or the STL can replace alot of the boilerplate code above.

With boost, the code can be reduced to:

#include <lambda/lambda.hpp>
// ...
mylist.sort( *_1 < *_2 );

in the case when you have overridden operator<.

Share this post


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

  • Advertisement