ideas for proper_partial_ordering

[tobias-loew]

see text in PR

[frederick-vs-ja]

Consider a type, where the natural comparison is a partial order (e.g. a math. lattice, multi-dim Boolean algebra, other multi-dim spaces) and that order is provided via <=> to the user.

• then all the default Compare predicates for sorted containers are broken, unless std::less is specialized for that type with a total order
• and all the default Compare predicates for ranges algorithms are broken. (Fullstop! No way get around std::ranges::less invoking operator < .)

So, silently, all ranges Compare-based algorithms are broken, unless you plug-in your own Compare everywhere!

On most platforms, floating-pointer types can represent NaN, so they're such types. IMO these algorithms are not broken unless NaN is passed. Although we may need to improve the requirements for non-ranges algorithms, but implementations shouldn't need to change.

IMHO, there are two options to solve this problem:

1. adding a std::proper_partial_ordering type, which cannot be used by std::less and std::ranges::less, thus forcing compilation errors when container/ranges-algorithms try to use the default Compare.

2. additionally to 1., adding a customization point in std::ranges::less (and greater), where the user can supply a total order based on the type to compare.

I think we can add

enum class ordering_forcing_kind {
  disabled,
  weak,
  strong
};

template<class>
constexpr ordering_forcing_kind force_customized_ordering = ordering_forcing_kind::disabled;

and allow users to defined specializations for cv-unqualified object types.

Then make comparison functors switch to use std::strong_order if the ordering is forced to strong, which is possibly intendedly ill-formed. Same for weak.

[tobias-loew]

Thanks for your reply. The ordering_forcing_kind approach sounds like a good solution for me.

But a short note to:

On most platforms, floating-pointer types can represent NaN, so they're such types. IMO these algorithms are not broken unless NaN is passed. Although we may need to improve the requirements for non-ranges algorithms, but implementations shouldn't need to change.

This is the usual example, when people in the standard are talking about partial-orders. Of course, it is a partial order, but it has a very large linear ordered subset, and gives the wrong impression of what partial orders really are. (It implies something like: "a partial order is an order with a little defect, when left out yields a total order".) But there are partial orders, where just a few elements are in order (or even none: a set of points without any points in order is a partial order). For many mathematical applications the natural order on a cartesian product is the (partial) product-order and not the lexicographic.

[brevzin]

Did you mean to send me an email? Why is this a PR? Anyway, I disagree with the premise. std::sort on a range of float is not inherently "broken."

[tobias-loew]

Did you mean to send me an email? Why is this a PR? Anyway, I disagree with the premise. std::sort on a range of float is not inherently "broken."

Yes, wanted to contact you, but couldn't find your email address. I didn't want to say that std::sort on float is broken. When NaN is not used everything works fine. But for types like powersets or math. lattices, where < is a proper partial order, there are problems, when operator< is defined that way.