Comparison function for sorting member vector with sort()

Question

i have a class like this:

class test
{  
    vector<expr*> _exprs;  

    bool cmp(expr* e1, expr* e2);   

    ExprManager* mg;  
}  

and the Comparison function is:

bool test::cmp(expr* e1, expr* e2)  
{  
    return exprHight(mg, e1) < exprHight(mg, e2);  
}  

then when i use the comparison function in sorting the _exprs(in another member function)

sort(_exprs->begin(), _exprs->end(), cmp);  

The compiler report:

error: argument of type ‘bool (test::)(void*, void*)’ does not match ‘bool (test::*)(void*, void*)’

How to fix it? Thanks for advance.

Answer 1

The normal way to define a predicate for sorting is as a functor.

Make your class define the operator() to do the comparing, and you can just pass an instance of the class to std::sort.

So really, all you need to do is to define the class like this instead:

class test
{  
    vector<expr*> _exprs;  

    bool operator()(expr* e1, expr* e2);   

    ExprManager* mg;  
}  

And then you can call sort like this:

sort(_exprs->begin(), _exprs->end(), test());  

or, of course, use an existing instance of the test class, instead of constructing a new one. But you just pass in a class instance, and don't need to mention the member function at all.

If the sorting takes place in another member function (it looks that way from your reference to _exprs), write

sort(_exprs->begin(), _exprs->end(), *this);  

One thing to note is that std::sort, like most other standard library algorithms, copies the predicate object, and so your predicate class must be able to handle copying safely (which your classes should always do anyway)

In short, the way to achieve this is to follow the "rule of three".

If your class defines a destructor, copy constructor or assignment operator, then it should almost certainly define all three.

If the compiler-generated copy constructor is used, it will simply copy your class' pointer members, so you will have two objects containing pointers to the same object.

If the class has a destructor which calls delete on that pointer, then that ends up being done twice. Which is an error.

If your class is intended to be copyable (and most of the standard library requires this), then you must define appropriate copy constructors and assignment operators to implement it safely (for example, copy the resource pointed to by the pointer, or use a smart pointer instead).

IF your class is not intended to be copyable, then you should define the copy constructor and assignment operators to be private, so that attempts to copy the class will result in a compile-time error, instead of runtime crashes.

You should never ever define a class which can be copied, but doesn't do so correctly. Either define the necessary copy constructor/assignment operator/destructors to handle copying, or make copying impossible by making copy ctor/assignment operator private.

Wrapping pointers to dynamically allocated memory owned by the class in smart pointers is a simple way to get copyability for free.

If the class contains only RAII objects, then you don't need to define a destructor at all, and so the rule of three doesn't require you to define copy constructor and assignment operator either.

Answer 2

You need to make test::cmp() static:

class test {
    // ...
    static bool cmp( expr * lhs, expr * rhs );
};

Alternatively, if test::cmp() cannot be static for some reason, you need to use (boost:: or std::tr1::) bind() to bind the (implicit) this parameter of cmp():

test * someInstance = this // other // something;
sort( _exprs->begin(), _exprs->end(),
      bind( &test::cmp,  someInstance, _1, _2 ) );

Answer 3

Use operator() and then pass '*this' as a Predicate to Sort algorithm.

class test
{  
    vector<expr*> _exprs;  

    bool operator()(expr* e1, expr* e2);   

    ExprManager* mg;  
}  

sort(_exprs->begin(), _exprs->end(), *this);  

Whatever you pass as predicate must have public accessibility,