Why is const required for 'operator>' but not for 'operator<'?

Consider this piece of code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& other) {
        return (key < other.key);
    }
};

int main() {
    std::vector < MyStruct > vec;

    vec.push_back(MyStruct(2, "is"));
    vec.push_back(MyStruct(1, "this"));
    vec.push_back(MyStruct(4, "test"));
    vec.push_back(MyStruct(3, "a"));

    std::sort(vec.begin(), vec.end());

    for (const MyStruct& a : vec) {
        cout << a.key << ": " << a.stringValue << endl;
    }
}

It compiles fine and gives the output one would expect. But if I try to sort the structures in descending order:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& other) {
        return (key > other.key);
    }
};


int main() {
    std::vector < MyStruct > vec;

    vec.push_back(MyStruct(2, "is"));
    vec.push_back(MyStruct(1, "this"));
    vec.push_back(MyStruct(4, "test"));
    vec.push_back(MyStruct(3, "a"));

    std::sort(vec.begin(), vec.end(), greater<MyStruct>());

    for (const MyStruct& a : vec) {
        cout << a.key << ": " << a.stringValue << endl;
    }
}

This gives me an error. Here is the full message:

/usr/include/c++/7.2.0/bits/stl_function.h: In instantiation of 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = MyStruct]':
/usr/include/c++/7.2.0/bits/stl_function.h:376:20: error: no match for 'operator>' (operand types are 'const MyStruct' and 'const MyStruct')
{ return __x > __y; }

It seems to be because this function right here doesn't have a const qualifier:

bool operator > (const MyStruct& other) {
        return (key > other.key);
}

If I add it,

bool operator > (const MyStruct& other) const {
        return (key > other.key);
}

Then everything is fine again. Why is this so? I'm not too familiar with operator overloading, so I've just put it in memory that we need to add the const but it's still weird why it works for operator< without the const.

Solution 1:

You get different behaviors because you are in fact calling two different (overloaded) sort functions.

In the first case you call the two parameter std::sort, which uses operator< directly. Since the iterators to your vector elements produce non-const references, it can apply operator< just fine.

In the second case, you are using the three parameter version of std::sort. The one that accepts a functor. You pass std::greater. And that functor has an operator() declared as follows:

constexpr bool operator()( const T& lhs, const T& rhs ) const;

Note the const references. It binds the elements it needs to compare to const references. So your own operator> must be const correct as well.

If you were to call std::sort with std::less, your operator< will produce the same error, because it's not const-correct.

Solution 2:

Use of std::sort(vec.begin(), vec.end()) depends only on the operator< function. It does not require that the function be able to work with const objects.

std::greater, on the other hand, requires the function be able to work with const objects.

You will see a similar problem if you use std::less, such as std::sort(vec.begin(), vec.end(), std::less<MyStruct>()).

Having said that, there is no reason for the operator< function and the operator> function to be non-const member functions. Any member function that does not modify member data should be made a const member function.