Implementing the spaceship operator for optional
Last week, the C++ Standards Committee added
operator<=>, known as the spaceship operator, to the working draft for what will eventually become C++20. This is an exciting new language feature for two reasons: it allows you to write one function to do all your comparisons where you used to have to write six, and it also allows you to write zero functions — just declare the operator as defaulted and the compiler will do all the work for you! Exciting times.
The paper itself presents many examples of how to implement the spaceship operator in various situations, but it left me with an unanswered question about a particular case — so I set out trying to figure out. This post is about the journey of how to implement
optional<T>. First, thanks to John Shaw for helping work through all the issues with me. And second, the resulting solution may not be correct. After all, I don’t even have a compiler to test it on. So if you think it’s wrong, please let me know (and please post the correct answer in this self-answered StackOverflow question).
First, the specs.
optional<T> has three categories of comparisons, all conditionally present based on the facilities of the relevant types:
optional<U>, where valid (6 functions).
U, where valid (12 functions). I’m skeptical of this particular use-case, but this post is all about implementing the spec.
nullopt_t(12 functions). This case is trivial to implement, since several of the operations are simply constants (e.g.
true). But, that’s still 12 trivial-to-implement functions.
In all cases, the semantics are that a disengaged optional is less than any value, but all disengaged values are equal. The goal is to take advantage of the new facilities that the spaceship operator provides us and reduce the correct load of 30 functions to just 3.
We’ll start with the
optional comparison. There are four cases to consider: both on, left on only, right on only, and both off. That leads us to our first approach:
The spaceship operator returns one of five different comparison categories:
weak_equality. Each of these categories has defined named numeric values. In the paper, the categories are presented in a way that indicates the direction in which they implicitly convert in a really nice way, so I’m just going to copy that image here (all credit to Herb Sutter):
Likewise, their table of values:
Just carefully perusing this table, it’s obvious that our first implementation is totally wrong.
strong_ordering has numeric values for
greater… but the rest don’t! In fact, there is no single name that is common to all 5. By implementing it the way we did, we’ve reduced ourselves to only supporting strong orderings.
So if we can’t actually name the numeric values, what do we do? How can we possibly do the right thing?
Here, we can take advantage of a really important aspect of the comparison categories: convertibility. Each type is convertible to all of its less strict versions, and each value is convertible to its less strict equivalents.
strong_ordering::greater can become
weak_equality::nonequivalent. And the way we can take advantage of this is to realize that we don’t really have four cases, we have two: both on, and not that. Once we’re in the “not” case, we don’t care about the values anymore, we only care about the bools. And we already have a way to do a proper 3-way comparison:
The shapeship operator for
bools gives us a
strong_ordering, which is convertible to everything. So that part is guaranteed to work and do the right thing (I encourage you to work through the cases and verify that this is indeed the case).
But this still isn’t quite right. The problem is actually
<=> (thanks, Captain Obvious?). You see, while
a < b is allowed to fallback to
a <=> b < 0, the reverse is not true.
a <=> b is not allowed to call anything else (besides
b <=> a). It either works, or it fails. By using the spaceship operator directly on our values, we’re actually reducing ourselves to only those modern types that support 3-way comparison. Which, so far, is no user-defined types. Moreover,
<=> doesn’t support mixed-integer comparisons, so even for those types that come with builtin spaceship support (that’s a fantastic phrase), we would effectively disallow comparing an
optional<int> to an
optional<long>. So, this operator in this particular context isn’t very useful.
So what are we to do? Re-implement 3-way comparison ourselves manually? Nope, that’s what the library is for! Along with language support for the spaceship operator, C++20 will also come with several handy library functions. The relevant one for us is
std::compare_3way(). This one will do the fallback: it prefers
<=>, but if not will try the normal operators and is smart enough to know whether to return
strong_equality. And it’s SFINAE-friendly. Which means for our purposes, we can just drop-in replace our too-constrained version with it:
And I think we’re done.
Now that we’ve figured out how to do the optional-vs-optional comparison, comparing against a value is straightforward. We follow the same pattern for the value-comparison case, we just need to know what to return in the case where the optional is disengaged. Semantically, we need to indicate that the optional is less than the value. Again, we can just take advantage that all the comparison category conversions just Do The Right Thing and use
We just replaced 12 functions (that, while simple, are certainly non-trivial to get right) with 10 lines of code. Mic drop.
All that’s left is the
nullopt_t comparison, which is just a simple comparison:
Putting it all together, and here’s what we end up with to cover all 30
Not bad for 25 lines of code?
Let me just reiterate that I’m not sure if this is the right way to implement these operators. But that’s the answer I’m sticking with until somebody tells me I’m wrong (which, if I am, please do! We’re all here to learn).
Needless to say, I’m very much looking forward to throwing out all my other comparison operators. Just… gotta wait a few more years.
Bonus level. Here’s what I think a comparison operator would look like for
std::expected<T, E>. The semantics here are that the values and errors compare against each other, if they’re the same. If they’re different types, the value is considered greater than the error. Although, for the purposes of this exercise, the specific semantics are less important than the fact that we get consistent semantics. And I think the right way to implement consistent semantics is:
common_comparison_category is a library metafunction that gives you the lowest common denominator between multiple comparison categories (which hopefully is SFINAE-friendly, but I’m not sure). The first if check handles the case where the value-ness differs between the two
expected objects. Once we get that out of the way, we know we’re in a situation where either both are values (so, compare the values) or both are errors (so, compare the errors). Just thinking of how much code you have to write today to accomplish the same thing makes me sweat…