Re: polymorphic sorting functors

[L. Kliemann]

* Jerry Coffin <jc*****@taeus.com>:

[ ... using std::sort ]

>Is there still a way to do this without using templates?

Sure -- you can use a smart pointer class of some sort, which can be
passed by value, and still point at derived objects.

The big question would be why you want to do this -- you haven't said
why you want to rule out templates, but unless your code is doing
something a lot different from what you've shown, a template will make
simplify your code considerably.

My question was mostly out of curiosity. I've been working with C++ for about
half a year now, and I came across several occasions where my first approach
was to use polymorphism, but it did not work (could not write compilable code
that would express what I meant). In many of these cases, using templates was
a solution. In fact, I cannot recall any major issue where polymorphism was a
solution. Now I wanted to review these cases to see if I missed something.

In the case at hand, it looks like polymorphism really is the inferior
approach. Templates look better. There is, however, a third alternative: give
my function sort_it() a similar interface to that of std::sort(), so that I
can pass any comparison functor to it (by value). Maybe someone can point out
to me how to accomplish that. Thank you!

[Jerry Coffin]

In article <g3**********@news.albasani.net>, st******@mail.uni-kiel.de
says...

[ ... ]

In the case at hand, it looks like polymorphism really is the inferior
approach. Templates look better. There is, however, a third alternative: give
my function sort_it() a similar interface to that of std::sort(), so that I
can pass any comparison functor to it (by value). Maybe someone can point out
to me how to accomplish that. Thank you!

That could make sense if you passed the comparison function by
_reference_ instead of value. If you pass it by value, I don't see the
point, since you just end up with essentially a clone of std::sort.

As far as the basic point of polymorphism goes, it's mostly for
situations where you don't know until _runtime_ exactly what type of
object you're going to work with. The most obvious case is a collection
that's heterogenous, so different objects in the collection need to act
in different ways to get the correct behavior.

Another type of situation is where the polymorphic objects are
essentially similar to device drivers. For example, you might have a
database front-end that can talk to various different kinds of database
servers. From the viewpoint of the front-end, any server (that can meet
its requirements) is the same, but you still need some customized pieces
of code to allow that common interface to talk to the individual
servers, and you do that by having objects to talk to the servers, and
virtual functions to define the interface.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Thomas J. Gritzan]

L. Kliemann schrieb:

* Thomas J. Gritzan <ph*************@gmx.de>:

>If you want to change the sorting behaviour at run-time, you could pass
a tr1::function object to std::sort.

Great! I'd never heard of tr1 before, but it seems to be a solution.

tr1 will be part of the coming C++ standard. Most parts of it were
developed and were/are part of the Boost library. Both tr1 and Boost are
worth to know.

This code works (using gcc 4.2.4, produced no warnings with -Wall and
-Wextra):

Some comments:

>
#include <iostream>
#include <vector>
#include <algorithm>
#include <tr1/functional>

using namespace std;

typedef tr1::function <bool (int, int)func_t;

class cmp_base : public std::binary_function<int, int, bool{
public:
virtual bool operator()(int i, int j) = 0; };
class cmp_inc : public cmp_base {
public:
virtual bool operator()(int i, int j) { return i<j; } };
class cmp_dec : public cmp_base {
public:
virtual bool operator()(int i, int j) { return i>j; } };

You don't need a hierarchy with virtual functions. You can contruct a
tr1::function object with a simply functor (class with operator()) or
even a normal function. tr1::function works internally with virtual
functions and will dispatch the call to the currently assigned function
or functor.

But be aware that this run-time dispatch will disable some compiler
optimization, like inlineing the comparator function into the sort
algorithm. It's not a problem unless you have many objects to sort and
you need speed.

void sort_it(vector<int*v, func_t cmp) {
sort(v->begin(), v->end(), cmp); }

Prefer pass by reference:

void sort_it(vector<int>& v, const func_t& cmp) {
sort(v.begin(), v.end(), cmp);
}

Pointers have additional complexity that's not needed in this case.
Pointers can be null, they can be reseated, you can do arithmetics with
them. Prefer to use pointers only when you need them.

I would also pass the comparator by (const) reference to avoid a copy.
It is a kind of microoptimization, but a common one.

int main(void) {
vector<intv;
v.push_back(10);v.push_back(1);v.push_back(20);
cmp_dec cmp1;
sort_it(&v, cmp1);
cout << "decreasing:" << endl;
for (unsigned int i=0; i<v.size(); ++i) { cout << v.at(i) << endl; }
cmp_inc cmp2;
sort_it(&v, cmp2);
cout << "increasing:" << endl;
for (unsigned int i=0; i<v.size(); ++i) { cout << v.at(i) << endl; }
return 0; }

In general, if you want others to read your code, please insert more
whitespace/newlines. This code might be compact formatted, but it is
horrible to read it.

--
Thomas