sorting list of pointers

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::operator<( Something & )
instead of default operator< for pointers ?

re: sorting list of pointers

Nenad Jalsovec wrote:
[color=blue]
> 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::operator<( Something & )
> instead of default operator< for pointers ?[/color]

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

//...

things.sort(Someting_ptr_cmp);

re: sorting list of pointers

"Rolf Magnus" <ramagnus@t-online.de> wrote in message
news:cfjavn$hgq$04$1@news.t-online.com...[color=blue]
> Nenad Jalsovec wrote:
>[color=green]
> > 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::operator<( Something & )
> > instead of default operator< for pointers ?[/color]
>
> struct Something_ptr_cmp
> {
> bool operator(Something* lhs, Something* rhs)[/color]

Did you forget the < there, as in:

bool operator <(Something* lhs, Something* rhs)
[color=blue]
> {
> return *lhs < *rhs;
> }
> };
>
> //...
>
> things.sort(Someting_ptr_cmp);
>[/color]

re: sorting list of pointers

Howard wrote:
[color=blue]
> "Rolf Magnus" <ramagnus@t-online.de> wrote in message
> news:cfjavn$hgq$04$1@news.t-online.com...[color=green]
>> Nenad Jalsovec wrote:
>>[color=darkred]
>> > 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::operator<( Something &
>> > )
>> > instead of default operator< for pointers ?[/color]
>>
>> struct Something_ptr_cmp
>> {
>> bool operator(Something* lhs, Something* rhs)[/color]
>
> Did you forget the < there, as in:[/color]

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.

re: sorting list of pointers

"Rolf Magnus" <ramagnus@t-online.de> wrote in message
news:cfjavn$hgq$04$1@news.t-online.com...[color=blue]
> Nenad Jalsovec wrote:
>[color=green]
> > 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::operator<( Something & )
> > instead of default operator< for pointers ?[/color]
>
> struct Something_ptr_cmp
> {
> bool operator(Something* lhs, Something* rhs)
> {
> return *lhs < *rhs;
> }
> };
>
> //...
>
> things.sort(Someting_ptr_cmp);
>[/color]


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() );
}

re: sorting list of pointers

"Nenad Jalsovec" <nenad@medix.com.hr> wrote in message
news:cfjjga$sfv$1@ls219.htnet.hr...[color=blue]
>
> "Rolf Magnus" <ramagnus@t-online.de> wrote in message
> news:cfjavn$hgq$04$1@news.t-online.com...[color=green]
> > Nenad Jalsovec wrote:
> >[color=darkred]
> > > 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::operator<( Something & )
> > > instead of default operator< for pointers ?[/color]
> >
> > struct Something_ptr_cmp
> > {
> > bool operator(Something* lhs, Something* rhs)
> > {
> > return *lhs < *rhs;
> > }
> > };
> >
> > //...
> >
> > things.sort(Someting_ptr_cmp);
> >[/color]
>
>
> 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() );
> }
>
>
>
>
>[/color]

Damn!
int main()

re: sorting list of pointers

On Sat, 14 Aug 2004 00:47:07 +0200, Rolf Magnus <ramagnus@t-online.de>
wrote:
[color=blue]
> Howard wrote:
>[color=green]
>> "Rolf Magnus" <ramagnus@t-online.de> wrote in message
>> news:cfjavn$hgq$04$1@news.t-online.com...[color=darkred]
>>> Nenad Jalsovec wrote:
>>>
>>> > 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::operator<( Something &
>>> > )
>>> > instead of default operator< for pointers ?
>>>
>>> struct Something_ptr_cmp
>>> {
>>> bool operator(Something* lhs, Something* rhs)[/color]
>>
>> Did you forget the < there, as in:[/color]
>
> 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.
>[/color]

You also forgot const

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

john

re: sorting list of pointers

John Harrison wrote:
[color=blue]
> On Sat, 14 Aug 2004 00:47:07 +0200, Rolf Magnus <ramagnus@t-online.de>
> wrote:
>[color=green]
>> Howard wrote:
>>[color=darkred]
>>> "Rolf Magnus" <ramagnus@t-online.de> wrote in message
>>> news:cfjavn$hgq$04$1@news.t-online.com...
>>>> Nenad Jalsovec wrote:
>>>>
>>>> > 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::operator<( Something
>>>> > & )
>>>> > instead of default operator< for pointers ?
>>>>
>>>> struct Something_ptr_cmp
>>>> {
>>>> bool operator(Something* lhs, Something* rhs)
>>>
>>> Did you forget the < there, as in:[/color]
>>
>> 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.
>>[/color]
>
> You also forgot const
>
> bool operator()(Something* lhs, Something* rhs) const[/color]

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

re: sorting list of pointers

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;
}

re: sorting list of pointers

"Nenad Jalsovec" <nenad@medix.com.hr> wrote in message news:cfjads$i80$1@ls219.htnet.hr...[color=blue]
> How to force things.sort() to use Something::operator<( Something & )
> instead of default operator< for pointers ?
>[/color]
Hopefully, you know that operator<() is not well defined for pointers that are not pointing
into the same array.

re: sorting list of pointers

Ron Natalie wrote in news:411ea484$0$2358$9a6e19ea@news.newshosting.com
in comp.lang.c++:
[color=blue]
>
> "Nenad Jalsovec" <nenad@medix.com.hr> wrote in message
> news:cfjads$i80$1@ls219.htnet.hr...[color=green]
>> How to force things.sort() to use Something::operator<( Something & )
>> instead of default operator< for pointers ?
>>[/color]
> Hopefully, you know that operator<() is not well defined for pointers
> that are not pointing into the same array.
>[/color]

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.
--
http://www.victim-prime.dsl.pipex.com/

re: sorting list of pointers

"Rob Williscroft" <rtw@freenet.co.uk> wrote in message[color=blue][color=green]
> > Hopefully, you know that operator<() is not well defined for pointers
> > that are not pointing into the same array.
> >[/color]
>
> 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 * >() );
> }
>[/color]

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,

re: sorting list of pointers

Ron Natalie wrote:
[color=blue]
>
> "Rob Williscroft" <rtw@freenet.co.uk> wrote in message[color=green][color=darkred]
>> > Hopefully, you know that operator<() is not well defined for pointers
>> > that are not pointing into the same array.
>> >[/color]
>>
>> 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 * >() );
>> }
>>[/color]
>
> 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,[/color]

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

re: sorting list of pointers

Ron Natalie wrote in news:411f77a4$0$2489$9a6e19ea@news.newshosting.com
in comp.lang.c++:
[color=blue]
>
> "Rob Williscroft" <rtw@freenet.co.uk> wrote in message[color=green][color=darkred]
>> > Hopefully, you know that operator<() is not well defined for
>> > pointers that are not pointing into the same array.
>> >[/color]
>>
>> 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 * >() );
>> }
>>[/color]
>
> Unfortunately, the above code doesn't have well defined behavior,[/color]

Yes it does, the citation is above.
[color=blue]
> 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.
>[/color]

Such a computer would have a == b return an undetermined value.
[color=blue]
> This is going to spell havoc for sorting algorithms,
>[/color]

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.
--
http://www.victim-prime.dsl.pipex.com/