polymorphic sorting functors

Discussion in 'C++' started by L. Kliemann, Jun 19, 2008.

  1. L. Kliemann

    L. Kliemann Guest

    #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?
     
    L. Kliemann, Jun 19, 2008
    #1
    1. Advertising

  2. L. Kliemann

    Ivan Guest

    On Jun 19, 12:02 pm, "L. Kliemann" <-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
     
    Ivan, Jun 19, 2008
    #2
    1. Advertising

  3. L. Kliemann

    L. Kliemann Guest

    * Ivan <>:

    >> 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?
     
    L. Kliemann, Jun 19, 2008
    #3
  4. L. Kliemann

    Triple-DES Guest

    On 19 Jun, 21:02, "L. Kliemann" <-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
     
    Triple-DES, Jun 20, 2008
    #4
  5. L. Kliemann

    Road.Tang Guest

    On Jun 20, 3:43 am, "L. Kliemann" <-kiel.de> wrote:
    > * Ivan <>:
    >
    > >> 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
     
    Road.Tang, Jun 20, 2008
    #5
  6. L. Kliemann

    L. Kliemann Guest

    * Road.Tang <>:
    > On Jun 20, 3:43 am, "L. Kliemann" <-kiel.de> wrote:
    >> * Ivan <>:
    >>
    >> >> 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!
     
    L. Kliemann, Jun 20, 2008
    #6
  7. L. Kliemann

    Jerry Coffin Guest

    In article <g3eafk$5sf$>, -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.
     
    Jerry Coffin, Jun 20, 2008
    #7
  8. L. Kliemann

    L. Kliemann Guest

    * Jerry Coffin <>:

    [ ... 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!
     
    L. Kliemann, Jun 22, 2008
    #8
  9. L. Kliemann

    Jerry Coffin Guest

    In article <g3l97c$uuu$>, -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.
     
    Jerry Coffin, Jun 22, 2008
    #9
  10. L. Kliemann

    L. Kliemann Guest

    * Jerry Coffin <>:
    > In article <g3l97c$uuu$>, -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?
     
    L. Kliemann, Jun 25, 2008
    #10
  11. L. Kliemann

    Kai-Uwe Bux Guest

    L. Kliemann wrote:

    > * Jerry Coffin <>:
    >> In article <g3l97c$uuu$>, -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
     
    Kai-Uwe Bux, Jun 25, 2008
    #11
  12. L. Kliemann

    Jerry Coffin Guest

    In article <g3tsvv$d96$>, -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.
     
    Jerry Coffin, Jun 25, 2008
    #12
  13. 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
     
    Thomas J. Gritzan, Jun 25, 2008
    #13
  14. L. Kliemann

    L. Kliemann Guest

    [solved] polymorphic sorting functors

    * Thomas J. Gritzan <>:
    > 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; }
     
    L. Kliemann, Jun 25, 2008
    #14
  15. Re: [solved] polymorphic sorting functors

    L. Kliemann schrieb:
    > * Thomas J. Gritzan <>:
    >> 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
     
    Thomas J. Gritzan, Jun 26, 2008
    #15
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul MG
    Replies:
    2
    Views:
    405
    Dhruv
    Jul 3, 2003
  2. Rob Williscroft

    Re: Need help with generic functors....

    Rob Williscroft, Aug 17, 2003, in forum: C++
    Replies:
    3
    Views:
    359
    Gordon Scott
    Aug 18, 2003
  3. red floyd
    Replies:
    0
    Views:
    341
    red floyd
    Nov 13, 2003
  4. nsgi_2004

    functors

    nsgi_2004, Aug 12, 2004, in forum: C++
    Replies:
    2
    Views:
    480
    Karl Heinz Buchegger
    Aug 12, 2004
  5. Christopher
    Replies:
    4
    Views:
    629
    James Kanze
    Nov 29, 2007
Loading...

Share This Page