Why I can not determine the comparison without constant

Question

If I define the compare function as follows:

 bool compare(Student& a, Student& b) { return an < bn; } 

g ++ will complain:

 g++ -Wall main.cpp -o main In file included from /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/algorithm:63:0, from main.cpp:1: /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h: In function '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Student*, std::vector<Student> >, _Tp = Student, _Compare = bool (*)(Student&, Student&)]': /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h:2261:78: instantiated from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Student*, std::vector<Student> >, _Compare = bool (*)(Student&, Student&)]' /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h:2302:62: instantiated from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Student*, std::vector<Student> >, _Size = long int, _Compare = bool (*)(Student&, Student&)]' /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h:5250:4: instantiated from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<Student*, std::vector<Student> >, _Compare = bool (*)(Student&, Student&)]' main.cpp:38:51: instantiated from here /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h:2229:4: error: invalid initialization of reference of type 'Student&' from expression of type 'const Student' /usr/lib/gcc/x86_64-pc-linux-gnu/4.5.3/include/g++-v4/bits/stl_algo.h:2232:4: error: invalid initialization of reference of type 'Student&' from expression of type 'const Student' Compilation exited abnormally with code 1 at Mon May 28 08:05:35 

But if I define a comparison with the const type, it will compile and work fine.

And here is the whole code:

 class Student { public: Student(string); string n; }; bool compare(Student& a, Student& b) { return an < bn; } Student::Student(string name) { n = name; } int main() { Student A = Student("A"); Student B = Student("B"); vector<Student> students; students.push_back(B); students.push_back(A); sort(students.begin(), students.end(), compare); cout << "After sort" << endl; for(vector<Student>::iterator i = students.begin(); i != students.end(); ++i) { cout << "Student: " << i->n << endl; } return 0; } 

Answer 1

In this implementation, std::sort uses

  const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&, _Compare); 

In your case, _Tp is the student, and _Compare is compare .

So, you basically have

 const Student& std::__median(const Student&, const Student&, const Student&, bool (*)(Student&, Student&) ) 

or similar. Obviously, the callback cannot be applied to parameters if they are converted to const , which is why it fails.

Make parameters for your compare const method.

Answer 2

I do not believe that there is a requirement in the standard that says that the parameters of the function must be const, so I believe that your implementation is wrong for rejection. However, there is a requirement that the function does not change the arguments:

From the standard - 25.4 / 2

Compare is the type of function object (20.8). Return value A function call operation applied to an object of type Compare, when contextually converted to bool (4), gives true if the first argument to the call is less than the second, and false otherwise. Compare comp is used for algorithms involving an ordering relationship. this suggested that comp would not apply any mutable function through a dereferenced iterator.

And the signature std::sort from 25.4.1.1

 template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) 

So, since your function is not allowed to change its arguments, it really should accept them as const, but the standard does not require this. Therefore, although your implementation may be erroneous, I believe that this is a forgiving error, since it manages to pay attention to the fact that either your function violates the standard by changing its arguments, or is not constant.

Answer 3

You must do this const, as it leaves two parameters the same.