Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > polymorphic sorting functors

Reply
Thread Tools

polymorphic sorting functors

 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      06-25-2008
L. Kliemann wrote:

> * Jerry Coffin <(E-Mail Removed)>:
>> In article <g3l97c$uuu$(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed)-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.

>
> My function f shall implement an algorithm which at some point of its
> operation has to sort things. I wish to use the algorithms with different
> ways of sorting. In which way to sort shall be passed to the function by
> some parameter.


And how does that differ from std::sort?

> Wouldn't it be an elegant way to allow that parameter to
> resemble the corresponding one in the std::sort function, in order that my
> function f can just pass it through?


If all you want is a wrapper around std::sort that operates on containers,
you could do:

template < typename Range, typename Comp >
void sort_range( Range & r, Comp p ) {
std::sort( r.begin(), r.end(), p );
}


Best

Kai-Uwe Bux
 
Reply With Quote
 
 
 
 
Jerry Coffin
Guest
Posts: n/a
 
      06-25-2008
In article <g3tsvv$d96$(E-Mail Removed)>, (E-Mail Removed)-kiel.de
says...

[ ... ]

> My function f shall implement an algorithm which at some point of its
> operation has to sort things. I wish to use the algorithms with different
> ways of sorting. In which way to sort shall be passed to the function by some
> parameter. Wouldn't it be an elegant way to allow that parameter to resemble
> the corresponding one in the std::sort function, in order that my function f
> can just pass it through?


Yes, it probably would. std::sort can use either a comparison object OR
a comparison function. TTBOMK, the only way to do that in C++ is to use
a template parameter.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
 
Thomas J. Gritzan
Guest
Posts: n/a
 
      06-25-2008
L. Kliemann schrieb:
> My function f shall implement an algorithm which at some point of its
> operation has to sort things. I wish to use the algorithms with different
> ways of sorting. In which way to sort shall be passed to the function by some
> parameter. Wouldn't it be an elegant way to allow that parameter to resemble
> the corresponding one in the std::sort function, in order that my function f
> can just pass it through?
>


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

--
Thomas
 
Reply With Quote
 
L. Kliemann
Guest
Posts: n/a
 
      06-25-2008
* Thomas J. Gritzan <(E-Mail Removed)>:
> L. Kliemann schrieb:
>> My function f shall implement an algorithm which at some point of its
>> operation has to sort things. I wish to use the algorithms with different
>> ways of sorting. In which way to sort shall be passed to the function by some
>> parameter. Wouldn't it be an elegant way to allow that parameter to resemble
>> the corresponding one in the std::sort function, in order that my function f
>> can just pass it through?
>>

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

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


#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; } };
void sort_it(vector<int> *v, func_t cmp) {
sort(v->begin(), v->end(), cmp); }
int main(void) {
vector<int> v;
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; }

 
Reply With Quote
 
Thomas J. Gritzan
Guest
Posts: n/a
 
      06-25-2008
L. Kliemann schrieb:
> * Thomas J. Gritzan <(E-Mail Removed)>:
>> 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<int> v;
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
sorting a vector, functors, and std::binary_function Christopher C++ 4 11-29-2007 11:27 AM
functors nsgi_2004 C++ 2 08-12-2004 07:35 AM
functors with reference parameters red floyd C++ 0 11-13-2003 12:50 AM
Re: Need help with generic functors.... Rob Williscroft C++ 3 08-17-2003 11:57 PM
Functors with behaviour in the destructor Paul MG C++ 2 07-03-2003 03:12 AM



Advertisments