I am implementing a three-way comparison (operator<=>) for an enum class representing Rock-Paper-Scissors. My implementation compiles and returns std::strong_ordering, but I am unsure whether it meets the formal requirements for std::strong_ordering, particularly regarding transitivity.
Here is my code:
#include <compare>
enum class Hand { Rock, Paper, Scissors };
std::strong_ordering operator<=>(Hand a, Hand b) {
if (a == Hand::Paper && b == Hand::Scissors) return std::strong_ordering::less;
if (a == Hand::Scissors && b == Hand::Rock) return std::strong_ordering::less;
if (a == Hand::Rock && b == Hand::Paper) return std::strong_ordering::less;
if (a == b) return std::strong_ordering::equal;
return std::strong_ordering::greater;
}
This implementation introduces a cyclic comparison:
Paper < Scissors
Scissors < Rock
Paper > Rock, breaking transitivity.
I used std::strong_ordering as the return type, since any two values of type enum class Hand are compariable, and all equal values of this type are same.You can see that this code can be compile, and works well on judging the winner of the game. Of course, I can't put a series of values of this enum class into a sort function or
std::set, etc., which introduces an undefined behavior.
I noticed that the C++ draft standard (N4950, §17.11.2[cmp.categories.pre]/2) contains a note stating that "The type strong_ordering corresponds to the term total ordering in mathematics." However, since this is only a note, I could not find an explicit normative requirement in the main text that std::strong_ordering must always represent a total order, particularly the transitivity requirement.
So my questions are:
1. Is std::strong_ordering formally required to enforce a total order, or is the note just an informal explanation?
2. If a total order is required, is my implementation invalid because it breaks transitivity?
3. Would std::partial_ordering be a better choice for this kind of cyclic comparison?
Your <=> that returns the type std::strong_order does not have to model the concept totally-ordered, but it is a good idea for it to do so.
Ie, an empty program with such a <=> and no use of it is well-formed. Once you do almost anything with it, your program is no longer valid.
As an example, almost any use of a strong order in any algorithm written by someone else is going to require it modelling three-way-comparable, which in turn requires you to model totally_order, which in turn requires transitive comparisons.
Let a and b be lvalues of type const remove_reference_t<T>. T and Cat model three_way_comparable<T, Cat> only if
...
(2.8) if Cat is convertible to strong_ordering, T models totally_ordered ([concept.totallyordered]).
Given a type T, let a, b, and c be lvalues of type const remove_reference_t<T>. T models totally_ordered only if
...
(1.2) If bool(a < b) and bool(b < c), then bool(a < c).
Your <=> fails [concept.totallyordered]/1.2 as follows:
Let a be Rock, b be Paper, and c be Scissors. Rock < Paper, Paper < Scissors, thus to model totally_ordered Rock must be less than Scissors, which is false; so your type does not model totally_ordered.
As three-way-comparable when Cat is strong_ordering requires it to model totally_ordered, your <=> does not produce a valid three-way-comparable object.
To be more concrete, if you stick your class into a variant, <=> is only valid on that variant if your strong order models three_way_comparable which in turn requires a total order, which yours is not.
You are not required by the standard that your std::strong_order <=> be non-garbage; simply creating such a <=> does not result in undefined behavior. But every bit of code generation from std, be it a sorting algorithm or putting your type into a container, will presume that your <=> models three-way-comparable, which yours does not, which in turn will lead very rapidly to errors at best and UB at worst.
Making a <=> not model three-way-comparable is a bit like making operator-> do something unrelated to dereferencing a pointer. Legal, but almost always a bad idea.