By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,426 Members | 1,877 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,426 IT Pros & Developers. It's quick & easy.

sorting list of pointers

P: n/a
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 ?
Jul 22 '05 #1
Share this Question
Share on Google+
13 Replies


P: n/a
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)
{
return *lhs < *rhs;
}
};

//...

things.sort(Someting_ptr_cmp);

Jul 22 '05 #2

P: n/a

"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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:

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

//...

things.sort(Someting_ptr_cmp);

Jul 22 '05 #3

P: n/a
Howard wrote:
"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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:


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.

Jul 22 '05 #4

P: n/a

"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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)
{
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() );
}

Jul 22 '05 #5

P: n/a

"Nenad Jalsovec" <ne***@medix.com.hr> wrote in message
news:cf**********@ls219.htnet.hr...

"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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)
{
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() );
}



Damn!
int main()
Jul 22 '05 #6

P: n/a
On Sat, 14 Aug 2004 00:47:07 +0200, Rolf Magnus <ra******@t-online.de>
wrote:
Howard wrote:
"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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:


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
Jul 22 '05 #7

P: n/a
John Harrison wrote:
On Sat, 14 Aug 2004 00:47:07 +0200, Rolf Magnus <ra******@t-online.de>
wrote:
Howard wrote:
"Rolf Magnus" <ra******@t-online.de> wrote in message
news:cf*************@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:


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


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).
Jul 22 '05 #8

P: n/a

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;
}
Jul 22 '05 #9

P: n/a

"Nenad Jalsovec" <ne***@medix.com.hr> wrote in message news:cf**********@ls219.htnet.hr...
How to force things.sort() to use Something::operator<( 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.

Jul 22 '05 #10

P: n/a
Ron Natalie wrote in news:41**********************@news.newshosting.com
in comp.lang.c++:

"Nenad Jalsovec" <ne***@medix.com.hr> wrote in message
news:cf**********@ls219.htnet.hr...
How to force things.sort() to use Something::operator<( 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.


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/
Jul 22 '05 #11

P: n/a

"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
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 * >() );
}


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,

Jul 22 '05 #12

P: n/a
Ron Natalie wrote:

"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
> 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 * >() );
}


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
Jul 22 '05 #13

P: n/a
Ron Natalie wrote in news:41**********************@news.newshosting.com
in comp.lang.c++:

"Rob Williscroft" <rt*@freenet.co.uk> wrote in message
> 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 * >() );
}


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.
--
http://www.victim-prime.dsl.pipex.com/
Jul 22 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.