sorting list of pointers

[Nenad Jalsovec]

using std::list;

struct Something{
Something( val ): value( val ){}
bool operator<( Something & s ){ return value < s.value; }
int value;
};

main(){
list< Something * > things;
things.pushBack( new Something( 10 ) );
things.pushBack( new Something( 20 ) );
things.sort();
}



How to force things.sort() to use Something:perator<( Something & )
instead of default operator< for pointers ?

 

[Rolf Magnus]

using std::list;

struct Something{
Something( val ): value( val ){}
bool operator<( Something & s ){ return value < s.value; }
int value;
};

main(){
list< Something * > things;
things.pushBack( new Something( 10 ) );
things.pushBack( new Something( 20 ) );
things.sort();
}



How to force things.sort() to use Something:perator<( Something & )
instead of default operator< for pointers ?

struct Something_ptr_cmp
{
bool operator(Something* lhs, Something* rhs)
{
return *lhs < *rhs;
}
};

//...

things.sort(Someting_ptr_cmp);

 

[Howard]

struct Something_ptr_cmp
{
bool operator(Something* lhs, Something* rhs)

Did you forget the < there, as in:

bool operator <(Something* lhs, Something* rhs)

 

[Rolf Magnus]

Did you forget the < there, as in:

No, I didn't. But I forgot extra parens. Should be:

bool operator()(Something* lhs, Something* rhs)

The idea is to have a comparison function object that can be
"called" (which means its operator() gets called) by the sort
algorithm.

 

[Nenad Jalsovec]

struct Something_ptr_cmp
{
bool operator(Something* lhs, Something* rhs)
{
return *lhs < *rhs;
}
};

//...

things.sort(Someting_ptr_cmp);

Yes, thanks. This works ok. My cpp reference book was missing void
list::sort( cmp_func_obj ). There was only void list::sort()
Here's complete thing without typos ( I hope )

#include <list>

using std::list

struct Something{
Something( int val ): value( val ){}
bool operator<( Something& s ){ return value < s.value; }
int value;
};

struct Something_ptr_cmp{
bool operator()( Something* lhs, Something* rhs){
return * lhs < * rhs;
}
};

main(){
list< Something* > things;
things.push_back( new Something( 10 ) );
things.push_back( new Something( 20 ) );
things.sort( Something_ptr_cmp() );
}

 

[Nenad Jalsovec]

Yes, thanks. This works ok. My cpp reference book was missing void
list::sort( cmp_func_obj ). There was only void list::sort()
Here's complete thing without typos ( I hope )

#include <list>

using std::list

struct Something{
Something( int val ): value( val ){}
bool operator<( Something& s ){ return value < s.value; }
int value;
};

struct Something_ptr_cmp{
bool operator()( Something* lhs, Something* rhs){
return * lhs < * rhs;
}
};

main(){
list< Something* > things;
things.push_back( new Something( 10 ) );
things.push_back( new Something( 20 ) );
things.sort( Something_ptr_cmp() );
}

Damn!
int main()

 

[John Harrison]

No, I didn't. But I forgot extra parens. Should be:

bool operator()(Something* lhs, Something* rhs)

The idea is to have a comparison function object that can be
"called" (which means its operator() gets called) by the sort
algorithm.

You also forgot const

bool operator()(Something* lhs, Something* rhs) const

john

 

[Rolf Magnus]

You also forgot const

bool operator()(Something* lhs, Something* rhs) const

Right, though I'm not sure whether that's acually needed. Btw: I also
forgot parens in the call to sort, should have been:

things.sort(Someting_ptr_cmp());

instead of:

things.sort(Someting_ptr_cmp);

Now you know why I don't like writing code on a piece of paper (as one
typically has to do in exams).

 

[Stanislaw Salik]

Looking for the most sophisticated way of sorting STL collections of
(smart)pointers (which was my new hobby for past few weeks), recently I
have encountered Boost Lambda library that really amazed me:
http://www.boost.org/libs/lambda/doc/index.html

The clue of lambda approach is that you dont have to provide a
comparator definition beyond a scope of your function. You just create
unnamed comparator object in place where it is used.

#include <list>
#include <boost/lambda/lambda.hpp>

using std::list;
using boost::lambda::_1;
using boost::lambda::_2;

struct Something{
Something( int val ): value( val ){}
bool operator<( Something& s ){ return value < s.value; }
int value;
};

int
main(){
list< Something* > things;
things.push_back( new Something( 10 ) );
things.push_back( new Something( 20 ) );
things.sort( *_1 < *_2 ); // Would you ever imagine
// something like that
// would ever compile?
return 0;
}

 

[Ron Natalie]

How to force things.sort() to use Something:perator<( Something & )
instead of default operator< for pointers ?

Hopefully, you know that operator<() is not well defined for pointers that are not pointing
into the same array.

 

[Rob Williscroft]

Ron Natalie wrote in in comp.lang.c++:

Hopefully, you know that operator<() is not well defined for pointers
that are not pointing into the same array.

However std::less< T * > is (20.3.3/8):

int
main()
{
list< Something * > things;
things.pushBack( new Something( 10 ) );
things.pushBack( new Something( 20 ) );
things.sort( std::less< Something * >() );
}

Rob.

 

[Ron Natalie]

However std::less< T * > is (20.3.3/8):

int
main()
{
list< Something * > things;
things.pushBack( new Something( 10 ) );
things.pushBack( new Something( 20 ) );
things.sort( std::less< Something * >() );
}

Unfortunately, the above code doesn't have well defined behavior, as I said.
Applying < to pointers only is well defined when the pointer values refer to
elements of the same array. In your case the pointers are two unrelated
values (different calls to new). It's quite legal that:

Something* a = new Something(10);
Something* b = new Something(20);

a < b ; // true
b < a; // also true.

This is going to spell havoc for sorting algorithms,

 

[Kai-Uwe Bux]

Unfortunately, the above code doesn't have well defined behavior, as I
said. Applying < to pointers only is well defined when the pointer values
refer to
elements of the same array. In your case the pointers are two unrelated
values (different calls to new). It's quite legal that:

Something* a = new Something(10);
Something* b = new Something(20);

a < b ; // true
b < a; // also true.

This is going to spell havoc for sorting algorithms,

From the standard:

[20.3.3/8] For templates *greater*, *less*, *greater_equal*, and
*less_equal*, the specializations for any pointer type yield a total order,
even if the built-in operators <, >, <=, >= do not.


I read this as a guarantee that

things.sort( std::less < Something* >() );

is well defined.


Best

Kai-Uwe Bux

 

[Rob Williscroft]

Ron Natalie wrote in in comp.lang.c++:

Unfortunately, the above code doesn't have well defined behavior,

Yes it does, the citation is above.

as I
said. Applying < to pointers only is well defined when the pointer
values refer to elements of the same array. In your case the
pointers are two unrelated values (different calls to new). It's
quite legal that:

Something* a = new Something(10);
Something* b = new Something(20);

a < b ; // true
b < a; // also true.

Such a computer would have a == b return an undetermined value.

This is going to spell havoc for sorting algorithms,

The real problem is strict weak ordering:

a < b && b < c

Doesn't imply:

a < c

But std::less< T * > is *required* to be specialized to overcome
this limitation with operator <.

Rob.