c++ - Does std::strong_ordering in C++20 require a total order? - Stack Overflow

admin管理员组

文章数量:1310455

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?

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?

• c++
• language-lawyer
• c++20
• spaceship-operator

Share Improve this question Follow edited Feb 11 at 15:30 TylerH 21.1k7777 gold badges7979 silver badges112112 bronze badges asked Feb 3 at 11:18 yqZhang4480yqZhang4480 54222 silver badges88 bronze badges 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. – j6t 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. – Oersted Commented Feb 3 at 12:21
• @Oersted A strict weak ordering implies transitivity and a strong ordering is stronger than a weak ordering. – j6t Commented Feb 3 at 12:34
• this answer thinks differently: stackoverflow/a/75770486/21691539. But, IMHO, it is not well-argued. It cites proposals (I found this one open-std./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. – Oersted Commented Feb 3 at 12:34
• @j6t: as I understand, strict_weak_order != weak_ordering though... – Jarod42 Commented Feb 3 at 13:36

 |  Show 7 more comments

1 Answer 1

Sorted by: Reset to default 11

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.

本文标签： cDoes stdstrongordering in C20 require a total orderStack Overflow