How can I synthesize a C++20 three-way comparison from two-way comparisons?

Raymond Chen

The C++20 three-way comparison operator <=> (commonly nicknamed the spaceship operator due to its appearance) compares two items and describes the result. It’s called the three-way comparison because there are five possible results: less, equal, equivalent, greater, and unordered.

Yeah, the name is kind of weird.

It’s called the three-way comparison because in other languages, the equivalent operator has three possible results: less, equal, and greater. C++20 expands the set of possible results but kept the old name. (Sound familiar?)

Ordering Results
strong ordering less equal equivalent greater  
weak ordering less equivalent greater  
partial ordering less equivalent greater unordered

Each of the orderings can convert to the one below it, using the conversions given by the chart.

The strong ordering distinguishes between items being equal (identical and interchangeable) and equivalent (not interchangeable but close enough for some purpose). For example, two instances of the same string "hello" are equal, in that they represent the same string and are fully interchangeable. On the other hand, two people with the same security clearance are equivalent from a security perspective (they have access to the same things), but they are not equal (they are nevertheless different people).

When sorting, you are usually interested in equivalence, but when searching you might be interested in equality. (I’m looking for Bob, not just anybody with the same security clearance as Bob.)

Suppose you have an object from a class library that predates C++20 and doesn’t support three-way comparison. You want your code to be able to take advantage of the three-way comparison should the library be updated but fall back to two-way comparison in the meantime. In other words, you want to take advantage of three-way comparison if available.

Fortunately, you don’t have to write all that SFINAE nonsense, because somebody else has done it for you: std::tuple.

Tuples have the bonus property of supporting the three-way comparison operator, even if the underlying types do not. In the case where they do not, they will synthesize a three-way comparison from the two-way comparisons.

if a < b return less
else if a > b return greater
otherwise return equivalent

So we can just wrap the objects inside a std::tuple and compare the tuples. To avoid unnecessary copies, we can wrap them as references, or use forward_as_tuple which always uses references.

std::weak_ordering
compare_3way_via_tuple(T const& a, T const& b)
{
    return std::forward_as_tuple(a) <=>
           std::forward_as_tuple(b);
}

It turns out that there’s already a pre-made function that does something very similar: std::compare_weak_order_fallback also synthesize a missing three-way comparison, but it uses a different algorithm from tuples:

if a == b return equivalent
else if a < b return less
otherwise return greater

Tuples use a different algorithm from std::compare_weak_order_fallback. Which one is better? Why are they different?

I suspect that tuples use a different algorithm because tuple ordering comes from C++11, which predates three-way comparison. Back in those days, the comparison operators was used mostly for sorting and other ordered-sequence type algorithms. And those algorithms require only that the objects support the < operator. Therefore, tuples have to make do with only the < operator.

On the other hand, std::compare_weak_order_fallback was born into the world of three-way comparisons, so it has more liberty to take dependencies on things beyond just the < operator.

If you know that the underlying object supports ==, then my guess is that std::compare_weak_order_fallback is better, because == testing tends to be faster than < testing. For example, comparing two strings for equality can short-circuit if the strings are different lengths. This shortcut is not available for less-than comparison.

7 comments

Discussion is closed. Login to edit/delete existing comments.

  • Stuart Ballard 0

    There’s clearly a tradeoff of performance vs accuracy here, but wouldn’t the most you really want would be

    bool is_partial = false; // Indicates whether to return equivalent or unordered if no comparison operator returns true
    
    if (a == b) {
      return equal;
    } else if (a > b) {
      return greater;
    } else if (b > a) { // Account for the possibility of no operator <
      return less;
    } else {
      return is_partial ? unordered : equivalent;
    }

    From my limited understanding of C++ which mainly comes from following Raymond’s blog and being fascinated by programming language design, I would guess you could use templates to automatically add a spaceship operator to any type that has == and > operators. Is that possible, or is there a language rule that prevents it?

    • 紅樓鍮 0

      …you could use templates to automatically add a spaceship operator to any type that has == and > operators.

      My understanding is that Raymond wants to use an existing operator<=> if it’s available, or live with the old comparison operators otherwise. If an operator<=> already exists, redefining it would be an error.

      • Stuart Ballard 0

        Ahh, I was imagining it like C#, where it’s often possible for multiple implementations of the same thing to exist and the compiler will choose the most specific match. I thought it would be perfectly allowable for a definition from a template to co-exist with one on the type itself, and that the compiler would prefer the latter when it exists.

        Could SFINAE be used to make the template only valid on types that don’t already have a spaceship operator?

        • 紅樓鍮 0

          Ah, if you mean a blanket definition of

          template <typename T>
          std::weak_ordering operator<=>(const T &, const T &)
              requires { /* ... */ };

          then I guess yeah, it is possible.

  • 紅樓鍮 0

    Comparing two std::strings for equality can also be a single SIMD operation if both strings are short, assuming that short string optimization applies mandatorily, that std::string is sufficiently aligned, and that bytes that do not currently hold live chars are kept 0 (or any other invariant value, maybe). Similarly, equality comparison for non-short strings can also be effectively SIMD-accelerated if heap allocation for std::string is both sufficiently aligned and subject to the same zero-padding invariant (at least in the last SIMD word that holds at least one live char).

    Bonus chatter: Consequently, comparing std::string_views has the potential to be vastly more inefficient than comparing std::strings, because std::string_view loses both alignment and padding information completely.

    Bonus bonus chatter: On a second thought, apparently comparison for less-than can also be SIMD-accelerated, subject to the same memory alignment and zero-padding requirements, if the processor supports comparison of unsigned integers in big endian.

    • Sukru Tikves 0

      You’d need to compare a lot of strings to need these kinds of micro optimizations.

      By then, you would probably use some sort of indexing, and hashing mechanism to avoid string comparisons anyway.

    • Adam Rosenfield 0

      The assumption that non-live chars are kept at 0 is not going to be valid. That would require e.g. the `resize()` and `erase()` methods to zero out data past the end-of-string when shrinking a string. Even without that assumption, though, it’d still be possible to have a SIMD-accelerated implementation, but you’d just need a bit of extra logic to handle that edge case, which would reduce the performance a bit.

      Microoptimizing string comparison is a complex task. If you look at the glibc implementation of strcmp(), it’s over 2000 lines of optimized assembly to handle all of the different edge cases, using SIMD when possible.

Feedback usabilla icon