why is there no ordering that implies substitutable, disallows incomparable?

Question

The standard library defines weak ordering, partial ordering and strong ordering. these types define semantics for orderings that imply 3 of the 4 combinations of implying/not implying substitutability (a == b implies f(a) == f(b) where f() reads comparison-related state) and allowing/disallowing incomparable values (a < b, a == b and a > b may all be false).

I have a situation where my three-way (spaceship) operator has the semantics of equality implies substitutability, but some values may be incomparable. I could return a weak_ordering from my three-way comparison, but this lacks the semantic meaning of my type. I could also define my own ordering type, but I am reluctant to do that without understanding why it was omitted.

I believe the standard library's orderings are equivalent to the mathematical definition of weak ordering, partial ordering and total ordering. however, those are defined without the notion of substitutability. Is there a mathematical ordering equivalent to the one I am describing? Is there a reason why it was omitted from the standard?

Answer 1

It's not entirely clear from the original paper why the possibility of a "strong partial order" wasn't included. It already had comparison categories that were themselves incomparable (e.g., weak_ordering and strong_equality), so it could presumably have included another such pair.

One possibility is that the mathematical notion of a partial order actually requires that no two (distinct) elements are equal in the sense that a ≤ b and b ≤ a (so that the graph induced by ≤ is acyclic). People therefore don't usually talk about what "equivalent" means in a partial order. Relaxing that restriction produces a preorder, or equivalently one can talk about a preorder as a partial order on a set of equivalence classes projected onto their elements. That's truly what std::partial_ordering means if we consider there to exist multiple values that compare equivalent.

Of course, the easy morphism between preorders and partial orders limits the significance of the restriction on the latter; "distinct" can always be taken to mean "not in the same equivalence class" so long as you equally apply the equivalence-class projection to any coordinate questions of (say) cardinality. In the same fashion, the standard's notion of substitutability is not very useful: it makes very little sense to say that a std::weak_ordering operator<=> produces equivalent for two values that differ "where f() reads comparison-related state" since if the state were comparison-related operator<=> would distinguish them.

The practical answer is therefore to largely ignore std::weak_ordering and consider your choices to be total/partial ordering—in each case defined on the result of some implicit projection onto equivalence classes. (The standard talks about a "strict weak order" in the same fashion, supposing that there is some "true identity" that equivalent objects might lack but which is irrelevant anyway. Another term for such a relation is a "total preorder", so you could also consider the two meaningful comparison categories to simply be preorders that might or might not be total. That makes for a pleasingly concise categorization—"<=> defines preorders; is yours total?"—but would probably lose many readers.)