Ahh, pointers! lol, didn't notice that.

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).

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<.