Sorting a list of objects.

[Amit Bhatia]

User-Agent: OSXnews 2.081
Xref: number1.nntp.dca.giganews.com comp.lang.c++:824790
Hi,
I have a list of objects (instantiations of class A) in a class B:

class B{
//other stuff;
list<Amylist;

}

Now I would like to sort the elements of mylist according to some
criteria. My question is how can I do it? I know stl list provides built in
sort function: where do I need to write/define this function so that I can
call something like:
mylist.sort(); ?

The class A is a concrete class. Do I need to define something the
function in class A?
thanks,
--a.


--

[Sumit Rajan]

Amit Bhatia wrote:

Hi,
I have a list of objects (instantiations of class A) in a class B:

class B{
//other stuff;
list<Amylist;

}

Now I would like to sort the elements of mylist according to some
criteria. My question is how can I do it? I know stl list provides built in
sort function: where do I need to write/define this function so that I can
call something like:
mylist.sort(); ?

The class A is a concrete class. Do I need to define something the
function in class A?
thanks,

You could define "<" for class A. Something like:

//within class A's definition
bool operator < (const A& rhs)
{
return (a < rhs.a);
}

Or you could define it as a free function (friendly or unfriendly :-) )
comparing two As. Something like:

bool operator < (const A& lhs, const A& rhs)
{
return (lhs.a < rhs.a);
}

In case it is a friend function you will need to add something like this
to the class definition:
friend bool operator < (const A& lhs, const A& rhs);
Regards,
Sumit.

[Kai-Uwe Bux]

Amit Bhatia wrote:

>
Hi,
I have a list of objects (instantiations of class A) in a class B:

class B{
//other stuff;
list<Amylist;

}

Now I would like to sort the elements of mylist according to some
criteria. My question is how can I do it? I know stl list provides built
in sort function: where do I need to write/define this function so that I
can call something like:
mylist.sort(); ?

The class A is a concrete class. Do I need to define something the
function in class A?
thanks,

You have several options:

a) define a member function

class A {
...
bool operator< ( A const & rhs ) const {
}

}

b) define a free-standing (friend) operator:

bool operator< ( A const & lhs, A const & rhs ) {
}

c) add a specialization to std::less<>:

namespace std {

template <>
struct less< A : binary_predicate< A {

bool operator() ( A const & lhs, A const & rhs ) {
}

};

d) define a free standing (friend) predicate

bool is_less ( A const & lhs, A const & rhs ) {
}

and pass this as a parameter:

mylist.sort( is_less );
The third and fourth alternatives convey the understanding that the ordering
is not natural, whereas the first two options indicate that objects of class
A allow for a canonical comparison.

The third option is often more convenient than the fourth since std::less
will be automatically used by sort() and its friends. The fourth
alternative is more appealing if you are using more than one sort order in
your program.

Best

Kai-Uwe Bux

[Ivan Vecerina]

"Kai-Uwe Bux" <jk********@gmx.netwrote in message
news:eg**********@murdoch.acc.Virginia.EDU...
: Amit Bhatia wrote:
....
: class B{
: //other stuff;
: list<Amylist;
....
: Now I would like to sort the elements of mylist according to some
: criteria. My question is how can I do it? I know stl list provides
built
: in sort function:
Just a note to the OP, as others implicitly pointed out:
an std::list can only be sorted using its member function
'sort', unlike random access containers (like std::vector
or std::queue) on which you use std::sort found in <algorithm>.

: where do I need to write/define this function so that I
: can call something like:
: mylist.sort(); ?
: >
: The class A is a concrete class. Do I need to define something the
: function in class A?
: thanks,
:
: You have several options:
:
: a) define a member function
:
: class A {
: ...
: bool operator< ( A const & rhs ) const {
: }
:
: }
:
: b) define a free-standing (friend) operator:
:
: bool operator< ( A const & lhs, A const & rhs ) {
: }
Of these two options, I always use b).
Reasons for this? :
- writing the implementation of b) is clearer,
more symmetric, and less error prone.
- implicit conversions: when using a), implicit
convertions to A will only be performed on the
rhs, but not on the lhs. Think of having a
BigInt class having a non-explicit constructor
from 'int', with a) you would not be able to
compile: bool b = 5 < myBigIntValue.

b) can directly be implemented within the class
body as follows:
friend bool operator<( A const& a, A const& b )
{ return a.m < b.m; }
: c) add a specialization to std::less<>:
:
: namespace std {
:
: template <>
: struct less< A : binary_predicate< A {
:
: bool operator() ( A const & lhs, A const & rhs ) {
: }
:
: };
I have trouble envisioning why one would want to write
this. IMO std::less still implies a natural, default
ordering of the operands, and if this is the case,
I'd rather provide the comparison operator <.
This is delicate to get right, and as far as I know,
there is no "binary_predicate" template in the standard
(you'd have to use binary_function<A,A,bool>).

: d) define a free standing (friend) predicate
:
: bool is_less ( A const & lhs, A const & rhs ) {
: }
:
: and pass this as a parameter:
:
: mylist.sort( is_less );

An alternative to this d) is to provide a predicate object:
struct AByName {
bool operator()( A const& a, A const& b )
{ return a.name < b.name; }
};
Passing it as:
mylist.sort( AByName() );

This may be more verbose, but has advantages:
- parameters can be provided to the comparison object
(and stored as data members), for example to indicate
which data member is to be used.
- I'm not sure this remains the case, but compilers used
to be more apt at inlining a predicate object than
a function provided by pointer ( = faster performance ).
So personally, I would only consider one of these 2 (or 3)
options:
- if there is a natural ordering, define operator < (as per b) )
- if there is none, use a predicate function or object
( d) or my last suggestion above )
Kind regards,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Kai-Uwe Bux]

Ivan Vecerina wrote:

"Kai-Uwe Bux" <jk********@gmx.netwrote in message

[snip]

: c) add a specialization to std::less<>:
:
: namespace std {
:
: template <>
: struct less< A : binary_predicate< A {
:
: bool operator() ( A const & lhs, A const & rhs ) {
: }
:
: };
I have trouble envisioning why one would want to write
this. IMO std::less still implies a natural, default
ordering of the operands, and if this is the case,
I'd rather provide the comparison operator <.

I feel a difference between a default total order (such as the one used by
set<>) and a natural ordering. This may depend on the local culture as it
is a matter or conveying intent and not in any way legislated by the
standard.

I overload std::less routinely for types for which there is a total ordering
that can be computed efficiently. The reason is simple: I want to be able
to use std::set<and std::map<without further thought; and in the
absence of a natural order, I want them to use an efficient method by
default. I only make operator< available if there is a natural meaning. For
instance, I would provide a specialization of std::less for a
free_group_element<Rankclass (and I would make it fast) but I would not
provide operator<.

However, I can see that there are reasons to think of std::less<Tas still
pretending to be natural: after all it is the default used in std::sort.

This is delicate to get right, and as far as I know,
there is no "binary_predicate" template in the standard
(you'd have to use binary_function<A,A,bool>).

Right about the binary_predicate, which should be in std but isn't :-(
However, I do not really see what is so hard about getting a partial
specialization for std::less<right. It is not any more difficult than
implementing a comparison function object of your own choice.

: d) define a free standing (friend) predicate
:
: bool is_less ( A const & lhs, A const & rhs ) {
: }
:
: and pass this as a parameter:
:
: mylist.sort( is_less );

An alternative to this d) is to provide a predicate object:
struct AByName {
bool operator()( A const& a, A const& b )
{ return a.name < b.name; }
};
Passing it as:
mylist.sort( AByName() );

This may be more verbose, but has advantages:
- parameters can be provided to the comparison object
(and stored as data members), for example to indicate
which data member is to be used.
- I'm not sure this remains the case, but compilers used
to be more apt at inlining a predicate object than
a function provided by pointer ( = faster performance ).

[snip]

Right, I missed that option.
Thanks

Kai-Uwe Bux