The Spaceship Operator <=> (And Comparison In General)

Problem: Comparison Operators

Each type should either overload …

  • All 6: ==, !=, <, >, <=, >=

  • (In)equality: ==, !=

  • None

This much writing!

  • Shortcut: only < for occasional sorted container insertion

  • Though containers generally support external ordering

  • But: incomplete overloading (e.g. omit !=) is bad code

  • With most types, ordering is natural

Open question remain pre C++20

  • Strong vs. weak ordering?

  • When two objects of a type compare equal, can they be different?

  • …

Annoying: Occasional Container Insertion ⟶ operator<()

  • Manually define operator<()

code/key-op-less-annoying-less-missing.cpp
#include <set>
#include <cassert>

struct key
{
    unsigned id;
};

int main()
{
    std::set<key> my_keys;
    auto [_, inserted] = my_keys.insert({1});          // <-- error: no match for ‘operator<’
    assert(inserted);

    return 0;
}

  • ⟶ annoying and error-prone

code/key-op-less-annoying.cpp
#include <set>
#include <cassert>

struct key
{
    unsigned id;
    bool operator<(const key& rhs) const
    {
        return id < rhs.id;                            // <-- annoying (and error-prone)
    }
};

int main()
{
    std::set<key> my_keys;
    auto [_, inserted] = my_keys.insert({1});
    assert(inserted);

    return 0;
}

Annoying: Implementing All Six (<, >, <=, >=, ==, !=)

  • operator<() is rarely enough

  • User expectation: if objects are less-comparable, they should provide the full set

  • ⟶ Implement the other five in terms of <

  • ⟶ Very annoying

code/key-op-less-all-six-annoying.cpp
#include <cassert>

struct key
{
    unsigned id;
    bool operator< (const key& rhs) const
    {
        return id < rhs.id;
    }
    bool operator==(const key& rhs) const { return !(*this < rhs) && !(rhs < *this); }
    bool operator!=(const key& rhs) const { return !(*this == rhs); }
    bool operator<=(const key& rhs) const { return *this < rhs || *this == rhs; }
    bool operator>=(const key& rhs) const { return !(*this < rhs); }
    bool operator> (const key& rhs) const { return rhs < *this && *this != rhs; }
};

int main()
{
    key k1{42};
    key k2{666};

    assert(k1 < k2);
    assert(k1 == k1);
    assert(k1 != k2);
    assert(k1 <= k1);
    assert(k1 <= k2);
    assert(k2 >= k2);
    assert(k2 >= k1);
    assert(k2 > k1);

    return 0;
}

Annoying: Even Simple (In)Equality Comparison

  • Two-dimensional point

  • Expectation: ==, !=

  • Even that is annoying

code/point-equality-annoying.cpp
#include <cassert>

struct point
{
    int x, y;

    bool operator==(const point& rhs) const
    {
        return x == rhs.x && y == rhs.y;
    }
    bool operator!=(const point& rhs) const { return !operator==(rhs); }
};

int main()
{
    point p1{1,2};
    point p2{3,4};

    assert(p1 == p1);
    assert(p1 != p2);

    return 0;
}

C++20 To The Rescue: (In)Equality

Rationale

  • C++ has always generated memberwise copy-constructor and assignment operator

  • Why not do something similar with (in)equality == and !=

Solution

  • == implemented, or simply requested = default

  • ⟶ != comes for free as !(a==b)

code/point-equality-default.cpp
#include <cassert>

struct point
{
    int x, y;

    bool operator==(const point& rhs) const = default; // <-- cool!
};

struct compatible_point
{
    int x, y;

    operator point() const
    {
        return {x,y};
    }
};

int main()
{
    point p{1,2};
    compatible_point cp{1,2};

    assert(p == cp);                                   // <-- p.operator==(cp), ok
    assert(cp == p);                                   // <-- cp.operator==(p), does not exist
    
    return 0;
}

Pythonicity: Comparing Compatible Types

  • Member operator==(const compatible_point& cp) converts cp to point

  • But not this, as in cp == p

  • Pythonic goodie: reverse parameters, and try again. (This is Python’s __eq__() method, see here)

code/point-equal-compatible-type.cpp
#include <cassert>

struct point
{
    int x, y;
    bool operator==(const point& rhs) const = default;
};

struct compatible_point
{
    int x, y;
    operator point() const { return point{x,y}; }
};

int main()
{
    point p{1,2};
    compatible_point cp{1,2};

    assert(p == cp);                                   // <-- rhs converted to point, old-style
    assert(cp == p);                                   // <-- magic: lhs and rhs reversed

    return 0;
}

Every == Has Its !=

  • A type may define multiple operator==() (e.g. to compare with unrelated types)

  • ⟶ each has their operator!=() automatically

  • … with the same Pythonic semantics just described (reversing parameters until it sees fit)

code/key-equality-comparison-with-unsigned.cpp
#include <cassert>

struct key
{
    unsigned id;
    bool operator==(unsigned rhs) const
    {
        return id == rhs;
    }
};

int main()
{
    key k{42};
    assert(k == 42);                                   // <-- explicitly defined in type
    assert(k != 666);                                  // <-- automatic !operator==()
    assert(42 == k);                                   // <-- freaky
    assert(666 != k);                                  // <-- freaky
    return 0;
}

Spaceship Operator <=>

  • a==b (e.g.) defines a relationship

  • a<b defines another relationship

  • …

  • All definitions should collaborate to implement one bigger relationship

  • ⟶ Ordering

  • operator<=>() return the entire relationship

  • ==, !=, <, >, <=, >= are then automatically derived

  • strcmp() on steroids

Ordering Relationships

operator<=>() returns one of the following ordering types:

  • std::strong_ordering: implies that the values are indistinguishable (i.e. if a == b, then f(a) == f(b)).

  • std::weak_ordering: allows equal, distinguishable values, but doesn’t permit uncomparable values.

  • std::partial_ordering: allows uncomparable values (i.e. a < b, a > b and a == b all return false).

To me, std::strong_ordering seems like the one preferred relationship to aim for.

Straightforward operator<=>()

  • unsigned implements std::strong_ordering

  • ⟶ can be used in = default spaceship of surrounding type

code/key-spaceship-trivial-default.cpp
#include <compare>
#include <cassert>

struct key
{
    unsigned id;
    std::strong_ordering operator<=>(const key& rhs) const = default;
};

int main()
{
    key k1{42};
    key k2{666};

    assert(k1 < k2);
    assert(k1 == k1);
    assert(k1 != k2);
    assert(k1 <= k1);
    assert(k1 <= k2);
    assert(k2 >= k2);
    assert(k2 >= k1);
    assert(k2 > k1);

    return 0;
}

Compound Datatypes (Handwritten)

  • Typical problem: comparable type has multiple members

  • ⟶ E.g. composite primary key in databases

  • Manual implementation follows: primary first, then secondary

  • (All the five others ⟶ see here)

code/key-spaceship-compound-handwritten.cpp
#include <compare>
#include <cassert>

struct key
{
    unsigned primary;
    unsigned secondary;
    bool operator<(const key& rhs) const
    {
        if (primary != rhs.primary)
            return primary < rhs.primary;
        else
            return secondary < rhs.secondary;
    }
};

int main()
{
    key k1{42, 1};
    key k2{42, 2};
    key k3{666, 1};

    assert(k1 < k2);
    assert(k1 < k3);

    return 0;
}

Compound Datatypes: = default Spaceship

  • = default: applies requested ordering to members, in declaration order

code/key-spaceship-compound-default.cpp
#include <compare>
#include <cassert>

struct key
{
    unsigned primary;
    unsigned secondary;
    std::strong_ordering operator<=>(const key& rhs) const = default;
};

int main()
{
    key k1{42, 1};
    key k2{42, 2};

    assert(k1 < k2);
    assert(k1 == k1);
    assert(k1 != k2);
    assert(k1 <= k1);
    assert(k1 <= k2);
    assert(k2 >= k2);
    assert(k2 >= k1);
    assert(k2 > k1);

    return 0;
}

Some Types Have A Weaker Ordering Than std::strong_ordering

  • double only supports std::partial_ordering

  • NaN does not compare well

  • == comparison is not so well defined too

  • Many other types too

code/key-spaceship-compound-double.cpp
#include <compare>
#include <cassert>

struct key
{
    unsigned primary;
    double secondary;                                  // <-- no std::string_ordering
    std::strong_ordering operator<=>(const key& rhs) const = default;
};

int main()
{
    key k1{42, 1};
    key k2{42, 2};
    assert(k1 < k2);                                   // <-- error: three-way comparison of ‘key::secondary’ has type ‘std::partial_ordering’, which does not convert to ‘std::strong_ordering’
    return 0;
}

Pointer Members: std::strong_ordering, But Unusable

  • secondary is const char*

  • Has std::strong_ordering, but compares pointer values

  • = default not correct

Fiasco (see P1185R2)

  • Implement <=>. This does NOT create == (and !=)!

  • Implement ==

code/key-spaceship-compound-pointer.cpp
#include <compare>
#include <cstring>
#include <cassert>

struct key
{
    unsigned primary;
    const char* secondary;

    std::strong_ordering operator<=>(const key& rhs) const
    {
        if (std::strong_ordering cmp = primary <=> rhs.primary; cmp != std::strong_ordering::equal)
            return cmp;

        // .primary are equal -> fallback to strcmp .secondary
        int cmp1 = std::strcmp(secondary, rhs.secondary);
        if (cmp1 < 0)
            return std::strong_ordering::less;
        else if (cmp1 == 0)
            return std::strong_ordering::equal;
        else
            return std::strong_ordering::greater;
    }

    bool operator==(const key& rhs) const
    {
        return !(*this < rhs) && !(*this > rhs);
    }
};

int main()
{
    key k1{42, "a"};
    key k2{42, "b"};
    key k3{43, "b"};

    assert(k1 < k2);
    assert(k1 == k1);
    assert(k1 != k2);
    assert(k1 <= k1);
    assert(k1 <= k2);
    assert(k2 >= k2);
    assert(k2 >= k1);
    assert(k2 > k1);

    assert(k1 < k3);
    assert(k2 < k3);

    return 0;
}