From: Garrett Mitchener <wgm2@acpub.duke.edu>
  To  : 
  Date: 16 Feb 1999 14:42:02 -0500

Re: using sort....

"Huned M. Botee" <huned.botee@duke.edu> writes:

> Luke Palmer wrote:
> > 
> > mmm....  yes, i know what you mean by derefrencing.  however, what i wanted
> > to do is to say
> > 
> > myList.sort();
> > 
> > and have STL sort the appointments in the list according to the appointment
> > comparison operators rather than sort the pointer values.  in short, i don't
> > really want to write a sort.....  :)   however, i may have to.  any ideas?
> > thanks.
> > -luke
> 
> make a list of objects. sort it. make a list of pointers using the list
> of objects. you end up with two parallel lists, sorted by object. One
> list is of pointers to objects, another of objects. not efficient, but
> it should work. you can then discard the list of objects and keep the
> list of pointers to sorted objects.
> 
> ciao.

I assume you are working with STL's sort function.  I can't recommend
that kind of parallel copy stuff.  You may be dealing with a vector of
pointers to objects that you can't have an array of.  They may be
pointers to objects of different subclasses of some abstract class.
You will hit this problem frequently if you use inheritance properly
and try to work with STL.

You are correct that just plain sorting a list of pointers is not what
you want.  The simpler version of sort just compares all the elements
with <.  It will put pointers in order of address, which is kind of
useless.  Also, you can't write a function

bool operator < ( Thingee *, Thingee * )

hoping it will sort them by value instead
because its arguments are all built-in types and the language already
defines an operator < for them.

However, STL provides a way out.  You should note that it's templated,
and that you there is a second variant which takes a predicate object
to sort by.  You can do something like this:

class PointerCompare
{
public:
   bool operator()( Thingee * left, Thingee * right )
   {
     ... compare *left with *right ...
   }
};

vector<Thingee*> someList;

sort( someList.begin(), someList.end(), PointerCompare() );

The last argument there is just constructing a temporary, anonymous
object of class PointerCompare.  The code for sort will do something
like this:

sort( a, b, pr )
{
 ... sorting along...
 if( pr( a, b ) ) // calls PointerCompare::operator() to tell which
                  // one comes first
 {
   ...put a first...
 }
 else
 {
   ...put b first...
 }
 ...
}

This syntax is understandably strange.  STL algorithms are designed to
take function objects as parameters.  Look at the STL documentation
for <algorithm> which has a few more details.

	-- Garrett *<:-)