c++sorting language-lawyer c++20 std-ranges

std::ranges::sort not working with non-default operator<=>?

I have a case when struct type needs non-default operator<=> - just not all fields are important when defining order of objects.

struct A
{
    int a;
    int b; // not important when ordering
    int c;

    constexpr std::strong_ordering operator<=>(const A& rhs) const
    {
        if (const auto res = a<=>rhs.a; res != 0) return res;
        return c<=>rhs.c;
    }
};

To my surprise, I cannot use container with this type as an argument to std::ranges::sort:

std::array<A, 100> aa{};
std::ranges::sort(aa);

I checked it on newest gcc (14) and clang (19) and it basically claims that the range is not sortable because std::invocable_v<std::ranges::less&, A&, A&> is not true. See godbold link

More observations:

It works with std::sort (std::sort(aa.begin(), aa.end());)
It works when adding non-default operator==
And it works with default (=default) operator<=>

Is this compilers bug, C++ standard bug or some strange C++ rules play here and it should be that way? If the last option is correct - can you provide justification for such behavior?

Update:

From the comments it seems that std::ranges::less{}(A{}, A{}) requires not only operator< (derived from operator<=>) but also operator== that cannot be derived from non-default operator<=> so the error.

But the one question remains - why std::ranges::less needs operator==?

And better example from comments: link

Solution

Sorting algorithms rely on the fact that the items being sorted are totally ordered (in the mathematical sense). This means that there is an order that is reflexive, transitive, antisymmetric and, in order to be a total order, strongly connected, which means that for any a and b,

a <= b || b <= a

or:

if (a != b) then a <= b or b <= a

and because of the antisymmetry requirement, it's EITHER a <= b OR b <= a. This again implies that for any collection a, b, c, ... there exists a permutation x, y, z, ... such that x <= y <= z <= ..., or in other words: The collection can be sorted.

So the constraint for ranges::less that its operands must be totally ordered exists not only for the purpose of requiring that certain operators are available, but also to indicate the operators must have certain semantics. Algorithms can then be written under the assumption that the available operators have these semantics.

This is why concepts in C++20 often have semantic requirements in addition to type requirements. Semantic requirements are not enforced by the compiler, but developers are supposed to honor them when defining a type that models a concept, and as a result, when a type models a concept, developers can assume that the type also fulfills all semantic requirements of the concept.

If a type is totally ordered, then all the comparison operators are well-defined for it and can be (mathematically) inferred from just the < operator. Therefore, the totally_ordered concept requires that all operators are available, simply because it is meaningful for a totally ordered type, and because it is easy to define all operators using the <=> operator.

However, for performance reasons, the compiler does not automatically generate the == operator when a type has a custom <=> operator, because <=> potentially cannot be implemented as efficiently as ==, and it is not guaranteed that the implicitly provided == operator would have the same semantics as if it was implemented in terms of the (custom) <=> operator. For example, when comparing strings, == can have O(1) time complexity for strings that have different length, whereas <=> cannot.

Therefore, if <=> is not defaulted, you have to explicitly define == in order for all comparison operators to be defined, which is required to model the concept totally_ordered, which is required by ranges_less, which is used by ranges::sort, because sorting algorithms require total order in order to work as designed.