Does std::set work correctly with a type that compares as std::partial_ordering?

Question

I came across this when defaulting the three-way-comparison operator (spaceship operator).

Let's consider this small example:

#include <set>
#include <limits>

struct A {
    float x;
    auto operator<=>(A const& other) const = default; // will be std::partial_ordering
};

int main()
{
    std::set<A>{ A{.x = std::numeric_limits<float>::quiet_NaN()}, A{.x = 1.f} };
}

Here we have a struct A that has one member of type float and defaults the <=> operator. Due tot he float member, the return type of the <=> operator will be std::partial_ordering. Partial ordering allows the category std::partial_ordering::unordered for elements that cannot be put into a specific order relative to other elements. For float this would affect nan for example. Any comparison of a float to nan will yield false.

Now, containers like std::set order their elements for being able to do binary search. For this they basically do a < comparison. Wouldn't this be broken for any type defining a partial ordering? In the example above, I can create a set of A and it compiles just fine. This seems like a pitfall to me because I assume that as soon as an element is inserted into the set that yields std::partial_ordering::unordered, the ordering inside the set would basically be broken, and various operations on the set would just cease to work correctly. Is my assumption correct?

Now, I know that it is possible in C++ to actually compare floats using a strong ordering. For this the function std::strong_order exists. So to fix the code, I could manually implement the three-way-comparison operator like this:

struct A {
    float x;
    auto operator<=>(A const& other) const{
        return std::strong_order(x, other.x);
    }
};

For this exmaple this is easy. But for larger structs/classes we are basically back to having to manually write comparisons that check member by member. Is there any way to achieve this comparison behaviour while still being able to default the spaceship operator? (without writing a wrapper class for float that offers strong order comparison)

tl;dr: To my understanding, set::set requires a strict weak ordering to work correctly. Still, I can construct a set using an element type that only offers a partial_ordering. This seems prone to causing bugs.

The example code is here, in case you're interested: https://godbolt.org/z/q4a95czTr

Answer 1

Wouldn't this be broken for any type defining a partial ordering?

No, not necessarily. I'm going to use float as the canonical example of a type with partial ordering, but the argument here applies to any partially ordered type.

std::set<float>, for instance, is not an inherently broken type. std::set<float>{1.f, 2.f, 3.f} will do exactly what you want, for instance. Indeed, it will do what you want for any floats you put into it... as long as they are not NaN.

There are really two approaches to this problem:

• you could put it in the type system, requiring that <=> yields at least weak_ordering, thus rejecting std::set<float>
• you could put it in the value system, and say it's undefined behavior if you have a partial ordering that compares as unordered. With <=>, if a <=> b is valid and yields a partial_ordering, you can assert that it's not unordered. That is, an operation is defined on a domain of values - not necessarily on every possible value in the type - and an algorithm is valid as long as the provided values are elements of the domain on which the operation is defined.

Rust does it the former way (which requires manually providing a comparison operation if you want to do something like sort a Vec<f32> - where that comparison probably just panics in the unordered case), and C++ has always done it the latter way - std::set<float> and sorting a std::vector<float> have always been valid in general, just with the precondition that NaN is not present in those containers (i.e. NaN is outside of the domain of the comparison).

I'm not sure that one approach is necessary better than the other. Rust's approach requires you to explicitly handle the unordered case, which is more tedious if you just don't have NaNs. In some sense, the C++ approach is more bug prone - since the unordered case won't be typically handled by simply aborting the program (although nothing stops you from writing an equivalently-buggy comparison in the Rust model).