14

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.

Is std::strong_ordering formally required to enforce a total order, or is the note just an informal explanation?

If a total order is required, is my implementation invalid because it breaks transitivity?

Improve this question
12
  • The note is just a note and not normative, because all the requirements for strong_ordering are the same as that for a total order in the mathematical sense. There does not have to be more normative text that makes them the same. Commented Feb 3 at 12:00
  • 1
    The more I look at the standard, the more I think that the transitivity property is not a subject. Thus defining strong_ordering as the same as total ordering was exaggerated. Commented Feb 3 at 12:21
  • @Oersted A strict weak ordering implies transitivity and a strong ordering is stronger than a weak ordering. Commented Feb 3 at 12:34
  • this answer thinks differently: stackoverflow.com/a/75770486/21691539. But, IMHO, it is not well-argued. It cites proposals (I found this one open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2830r6.html) where transitivity is mentioned but I can find it only in the algorithm and concept sections of the standard, which speaks of strict ordering. Commented Feb 3 at 12:34
  • @j6t: as I understand, strict_weak_order != weak_ordering though... Commented Feb 3 at 13:36

1 Answer 1

Reset to default
12

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.

[cmp.concept]/2:

 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]).

[concept.totallyordered]/1:

 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.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Sorry but were do you get that three_way_comparable implies transitivity and is required by std algorithm? As mentioned in the question comments, I could only find a Compare requirement that is, unfortunately, not linked to three_way_comparable concept.
@Barry eel.is/c++draft/cmp.concept#2.8 - "if Cat is convertible to strong_ordering, T models totally_ordered ([concept.totallyordered])."
@Oersted Three way comparable requires total order if the category is strong ordering. I included the text from the standard which ... literally just says that.
@Yakk-AdamNevraumont You know what, I missed that bullet. Which is particularly bad since I probably wrote that bullet.
@Oersted concepts can have semantic requirements. It's really dangerous to return std::strong_ordering from a non-transitive comparison. You satisfy std::three_way_comparable (all the syntax is there and correct), but don't model it (the semantic requirements are not met), so the compiler will admit uses that are ill-formed-no-diagnostic. res.on.requirements
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.