Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

polymorphic sorting functors

 
 
L. Kliemann
Guest
Posts: n/a
 
      06-19-2008
#include <iostream>
#include <vector>

using namespace std;

class cmp_base : public std::binary_function<int, int, bool> {
public:
virtual bool operator()(int i, int j) { return i>j; }
};
class cmp_inc : public cmp_base {
public:
virtual bool operator()(int i, int j) { return i<j; }
};
void sort_it(vector<int> *v, cmp_base *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_inc cmp;
sort_it(&v, &cmp);
for (unsigned int i=0; i<v.size(); ++i) { cout << v.at(i) << endl; }
return 0;
}


It should be clear what I am trying to implement here: function sort_it shall
sort the given vector according to the comparison functor passed in the
second argument. The base class 'cmp_base' would usually be implemented
purely virtual, but is here given with an implementation for sorting the
vector in decreasing order, for demonstration purposes.

The problem is that although I create an object of type 'cmp_inc', the vector
is sorted in decreasing order. If 'cmp_base' is implemented as an ABC, the
program won't even compile.

As far as I understood, I am following a standard approach here: having a
base class and functions taking pointers to the base class, but in fact
handing pointers to objects of derived classes to these functions. However,
the sort function from the STL expects an object, not a pointer, and so I
pass *cmp to it. This seems to be the cause of all the trouble.

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

 
Reply With Quote
 
 
 
 
Ivan
Guest
Posts: n/a
 
      06-19-2008
On Jun 19, 12:02*pm, "L. Kliemann" <(E-Mail Removed)-kiel.de> wrote:
> #include <iostream>
> #include <vector>
>
> using namespace std;
>
> class cmp_base : public std::binary_function<int, int, bool> {
> * *public:
> * *virtual bool operator()(int i, int j) { return i>j; }};
>
> class cmp_inc : public cmp_base {
> * *public:
> * *virtual bool operator()(int i, int j) { return i<j; }};
>
> void sort_it(vector<int> *v, cmp_base *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_inc cmp;
> * *sort_it(&v, &cmp);
> * *for (unsigned int i=0; i<v.size(); ++i) { cout << v.at(i) << endl; }
> * *return 0;
>
> }
>
> It should be clear what I am trying to implement here: function sort_it shall
> sort the given vector according to the comparison functor passed in the
> second argument. The base class 'cmp_base' would usually be implemented
> purely virtual, but is here given with an implementation for sorting the
> vector in decreasing order, for demonstration purposes.
>
> The problem is that although I create an object of type 'cmp_inc', the vector
> is sorted in decreasing order. If 'cmp_base' is implemented as an ABC, the
> program won't even compile.
>
> As far as I understood, I am following a standard approach here: having a
> base class and functions taking pointers to the base class, but in fact
> handing pointers to objects of derived classes to these functions. However,
> the sort function from the STL expects an object, not a pointer, and so I
> pass *cmp to it. This seems to be the cause of all the trouble.
>
> Is there still a way to do this without using templates?


It seems std::sort takes the 3rd parameter as a pass by value not a
pass by reference.

Therefore when you pass a reference to a cmp_base by value into
std::sort, std::sort has no idea about the derived object type you are
actually passing.

Makes sense?

Ivan Novick
 
Reply With Quote
 
 
 
 
L. Kliemann
Guest
Posts: n/a
 
      06-19-2008
* Ivan <(E-Mail Removed)>:

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


[...]
>> As far as I understood, I am following a standard approach here: having a
>> base class and functions taking pointers to the base class, but in fact
>> handing pointers to objects of derived classes to these functions. However,
>> the sort function from the STL expects an object, not a pointer, and so I
>> pass *cmp to it. This seems to be the cause of all the trouble.
>>
>> Is there still a way to do this without using templates?

>
> It seems std::sort takes the 3rd parameter as a pass by value not a
> pass by reference.
>
> Therefore when you pass a reference to a cmp_base by value into
> std::sort, std::sort has no idea about the derived object type you are
> actually passing.
>
> Makes sense?


Yes, that makes sense.

Isn't that pretty bad design on the part of std::sort?

 
Reply With Quote
 
Triple-DES
Guest
Posts: n/a
 
      06-20-2008
On 19 Jun, 21:02, "L. Kliemann" <(E-Mail Removed)-kiel.de> wrote:
> #include <iostream>
> #include <vector>
>
> using namespace std;
>
> class cmp_base : public std::binary_function<int, int, bool> {
> * *public:
> * *virtual bool operator()(int i, int j) { return i>j; }};
>
> class cmp_inc : public cmp_base {
> * *public:
> * *virtual bool operator()(int i, int j) { return i<j; }};


You have forgotten to declare your operator const, by the way.

> void sort_it(vector<int> *v, cmp_base *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_inc cmp;
> * *sort_it(&v, &cmp);
> * *for (unsigned int i=0; i<v.size(); ++i) { cout << v.at(i) << endl; }
> * *return 0;
>
> }
>
> It should be clear what I am trying to implement here: function sort_it shall
> sort the given vector according to the comparison functor passed in the
> second argument. The base class 'cmp_base' would usually be implemented
> purely virtual, but is here given with an implementation for sorting the
> vector in decreasing order, for demonstration purposes.
>
> The problem is that although I create an object of type 'cmp_inc', the vector
> is sorted in decreasing order. If 'cmp_base' is implemented as an ABC, the
> program won't even compile.
>
> As far as I understood, I am following a standard approach here: having a
> base class and functions taking pointers to the base class, but in fact
> handing pointers to objects of derived classes to these functions. However,
> the sort function from the STL expects an object, not a pointer, and so I
> pass *cmp to it. This seems to be the cause of all the trouble.
>
> Is there still a way to do this without using templates?


Any reason in particular that you can't use templates here?

template<typename Comp>
void sort_it(vector<int> *v, const Comp& cmp) {
sort(v->begin(), v->end(), cmp);

}

DP
 
Reply With Quote
 
Road.Tang
Guest
Posts: n/a
 
      06-20-2008
On Jun 20, 3:43 am, "L. Kliemann" <(E-Mail Removed)-kiel.de> wrote:
> * Ivan <(E-Mail Removed)>:
>
> >> void sort_it(vector<int> *v, cmp_base *cmp) {
> >> sort(v->begin(), v->end(), *cmp);}

>
> [...]
>
>
>
> >> As far as I understood, I am following a standard approach here: having a
> >> base class and functions taking pointers to the base class, but in fact
> >> handing pointers to objects of derived classes to these functions. However,
> >> the sort function from the STL expects an object, not a pointer, and so I
> >> pass *cmp to it. This seems to be the cause of all the trouble.

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

>
> > It seems std::sort takes the 3rd parameter as a pass by value not a
> > pass by reference.

>
> > Therefore when you pass a reference to a cmp_base by value into
> > std::sort, std::sort has no idea about the derived object type you are
> > actually passing.

>
> > Makes sense?

>
> Yes, that makes sense.
>
> Isn't that pretty bad design on the part of std::sort?


You used cmp_base* , because you want a unique sort interface, here is
sort_it.
so you can pass any subclass of cmp_base to sort_it , regardless of
what's logic in your sub-class.

but note standard sort is better one, it accepts any sub-class you
have, including sub-classesof cmp_base and all other functional
objects or functions themself.
and no performance cost of a indirection of base pointer.


-roadt





 
Reply With Quote
 
L. Kliemann
Guest
Posts: n/a
 
      06-20-2008
* Road.Tang <(E-Mail Removed)>:
> On Jun 20, 3:43 am, "L. Kliemann" <(E-Mail Removed)-kiel.de> wrote:
>> * Ivan <(E-Mail Removed)>:
>>
>> >> void sort_it(vector<int> *v, cmp_base *cmp) {
>> >> sort(v->begin(), v->end(), *cmp);}


[...]
> You used cmp_base* , because you want a unique sort interface, here is
> sort_it.
> so you can pass any subclass of cmp_base to sort_it , regardless of
> what's logic in your sub-class.
>
> but note standard sort is better one, it accepts any sub-class you
> have, including sub-classesof cmp_base and all other functional
> objects or functions themself.
> and no performance cost of a indirection of base pointer.


Ok, I see. Could you please point out to me how I can write a function
with an interface as std::sort has got? Then I would use that for sort_it.

Thank you!

 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      06-20-2008
In article <g3eafk$5sf$(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed)-kiel.de
says...

[ ... using std::sort ]

> The problem is that although I create an object of type 'cmp_inc', the vector
> is sorted in decreasing order. If 'cmp_base' is implemented as an ABC, the
> program won't even compile.


Since it's passed by value, the derived object is being "sliced" to
become a base object.

> As far as I understood, I am following a standard approach here: having a
> base class and functions taking pointers to the base class, but in fact
> handing pointers to objects of derived classes to these functions. However,
> the sort function from the STL expects an object, not a pointer, and so I
> pass *cmp to it. This seems to be the cause of all the trouble.
>
> 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
L. Kliemann
Guest
Posts: n/a
 
      06-22-2008
* Jerry Coffin <(E-Mail Removed)>:

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

 
Reply With Quote
 
Jerry Coffin
Guest
Posts: n/a
 
      06-22-2008
In article <g3l97c$uuu$(E-Mail Removed)>, (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.

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.
 
Reply With Quote
 
L. Kliemann
Guest
Posts: n/a
 
      06-25-2008
* Jerry Coffin <(E-Mail Removed)>:
> In article <g3l97c$uuu$(E-Mail Removed)>, (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. 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?

 
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