1. Revision History

r1: Incorporated feedback from EWG meeting in Rappersville.
The feedback was:

Remove the floating point exception (bullet 1.1) as R0 recommended, since Unicode strings, etc., are a possible rationale.

Do not propose propose making existing
functions "customization points" (as used in [P0551R3]).* _order 
Add a new
customization point, along with a bikeshedding section on its actual name, with the behaviour:default_order 
It has the IEC 559 behavior from bullet 1.1 of
strong_order 
It is defined for all (other) floatingpoint types; it is implementationdefined whether it is consistent with the partial order from the comparison operators. (Implementations should do this.)

It is a customization point (à la [P0551R3]).


Investigate the possibility of adding Lawrence’s weak order (from [P0100R2]) for floatingpoint numbers (which did not make it in with spaceship).
2. Status of this paper
This paper has been seen by LEWG, provided feedback, and reworked. It is ready to be seen again by LEWG.
3. Problem Description
This paper is a proposal to amend a library extension that has been voted into the working draft as part of [P0768R1].
This paper proposes a new ordering customization point for possibly nonsemantic strong orderings, which should be equal to
for stronglyordered types, and can be customized to represent an arbitrary total order for types that do not have a semantic ordering.
The current C++ standard does not have an explicitly designated customization point for providing a default ordering. Elements of Programming uses
for this purpose, as does the global order for pointers; but with the introduction of
,
is missing features, such as computing equality without calling it twice. It has also failed to get adoption for this purpose throughout the years, perhaps exactly due to the missing features.
Note: see §4 Exposition: On Natural and Default Orderings for the definitions and discussion of orderings.
The wording of point 1.1 of the
algorithm suggests that
is finally this missing customization point for specifying a default ordering for types whose natural ordering is not strong and total, since it does exactly that for the iec559 types.
The issue is that the rest of the points make this function rather unsuitable for use as a customization point, since the language explicitly makes it not SFINAEfriendly. In the event that it cannot be synthesized, it is marked as deleted, and not as "shall not participate in overload resolution".
LEWG has expressed a strong preference to introducing a new customization point for such nonsemantic strong orderings, and clarified that
should not be a customization point.
4. Exposition: On Natural and Default Orderings
There are obviously many reasons for sorting. However, this paper is chiefly concerned with the division between the natural ordering and the default total ordering as required for Regular types by Stepanov and McJones in their seminal work Elements of Programming (page 62, section 4.4).
The natural ordering is the ordering that makes semantic sense for a type. This is the ordering that
and its library extensions are tailormade for: not every type is ordered (or even equalitycomparable), and when a type supports an ordering, it might be strong, partial, or weak.
We use these orderings when we need them to make sense  heaps, scheduling tasks by topological sorts, various displays for users, etc. Not all value types have a natural ordering, because not all types are ordered. The Gaussian integers are one such type.
The default ordering, from Elements of Programming is the finest ordering (transitive antisymmetric antireflexive relation) that a type admits, with its equality is defined by valuesubstitutability (unequal elements must be ordered); it is always strong and total, and might not make semantic sense.
According to Elements of Programming, every Regular type should provide a default ordering.
A type with a default ordering is far more useful than one without; ordering enables the use of treebased containers (i.e.
,
), and algorithms based on sorted data (
, the various set algorithms,
, and the various versions of binary search)  and this is just the tip of the iceberg. The only requirement for the above is having a total strong ordering  what the ordering means is utterly irrelevant, we only require a global order relation.
The lexicographic ordering of the Gaussian integers is a good example of a default ordering.
Another excellent example is
 its various
s and infinities are not ordered, which is the reason its natural ordering is not suitable as a default ordering. However, iec559 defines a total strong ordering for those values, thus enabling the uses outlined above.
5. Status Quo
For reference, the current specification for the
algorithm is as follows:
template < class T > constexpr strong_ordering strong_order ( const T & a , const T & b );

Effects: Compares two values and produces a result of type
:strong_ordering 
If
is true, returns a result of typenumeric_limits < T >:: is_iec559
that is consistent with thestrong_ordering
operation as specified in ISO/IEC/IEEE 60559.totalOrder 
Otherwise, returns
if that expression is wellformed and convertible toa <=> b
.strong_ordering 
Otherwise, if the expression
is wellformed, then the function shall be defined as deleted.a <=> b 
Otherwise, if the expressions
anda == b
are each wellformed and convertible toa < b
, returnsbool
whenstrong_ordering :: equal
isa == b true
, otherwise returns
whenstrong_ordering :: less
isa < b true
, and otherwise returns
.strong_ordering :: greater 
Otherwise, the function shall be defined as deleted.

6. Proposal
6.1. Introduce a new customization point for an arbitrary total ordering
Introduce a new algorithm, with the name
(but see §7 Name of The Default Order Algorithm), with the following semantics:
Let
be a type, and
and
be values of type
(as if
and
were
):

If wellformed, the expression
shall return an object convertible todefault_order ( a , b )
.strong_ordering 
shall be a designated customization point in the sense of [P0551R3].default_order 
If the expression
is wellformed, then the expressionstrong_order ( a , b )
is wellformed.default_order ( a , b ) 
If not explicitly specialized for a type
andT
is wellformed, the expressionstrong_order ( a , b )
shall return the result of the expressiondefault_order ( a , b )
. (Note: this means thatstrong_order ( a , b )
defaults todefault_order
if available for the type.  end note.)strong_order
6.2. Move the iec559 treatment (point 1.1) from strong_order
to default_order
Since this paper adds an explicit customization point for a nonsemantic total order on any type, the exception for iec559 floatingpoint types can now be implemented by explicitly providing an implementation for the
customization point for those types.
The concrete proposal is as follows:

remove point 1.1 of the
algorithm, which removes the exception for iec559 types.strong_order 
add a provision to
default_order 
if
is( bool ) numeric_limits < T >:: is_iec559 true
, the expression
returns a result of typedefault_order ( a , b )
that is consistent with thestrong_ordering
operation as specified in ISO/IEC/IEEE 60559.totalOrder

Remark: libraries are encouraged to provide implementations of this customization point for their userdefined types, especially if the
for the type does not provide a
, to enable possibly nonsemantic total orderings over their entire domain. The use of implementations of this customization point that do not define a strict total order render the program illformed (no diagnostic required).
7. Name of The Default Order Algorithm
The new customization point that exposes an arbitrary order for any type that cares to provide one needs a name. This paper suggests a 5way poll to LEWG on the following options:
7.1. default_order

Pros:

it is what Elements of Programmming calls it, apriori giving it wide recognition

it is reasonably short

the name is semantically netural.

does not imply that the order has any meaning past strong and total (eg. "lexicographic")


Cons:

it implies neither that it is total, nor that it is strong, despite the requirement it be both.

is the favorite of the paper author, as well as most of the reviewers of this paper.
7.2. total_order

Pros:

communicates the totality of the order

is the nametotalOrder
chose for the order over floating point types that implement these semanticsISO / IEC / IEEE 60559 
it is reasonably short


Cons:

does not imply it is a strong order

at least to the author’s mind, vaguely implies semantics past strong and total, which might not be the case.

7.3. arbitrary_order

Pros:

clearly implies it might not be anything past strong and total


Cons:

implies neither that it is total, nor that it is strong

very vague

sounds slightly derogatory for a facility that is to be used mostly by critical algorithms and data structuers

7.4. default_strong_order

Pros:

clear

roughly in line with Elements of Programming


Cons:

very long for a facitlity that will be used for inline calls to
andsort unique 
still not clear it is total

7.5. default_total_order

Pros:

clear

roughly in line with iec559 and Elements of Programming


Cons:

very long for a facitlity that will be used for inline calls to
andsort unique 
still not clear it is strong

8. On Compatibility Between the Natural and Default Orderings
Elements of Programming specifies that for types where the natural and default orderings differ, the default ordering should be finer than the natural one: that is, if
and
are comparable and compare unequal under
, the default order produces the same result (less or greater).
It is the opinion of the author that requiring this in the language of the standard library as a mandatory semantic constraint seems like a bad idea.
For instance, if one takes the Gaussian integers ordered by the Manhattan distance to zero (sum of absolute values of the two components), the compatible total order (a lexicographic ordering of every equivalence class) is far slower to compute than the simple lexicographic one.
Furthermore, if needed, a finer compatible total order can always be achieved on the fly by comparing with the natural order first: if the result is
or
, keep the result; otherwise, fall back on the default ordering.
9. Why not just make strong_order
a customization point?
Main reasons:

it would inhibit providing both a natural (
,<=>
) (and possibly slow) and a default (fast) order for a typestrong_order 
the committee guidance strongly preferred this option, as it keeps the meaning of
fixed (since it is not a customization point)strong_order 
it is less surprising if the order algorithms that are related to order types by name (
weak_order
,weak_ordering
partial_order
,partial_ordering
strong_order
) had the same specification, while a fourth customization point that isn’t related by any of them by name serves as the customization point for default order.strong_ordering
It is notable that this was the direction suggested by the orginal paper, but the committee rejected it.
10. Proposed Wording
From section 24.x.4, Comparison Algorithms [cmp.alg], under
:
numeric_limits < T >:: is_iec559
is true, returns a result of type strong_ordering
that is consistent with the totalOrder
operation as specified in ISO/IEC/IEEE 60559.
(1.2) Otherwise, returns
After 24.x.4 paragraph 3,
, add:

template < class T > constexpr strong_ordering default_order ( const T & a , const T & b );
4. Effects: (4.1) if
is true, returns a result of typestd :: numeric_limits < T >:: is_iec559
that is consistent with thestrong_ordering
operation as specified in ISO/IEC/IEEE 60559.totalOrder  (4.2) Otherwise, returns
if that expression is wellformed and convertible tostrong_order ( a , b ) strong_ordering  (4.3) Otherwise, this function shall not participate in overload resolution.
 (4.1) if
 5. Remarks: this function is a designated customization point ([namespace.std]).
Under
>
, insert declaration:
template < class T > constexpr strong_ordering default_order ( const T & a , const T & b );
11. Acknowledgments
I would like to thank

Roger Orr for bringing this to my attention;

Thomas Köppe for his valuable comments, review, and most of all some extremely clear and laconic wording;

Sam Finch for thoroughly breaking my examples, some example code, great substantive comments, and pointing out that the current definition actually breaks types that define a partiallyordered set of comparison operators;

Richard Smith for further fixing my example in light of Concepts, and example code.

Herb Sutter and Walter Brown for providing guidance on customization points.

Louis Dionne for great comments on the structure of the paper and how to bring the focus where it needs to be;

Walter Brown for representing the paper at committee meetings when I could not make it in person, and guidance with direction;

Herb Sutter for his comments and support for getting ordering right.
And, again, a special thankyou to Walter Brown, who, with his final lightning talk in Bellevue, reminded me to remember whose shoulders I’m standing on.
Thank you all!
Appendix A: Proof strong_order
is not a valid customization point
Say we have a template struct representing the Gaussian integers, with a natural order defined by the Manhattan distance from
. This struct still defines a
to model Regular.
Note: The Regular above refers to the Elements of Programming concept, not the ISO C++ Regular, which is weaker.
Note: There is no natural order on Gaussian integers, but humor this example, please.
namespace user { template < typename T > struct gaussian { static_assert ( std :: is_integral_v < T > ); T re ; T im ; constexpr std :: strong_equality operator == ( gassian const & other ) const { return re == other . re && im == other . im ; } constexpr std :: weak_ordering operator <=> ( gaussian const & other ) const { return ( * this == other ) ? std :: weak_ordering :: equal : ( abs ( * this ) == abs ( other )) ? std :: weak_ordering :: equivalent : abs ( * this ) <=> abs ( other ); } friend constexpr T abs ( gaussian const & ) { using std :: abs ; return abs ( re ) + abs ( im ); } friend constexpr std :: strong_ordering strong_order ( gaussian const & x , gaussian const & y ) { // compare lexicographically return std :: tie ( x . re , x . im ) <=> std :: tie ( y . re , y . im ); } }; }
Consider a transparent ordering operator for
:
struct strong_less template < typename T , typename U > bool operator ()( T const & x , U const & y ) { using std :: strong_order ; // use ADL return strong_order ( x , y ) < 0 ; } using is_transparent = std :: true_type ; };
Also say we had a type with an implicit conversion to our
:
template < typename T > struct lazy { std :: function < T () > make ; operator T () const { return make (); } };
This function now fails to compile, because the chosen
is deleted.
bool exists ( lazy < gaussian < int >> const & x , std :: set < gaussian < int > , strong_less > const & in ) { /* imagine this being a template in both parameters  it’s pretty normal */ return in . count ( x ); }
The stdprovided
is deleted because it cannot be synthesized from
's
. The reason it is chosen over the friend function, however, is because the standard template matches better than the friend which would require an implicit conversion.
If the stdprovided
did not participate in overload resolution, however, this example would work just fine.