Passing a private class method as a comparison operator for std :: sort

Question

I am writing code to solve the following problem: given the set of numbers x[0] , x[1] , ..., x[N-1] , find a permutation that sorts them in ascending order. In 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]] .

To do this, I saved the vector x and the pointer vector i (originally filled with i[j] = j ) as private members of the class. I also defined a private method as

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

Now I would call 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 had to do everything right, and the documentation std::sort mentions that I can pass the function as a comparison operator to std::sort ( http://www.cplusplus.com/reference/algorithm/sort/ )

Thanks for all the help in advance.

Answer 1

There are several issues with your approach. The first and most obvious 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 implementation will try to call the free (non-member) function with two integer arguments.

In addition, you cannot create a pointer to a member function without explicitly specifying your address. String std::sort(..., compare); will not compile for a member function. While functions that are not members automatically break up into a pointer to a function that does not take place here.

In C ++ 11, there are two different solutions you can take. The most common is to create 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 

Another approach would be to bind an object and a member function to a functor:

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

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

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

Answer 2

Keep in mind that instance methods have an implicit first parameter - the this pointer to the object. Thus, your comparison operator is not of the type expected by std::sort — three arguments are required instead of the expected one. 2. Use the bind function to get around this (for example, boost::bind ). See this question for example.

Answer 3

One way to solve this problem is to define a function call operator in your class ( see here ):

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

Then you can call the sort () method as follows:

 sort(i.begin(), i.end(), *this); 

Answer 4

I just want to comment that @dribeas answer doesn't work for me. I use the lambda function and I had to edit it:

  std::sort(MyVector.begin(), MyVector.end(), [this](int x, int y) { return compare(x,y); });