Sorting a list of objects.

A

Amit Bhatia

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

class B{
//other stuff;
list<A> mylist;

}

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.




--
 
S

Sumit Rajan

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

class B{
//other stuff;
list<A> mylist;

}

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

Kai-Uwe Bux

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

class B{
//other stuff;
list<A> mylist;

}

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
 
I

Ivan Vecerina

: Amit Bhatia wrote:
....
: > class B{
: > //other stuff;
: > list<A> mylist;
....
: > 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
 
K

Kai-Uwe Bux

Ivan said:
: 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<Rank> class (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<T> as 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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top