# Conditionally implementing spaceship

- Improvements to <=>
- Conditionally implementing spaceship
- Unconditionally 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.

*Next post in the series:*Unconditionally implementing spaceship

Let me know what you think of this article on twitter @BarryRevzin!