Conditionally implementing spaceship

When it comes to adopting operator<=> for library class templates, there are three choices a library can make:

Just don’t adopt it (Never Spaceship)
Conditionally adopt it if all of its constituent types provide it (Sometimes Spaceship)
Unconditionally adopt it, if necessary assuming the minimum semantics that the library requires (Always Spaceship)

There isn’t really that much to say about Never Spaceship. This post will focus on Sometimes Spaceship - how to conditionally provide spaceship. Always Spaceship will be the subject of a future post (I’m using “Always” here to still be conditioned on the type having comparison operators - I’m not suggesting that you take a type without any comparisons defined, stick it in a vector and suddenly you can compare them).

In P1186R0, I focused on std::optional<T> and in the previous post in this series, I talked about std::pair<T, U>. In this post I will instead focus on std::vector<T>. The reasons for this (in addition to a general penchant for variety) are:

For vector<T>, unlike pair<T,U>, the comparison operators cannot be defaulted. They are, in that sense, more interesting to consider.
For vector<T>, unlike optional<T>, the relational operators are all defined in terms of <. That is p >= q is defined as !(p < q), so the type T only has to define operator<. optional<T> on the other hand is transparent, its operator>= forwards to T’s operator>=. The transformation done by vector is pretty typical for the standard library, and there is even blanket wording in the standard assuming this in [operators]. I’ll explain the significance of this in the future Always Spaceship post.

Ultimately, the reason I wanted to write this post right now isn’t that I had an urge to implement more operator<=>s. It’s that with each discussion I have about this topic, I feel that I can do it better - and many of the arguments I’ve made in the past are just incorrect and my previous attempts at solving this problem need to be improved. Think of this post as my way of trying to figure out how to actually solve this problem.

C++17 status quo for `vector<T>`

Before I go in depth about how the comparison operators for vector<T> could look tomorrow, I thought it would be helpful to start with how they look today. I’m going to use concepts anyway, just for convenience. We’ve had concepts in the standard for quite some time - just not as a language feature - so this isn’t too much of a stretch (although for vector<T>, none of these operators are actually constrained according to the standard).

// just a convenience alias
template <typename T>
using CREF = remove_reference_t<T> const&;

// the "concepts" for comparisons as they exist in the Standard
// Library today. I am just using them for convenience
template <typename T>
concept Cpp17EqualityComparable = requires(CREF<T> a, CREF<T> b) {
  { a == b } -> convertible_to<bool>;
};

template <typename T>
concept Cpp17LessThanComparable = requires(CREF<T> a, CREF<T> b) {
  { a < b } -> convertible_to<bool>;
};

// two operators actually implement functionality
template <Cpp17EqualityComparable T>
bool operator==(vector<T> const& lhs, vector<T> const& rhs) {
    return equal(lhs.begin(), lhs.end(),
                 rhs.begin(), rhs.end());
}

template <Cpp17LessThanComparable T>
bool operator<(vector<T> const& lhs, vector<T> const& rhs) {
    return lexicographical_compare(lhs.begin(), lhs.end(),
                                   rhs.begin(), rhs.end());
}

// the other four just forward to one of the first two
template <Cpp17EqualityComparable T>
bool operator!=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs == rhs);
}

template <Cpp17LessThanComparable T>
bool operator<=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(rhs < lhs);
}

template <Cpp17LessThanComparable T>
bool operator>(vector<T> const& lhs, vector<T> const& rhs) {
    return rhs < lhs;
}

template <Cpp17LessThanComparable T>
bool operator>=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs < rhs);
}

We have 6 operators, 4 of which defer to one of the other 2. This is our starting point, and what we want to improve.

A `concept` for `operator<=>`

Before I get into any further implementation, we need a concept for the spaceship operator. With a lot of help from Casey Carter, this is what I’m gong to propose for C++20:

template <typename T, typename Cat>
  concept compares-as = // exposition only
    Same<common_comparison_category_t<T, Cat>, Cat>;

template <typename T, typename Cat=std::partial_ordering>
  concept ThreeWayComparable = requires(CREF<T> a, CREF<T> b) {
    { a <=> b } -> compares-as<Cat>;
  };

template <typename T, typename U,
          typename Cat=std::partial_ordering>
  concept ThreeWayComparableWith =
    ThreeWayComparable<T, Cat> &&
    ThreeWayComparable<U, Cat> &&
    CommonReference<CREF<T>, CREF<U>> &&
    ThreeWayComparable<
      common_reference_t<CREF<T>, CREF<U>>,
      Cat> &&
    requires(CREF<T> t, CREF<U> u) {
      { t <=> u } -> compares-as<Cat>;
      { u <=> t } -> compares-as<Cat>;
    };

If we just wrote the requirement as { t <=> u } -> convertible_to<Cat>, that would allow for some awkward things like returning a type that isn’t a comparison category but happens to have a conversion operator for one. I don’t know that anybody would ever actually write that, but it’s better to just be more explicit. What we want to say isn’t that the type is convertible to Cat, we want to say that it’s specifically a comparison category that is convertible to Cat. That’s what common_comparison_category_t<T, Cat> is for - that type will either be void (if either type isn’t actually a comparison category) or the weaker of T and Cat - we’re okay with Cat being weaker than T, but not vice versa. Hence the Same.

The heterogeneous comparison concept follows the pattern of the other standard library concepts. We’re not just checking syntax, we’re checking full semantics. It’s not just that syntactically you can write t <=> u, it’s that all variations of that make sense, including t <=> t and u <=> u.

Conditionally adopting `operator<=>`, Take 1

To start with, we must keep operator== as is. It’s not going anywhere and it’s correct. After P1185R0 (also described in the last post), it cannot be replaced with operator<=>. Even if we choose to unconditionally provide <=>, we need still to provide operator== too. a == b never calls a <=> b implicitly.

But we can easily drop operator!=. By default, a != b will rewrite to !(a == b) (technically to (a == b) ? false : true to sidestep the language having to deal with operator!() and only require a contextual conversion to bool - I preferred to write the conditional operator than !static_cast<bool>(a == b)…). That is precisely what our operator does, and that is precisely what all operator!=s should do, so we don’t need it to write it. Ever again.

That drops us to 5 operators.

What I argued in P1186R0 was that conditionally adopting operator<=> is bad because the way you would do that is:

// same two operators providing functionality
template <Cpp17EqualityComparable T>
bool operator==(vector<T> const& lhs, vector<T> const& rhs) {
    return equal(lhs.begin(), lhs.end(),
                 rhs.begin(), rhs.end());
}

template <Cpp17LessThanComparable T>
bool operator<(vector<T> const& lhs, vector<T> const& rhs) {
    return lexicographical_compare(lhs.begin(), lhs.end(),
                                   rhs.begin(), rhs.end());
}

// just three other "forwarding" operators
template <Cpp17LessThanComparable T>
bool operator<=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(rhs < lhs);
}

template <Cpp17LessThanComparable T>
bool operator>(vector<T> const& lhs, vector<T> const& rhs) {
    return rhs < lhs;
}

template <Cpp17LessThanComparable T>
bool operator>=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs < rhs);
}

// and Sometimes Spaceship
template <ThreeWayComparable T>
compare_3way_type_t<T> operator<=>(vector<T> const& lhs,
                                   vector<T> const& rhs) {
    return lexicographical_compare_3way(lhs.begin(), lhs.end(),
                                        rhs.begin(), rhs.end());
}

Any type which satisfies ThreeWayComparable would also satisfy Cpp17LessThanComparable (short of weird pathological cases where a type implements operator<=> but deletes operator<… don’t do that), and the result would be that p <=> q would invoke operator<=> but p < q would invoke operator<. That’s bad both because we would never actually invoke <=> (which would become oddly useless) but also because <=> could provide a faster ordering than < could, and we’re not taking advantage of this (for vector<T>, we’d be making up to 2N-1 calls to < when we could be making just N calls to <=>).

That’s the argument I made in P1186 - and the above paragraph is totally true and I stand by it. But it’s not really an argument against Sometimes Spaceship, it’s simply an argument to avoid this specific implementation strategy for Sometimes Spaceship.

Do not do this, I was wrong, it is wrong. This is an anti-pattern.

Conditionally adopting `operator<=>`, Take 2

In my previous post, I shows an improved implementation which gets you the right semantics you want: p < q invokes <=> if there is an <=> that can be invoked, and only invokes < if there is no spaceship candidate. That implementation was a bit verbose, and actually could only be written using member functions. For vector<T>, that would look like:

template <typename T>
struct vector {
    bool operator==(vector<T> const&) const
        requires Cpp17EqualityComparable<T>;

    // the pre-existing operators
    bool operator< (vector<T> const&) const
        requires Cpp17LessThanComparable<T>;
    bool operator<=(vector<T> const&) const
        requires Cpp17LessThanComparable<T>;
    bool operator> (vector<T> const&) const
        requires Cpp17LessThanComparable<T>;
    bool operator>=(vector<T> const&) const
        requires Cpp17LessThanComparable<T>;

    // <=> and defaulted operators
    compare_3way_type_t<T> operator<=>(vector<T> const&) const
        requires ThreeWayComparable<T>;
    bool operator< (vector<T> const&) const
      requires Cpp17LessThanComparable<T> && ThreeWayComparable<T>
        = default;
    bool operator<=(vector<T> const&) const
      requires Cpp17LessThanComparable<T> && ThreeWayComparable<T>
        = default;
    bool operator> (vector<T> const&) const
      requires Cpp17LessThanComparable<T> && ThreeWayComparable<T>
        = default;
    bool operator>=(vector<T> const&) const
      requires Cpp17LessThanComparable<T> && ThreeWayComparable<T>
        = default;
};

The purposes of defaulting all those operators is to get around the problem in the previous implementation. Now, given p < q, the defaulted candidate would be preferred to the pre-existing one (because of concepts and constraint subsumption). And p < q for defaulted < means exactly (p <=> q) < 0. That was what we wanted to happen: for types which don’t have spaceship yet, we preserve existing behavior, but for types which do have spaceship, we always invoke it.

This solution is an improvement in semantics. But… we have to write 10 functions, 4 of which are defaulted? That’s… not a good story. Plus we’re stuck writing these as member functions, and member functions have slightly different semantics than non-member functions. It’d be good to pick your implementation strategy based on the semantics you want for those comparisons - not just as a result of only having a single option.

Conditionally adopting `operator<=>`, Take 3

Let’s take a step back and reconsider what is actually going on here, and what we are trying to accomplish (and a big thank you to Casey Carter for spending the time to help me improve this solution and to give me the tools to come up with a better one).

Typically, when we perform overload resolution, we look up a particular name (like begin or operator<<), find all the candidates with that name, and then pick the best one. Importantly, the candidates that we look up all are named the same. We pick the best begin, or the best operator<<, etc. It’s tempting to extend this intuition out to understanding spaceship - and think that the way overload resolution continues to work with an expression like p < q is that we pick the best operator< among the operator<s and, if we can’t find one, fallback to looking up p <=> q < 0.

But that isn’t how it works at all. We do something fairly novel - our candidate set for relational comparisons includes both operator< candidates and operator<=> candidates and reversed operator<=> candidates. We try to pick the best viable candidate amongst this entire set. The relevant order of tie-breakers here is (filtered from [over.match.best]):

Better conversion sequence
Prefer the candidate that is NOT a function template specialization to one that is
Prefer the more specialized function template (partial ordering rules)
Prefer the more constrained function template (concept subsumption rules)
Prefer the non-rewritten candidate (i.e. in this case p < q, prefer an operator< to an operator<=>)
Prefer the non-reversed candidate (i.e. in this case p < q, prefer p <=> q < 0 to 0 < (q <=> p))

What in here can we use to our advantage? To restate our goal: we want p < q to invoke operator<=> if that is a viable candidate, otherwise to fall-back to operator< if that is a viable candidate.

If we look at our operator declarations, #1, #2, and #3 will just never apply. Every operator takes both of its arguments as vector<T> const&. Same conversion sequences, everything is a template, nothing is more specialized. The next tie-breaker is #4. Can we take advantage of that one? Yes, we can! We just have to make spaceship more constrained than each of the relational operators. That’s just a matter of ensuring that subsumption happens.

The pattern we want is this:

template <Cpp17LessThanComparable T>
bool operator<(T const&, T const&);

template <ThreeWayComparable T>
    requires Cpp17LessThanComparable<T>
bool operator<=>(T const&, T const&);

For a given type, if ThreeWayComparable<T> holds, the expression p < q will find both of these operators as candidates (again, despite having different names!). But operator<=> is more constrained following the subsumption rules, so it will be preferred.

If ThreeWayComparable<T> does not hold, but Cpp17LessThanComparable<T> does, then p < q only has one viable candidate: operator<. Again, as desired.

That full solution, a vector<T> which conditionally provides <=> if and only if T does - but uses it for all the ordering comparisons, looks like this:

template <Cpp17EqualityComparable T>
bool operator==(vector<T> const& lhs, vector<T> const& rhs) {
    return equal(lhs.begin(), lhs.end(),
                 rhs.begin(), rhs.end());
}

template <Cpp17LessThanComparable T>
bool operator<(vector<T> const& lhs, vector<T> const& rhs) {
    return lexicographical_compare(lhs.begin(), lhs.end(),
                                   rhs.begin(), rhs.end());
}

template <Cpp17LessThanComparable T>
bool operator<=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs > rhs);
}

template <Cpp17LessThanComparable T>
bool operator>(vector<T> const& lhs, vector<T> const& rhs) {
    return rhs < lhs;
}

template <Cpp17LessThanComparable T>
bool operator>=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs < rhs);
}

template <ThreeWayComparable T>
    requires Cpp17LessThanComparable<T>
compare_3way_type_t<T> operator<=>(vector<T> const& lhs,
                                   vector<T> const& rhs) {
    return lexicographical_compare_3way(lhs.begin(), lhs.end(),
                                        rhs.begin(), rhs.end());
}

I believe this is really the correct way to conditionally provide operator<=> for a library type. We still have to write 6 functions (not 10 as I’d previously claimed), we just swapped operator!= for operator<=>, but we have to be careful about how to properly constrain these operators.

As you can hopefully see by my series of errors in attempting to solve this problem, it’s decidedly non-trivial! Unlike my initial attempt in P1186, this solution is optimal. Unlike my second attempt last month, this solution doesn’t require gratuitous defaulting of operators.

I had mentioned earlier that vector<T> specifically does not currently constrain its comparison operators. Extending vector specifically to conditionally adopt <=> is even easier, since all you need to do is add a constrained operator<=> and you’re done; a constrained function is automatically more constrained than an unconstrained one, don’t even need any kind of complicated reasoning there.

Conditionally adopting `operator<=>`, conditional C++20

A slightly more complex topic would be to handle the case where we not only just want Sometimes Spaceship, but we also want a library that can compile in C++17 mode too. For that, we have no choice but to hide the operator behind an #ifdef. But what is the right way to do it?

The rule I briefly touched on in the last section - that a constrained function is trivially more constrained than an unconstrained one - turns out to help us mightily. C++17 doesn’t have concepts, so no existing operators will use them - they will either be unconstrained or use a mechanism like std::enable_if to remove themselves from overload sets as necessary. As a result, all you have to do in this cases is conditionally preprocess our conditional operator<=>, as follows:

// type traits for == and <, implementation left as an exercise
template <typename T> struct supports_eq;
template <typename T> struct supports_lt;

template <typename T>
enable_if_t<supports_eq<T>::value, bool>
operator==(vector<T> const& lhs, vector<T> const& rhs) {
    return equal(lhs.begin(), lhs.end(),
                 rhs.begin(), rhs.end());
}

// we need != in C++17, and no point in preprocessing this one out
template <typename T>
enable_if_t<supports_eq<T>::value, bool>
operator!=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs == rhs);
}

template <typename T>
enable_if_t<supports_lt<T>::value, bool>
operator<(vector<T> const& lhs, vector<T> const& rhs) {
    return lexicographical_compare(lhs.begin(), lhs.end(),
                                   rhs.begin(), rhs.end());
}

template <typename T>
enable_if_t<supports_lt<T>::value, bool>
operator<=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs > rhs);
}

template <typename T>
enable_if_t<supports_lt<T>::value, bool>
operator>(vector<T> const& lhs, vector<T> const& rhs) {
    return rhs < lhs;
}

template <typename T>
enable_if_t<supports_lt<T>::value, bool>
operator>=(vector<T> const& lhs, vector<T> const& rhs) {
    return !(lhs < rhs);
}

// use the feature-test macro to conditionally preprocess
// the spaceship operator (I am not sure at the moment what
// the correct macro is for operator<=>)
#if __cpp_spaceship
template <ThreeWayComparable T>
compare_3way_type_t<T> operator<=>(vector<T> const& lhs,
                                   vector<T> const& rhs) {
    return lexicographical_compare_3way(lhs.begin(), lhs.end(),
                                        rhs.begin(), rhs.end());
}
#endif

In C++17, we think of the six two-way comparison functions here as being constrained. In the sense that these functions have static preconditions that, if unmet, lead to these operators being removed from the overload set (i.e. SFINAE).

But with the introduction of Concepts in C++20, the term constrained refers specifically to the use of Concepts (whether named concepts or requires clauses). In C++20, those six comparison functions are considered to be not be constrained. The new operator<=> on the other hand, is constrained - and hence is more constrained than any of the other binary operators. This ensures that when operator<=> is a viable candidate (i.e. when ThreeWayComparable<T> holds), that it is the best viable candidate.

The above implementation does the right thing. In C++17, there will not be an operator<=> declared. In C++20, there will be, and it will be used in precisely the cases we want it to be.

Conditionally implementing spaceship

C++17 status quo for vector<T>

A concept for operator<=>

Conditionally adopting operator<=>, Take 1

Conditionally adopting operator<=>, Take 2

Conditionally adopting operator<=>, Take 3

Conditionally adopting operator<=>, conditional C++20