Passing a private method of the class as the compare operator for std::sort

Question

I am writing a code to solve the following problem: Given a set of numbers x[0], x[1], ..., x[N-1], find the permutation that makes them sorted in the ascending order. In the other words, I would like to find a permutation on {0,2,...,N-1} such as i[0], i[1], ..., i[N-1] such that x[i[0]] <= x[i[1]] <= ... <= x[i[N-1]].

For this, I have stored the x vector and an index vector i (initially filled with i[j] = j) as private members of a class. I have also defined a private method as

bool MyClass::compare(size_t s, size_t t) {
    return (x[s] < x[t]);
}

Now, I would call the std::sort as follows

std::sort(i.begin(), i.end(), compare);

and I expect to get the desired result. But the code does not compile and I get the following error:

error: no matching function for call to ‘sort(std::vector<long unsigned int>::iterator, std::vector<long unsigned int>::iterator, <unresolved overloaded function type>)’

I must have done everything correctly as also the documentation of std::sort mentions that I can pass a function as the compare operator to std::sort (http://www.cplusplus.com/reference/algorithm/sort/)

Thanks for all the helps in advance.

Answer 1

There are a couple of issues with your approach. The first one and most evident is that you cannot use a member function as a free function. To be able to call compare you need an object of type MyClass and two integers. Inside std::sort the implementation is going to try to call a free (non-member) function with only two integer arguments.

Other than that, you cannot create a pointer to a member function without explicitly taking its address. The line std::sort(..., compare); will not compile for a member function. While non-member functions will automatically decay to a pointer to the function that is not the case here.

In C++11 there are two different solutions that you can take. The most generic is creating a lambda that captures the this argument:

std::sort(std::begin(i),std::end(i),
          [](int x, int y) { return compare(x,y); }); // or maybe even implement here

A different approach would be binding the object and the member function into a functor:

std::sort(std::begin(i),std::end(i),
          std::bind(&MyClass::compare,this,_1,_2));

In this last case, the std::bind function will create an object that implements operator() taking two arguments and will call the member function MyClass::compare on the object pointed by this.

The semantics of both approaches are slightly different, but in this case you can use either one.

Answer 2

Please keep in mind instance methods have an implicit first parameter - the this pointer of the object. Thus your comparison operator is not of the type expected by std::sort - it takes three arguments instead of the expected 2. Use a bind function to get around this(for instance boost::bind). Take a look at this question for instance.