Implementing the Spaceship Operator for Optional

In November 2017, the C++ Standards Committee added operator<=>, known as the spaceship operator [P0515], 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 operator<=> for 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 [StackOverflow]).

First, the specs. optional<T> has three categories of comparisons, all conditionally present based on the facilities of the relevant types:

• optional<T> compares to optional<U>, where valid (6 functions).
• optional<T> compares to U, where valid (12 functions). I’m sceptical of this particular use-case, but this post is all about implementing the spec.
• optional<T> compares to nullopt_t (12 functions). This case is trivial to implement, since several of the operations are simply constants (e.g. operator>=(optional<T>, nullopt_t) is 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 current load of 30 functions to just 3.

We’ll start with the optional on 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 (Listing 1).

template <typename T>
class optional {
public:
  // from here on out, assuming that heading
  // exists ...

  template <typename U>
  constexpr auto operator<=>(
    optional<U> const& rhs) const
    -> decltype(**this <=> *rhs)
  {
    using R = decltype(**this <=> *rhs);
    if (has_value() && rhs.has_value()) {
      return **this <=> *rhs;
    } else if (has_value()) {
      return R::greater;
    } else if (rhs.has_value()) {
      return R::less;
    } else {
      return R::equal;
    }
  }
};
            

The spaceship operator returns one of five different comparison categories:

• strong_ordering
• weak_ordering
• partial_ordering
• strong_equality
• 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 as Figure 1 (all credit to Herb Sutter).

Figure 1

Likewise, their table of values is shown in Table 1 below.

Just carefully perusing this table, it’s obvious that our first implementation is totally wrong. strong_ordering has numeric values for less, equal, and 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_ordering::greater or
• partial_ordering::greater or
• strong_equality::nonequal or
• 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: <=>! (See Listing 2.)

template <typename U>
constexpr auto operator<=>(optional<U>
  const& rhs) const
  -> decltype(**this <=> *rhs)
{
  if (has_value() && rhs.has_value()) {
    return **this <=> *rhs;
  } else {
    return has_value() <=> rhs.has_value();
  }
}
            

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 built-in 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 and 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_ordering or strong_equality. And it’s SFINAE-friendly. Which means for our purposes, we can just drop-in replace our too-constrained version with it (see Listing 3).

template <typename U>
constexpr auto operator<=>(optional<U>
  const& rhs) const
  -> decltype(compare_3way(**this, *rhs))
{
  if (has_value() && rhs.has_value()) {
    return compare_3way(**this, *rhs);
  } else {
    return has_value() <=> rhs.has_value();
  }
}
            

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 strong_ordering::less (see Listing 4).

template <typename U>
constexpr auto operator<=>(U const& rhs) const
  -> decltype(compare_3way(**this, rhs))
{
  if (has_value()) {
    return compare_3way(**this, rhs);
  } else {
    return strong_ordering::less;
  }
}
            

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 (Listing 5).

constexpr strong_ordering operator<=>(nullopt_t ) const
{
  return has_value() ? strong_ordering::greater
                     : strong_ordering::equal;
}
            

Putting it all together, and Listing 6 is what we end up with to cover all 30 std::optional<T> comparisons.

template <typename T>
class optional {
public:
  // ...

  template <typename U>
  constexpr auto operator<=>(optional<U>
    const& rhs) const
    -> decltype(compare_3way(**this, *rhs))
  {
    if (has_value() && rhs.has_value()) {
      return compare_3way(**this, *rhs);
    } else {
      return has_value() <=> rhs.has_value();
    }
  }

  template <typename U>
  constexpr auto operator<=>(U const& rhs) const
    -> decltype(compare_3way(**this, rhs))
  {
    if (has_value()) {
      return compare_3way(**this, rhs);
    } else {
      return strong_ordering::less;
    }
  }

  constexpr strong_ordering
    operator<=>(nullopt_t ) const
  {
    return has_value() ? strong_ordering::greater
    : strong_ordering::equal;
  }
};
            

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 [StackOverflow] 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 as shown in Listing 7.

template <typename T, typename E>
class expected {
public:
  // ...
  template <typename T2, typename E2>
  constexpr auto operator<=>(expected<T2, E2>
    const& rhs) const
    -> common_comparison_category_t<
        decltype(compare_3way(value(),
          rhs.value())),
          decltype(compare_3way(error(),
          rhs.error()))>
  {
    if (auto cmp = has_value() <=>
        rhs.has_value(); cmp != 0) {
      return cmp;
    }
    if (has_value()) {
      return compare_3way(value(), rhs.value());
    } else {
      return compare_3way(error(), rhs.error());
    }
  }
};
            

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…

References

[P0515] ‘Consistent comparison’ (2017) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0515r3.pdf

[StackOverflow] ‘Implementing operator<=> for optional<T>’https://stackoverflow.com/questions/47315539/implementing-operator-for-optionalt

Barry Revzin I’m a C++ developer for Jump Trading, member of the C++ Standards Committee, also ‘Barry’ on StackOverflow. On the side, I’m also an avid swimmer and do data analysis for SwimSwam magazine. And take care of my adorable Westie and life mascot, Hannah.