Why do I get a compilation error for this program in g++ 4.8.5?

Question

I'm trying to solve a problem from an online judge and the judge uses g++ 4.8.5.

The following program compiles correctly on my machine (g++ 8.2.0) with -std=c++11 -pedantic-errors:

#include <algorithm>

struct Task {
    int deadline;
    const bool operator<(const Task &o) {
        return deadline < o.deadline;
    }
};
Task tasks[] = {8, 4, 3, 5, 1, 2, 0, 7};

int main()
{
    std::sort(tasks, tasks + 8);
}

However, the judge gives me the following errors:

In file included from /usr/include/c++/4.8/algorithm:62:0,
                 from Main.cpp:1:
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = Task*; _Tp = Task]':
/usr/include/c++/4.8/bits/stl_algo.h:2283:70: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = Task*]' /usr/include/c++/4.8/bits/stl_algo.h:2315:54:
required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = Task*; _Size = int]' /usr/include/c++/4.8/bits/stl_algo.h:5461:36:
required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = Task*]' Main.cpp:15:23:
required from here /usr/include/c++/4.8/bits/stl_algo.h:2245:19:
error: passing 'const Task' as 'this' argument of 'const bool Task::operator<(const Task&)' discards qualifiers [-fpermissive]
    while (__pivot < *__last)
       ^

The judge compiles with -std=c++11 -O2 -lm.

Does g++ 4.8 not fully support C++11? How do I compile this?

Answer 1

Yes, GCC 4.8 does support most of C++11, which can be seen here. However, this seems to have been an error in GCC 4.8. The exact requirements of std::sort are located in Section 25.4 of this ISO specification from 2013.

There it notes that the only requirement on operator< is that it implements a "strict weak ordering". It then goes on to define a "strict weak ordering" by its mathematical properties. None of this seems to imply that operator< must be const as GCC 4.8 tried to force. The operator< could perhaps change an internal variable, and still follow the specification, as long as the booleans returned make a "strict weak ordering". This could be used to count the number of comparisons made on each variable by the std::sort function, allowing easier benchmarking of std::sort without going into undefined behavior (As just one example of many different possibilities).

Using const must have been an over-assumption on the original implementation of C++11 in GCC 4.8, and was corrected in later versions.

Unfortunately, if the online judge is using that version of GCC, you can't do anything about it. The other answers here specify how to fix it (Namely, making your member function const).

Digging into GCC's history, we can see that it was changed here, on 2013-09-27. It seemed like a larger refactor that might not've paid attention to intricacies, but the contributer did remove const in several areas so it appeared to be intentional. The commit msg isn't too enlightening either. If you want you can email him, see if he remembers xD

Answer 2

const bool operator<(const Task &o) {

should be

bool operator<(const Task &o) const {

It doesn't make sense for the return value to be const, and as a comparison operator it doesn't need to modify *this.

The error message says passing 'const Task' as 'this' argument of 'const bool Task::operator<(const Task&)' discards qualifiers, so somewhere in the bowels of std::sort it's trying to call operator< on a const Task object. Your original tasks array is not const, so this is presumably because std::sort is calling a helper function that takes a const Task & (because the helper function doesn't need to modify anything).

The call fails because your operator< wasn't declared as const (i.e. callable on a const object).

I'm not sure what's different about g++ 8.2, but apparently the implementation of std::sort has changed so it doesn't refer to const T objects internally anymore.

Answer 3

Notice this line in the error message

error: passing 'const Task' as 'this' argument of 'const bool Task::operator<(const Task&)' discards qualifiers

std::sort expects the operator< for your object to not modify the object itself. You need to indicate the fact that your comparison operator does not mutate the object's state by explicitly marking it as const.

The correct version would look something like

struct Task {
    int deadline;
    const bool operator<(const Task &o) const {
        return deadline < o.deadline;
    }
};

Refer to this link for more info: Meaning of 'const' last in a function declaration of a class?