1. Revision History
1.1. R1: Incorporated feedback from LEWG 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 "customisation points" (as used in [P0551R3]).* _order 
Add a new
customisation 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 customisation 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).
1.2. R2: Incorporated feedback from LEWG meeting in San Diego, merged with [P0863R1]
Feedback in San Diego was:

We want to solve
for not obviously comparablestd :: set < T >
(0/6/4/1/1).T 
We want to solve
for not obviously hasheablestd :: unordered_set < T >
. (Out of scope of this paper)T 
We need to adress the fact that containers need to provide specializations of
if it is a customisation point.strong_order 
We want
to be the customisation point (Herb’s proposed poll)  never taken.strong_order
2. Status of this paper
R2 of this paper is a merge of its R1 and Jeff Snyder’s [P0863R1], and is synchronized with Barry Revzin’s [D1186R1]. It incorporates all feedback for R0 and R1, and presents a coherent design for the library components of
.
3. Problem Description
This paper is a proposal to amend the comparison algorithms that have been voted into the working draft as part of [P0768R1].
As worded, the
comparison algorithm provides:

a strong ordering for some types that do not have it provided by
(IEC559 floating point types),<=> 
a way of generating a value of type
by falling back to thestrong_ordering
and==
operators if<
is not callable or does not result in a<=>
.strong_ordering
However, the authors of this paper and the author of [P0515R3] intended for
to be a customisation point, and it is not currently usable as such.
In the standard, we need to provide the ability to customize
and a way to fall back to
and
. This paper argues that these are fundamentally incompatible, and cannot be served by the same function.
[P0891R0] and [P0891R1] of this paper presented the case for having a customisation point for ordering in the language. This paper only summarizes the currently relevant bits of that discussion. For wider context, the reader should refer to the previous revisions, as well as to [P0863R1].
4. Principles
To arrive at the final design of this paper, we used the following principles:

Consistency:
algorithms should behave consistently with* _order
by default.<=> 
Weakening: If a type has a given order, than it also has all weaker orders.

Ambiguity of Legacy: The ordering category provided by the legacy comparison operators is ambiguous. The standard currently expects merely that
provides a weak ordering.< 
Customisation: As
is a customisation point for the natural ordering on a type, so<=>
is a customisation point for an arbitrary strong order on that type.strong_order 
Fallback: We need convenient functions to get
types from legacy comparison operators.* _ordering
From these principles, these corollaries follow:

Corollary 1: from Consistency it follows that, if
provides a given order<=>
, then the default implementation ofX
should use it.X_order
Example:
should be equivalent tostrong_order ( 1 , 2 )
, since1 <=> 2
'sint
provides a strong ordering.operator <=>
likewise, sinceweak_order ( 1 , 2 )
is convertible to1 <=> 2
.strong_ordering 
Corollary 2: from Consistency, Weakening and Customisation, it follows that:

if
does not provide a strong enough order, but a stronger ordering function (e.g.<=>
forstrong_order
,weak_order
forweak_order
) is available, then the weaker ordering function must fall back on it (this works recursively, so ifpartial_order
is defined, so isstrong_order
).partial_order
Example: given
,struct C { partial_ordering operator <=> ( C const & ) const ; }; strong_ordering strong_order ( C const & , C const & );
should returnweak_order ( c1 , c2 )
, becausestrong_order ( c1 , c2 )
does not provide a sufficiently strong order.c1 <=> c2


Corollary 3: from Consistency and Fallback, it follows that if
exists, the fallback function should use it in preference of legacy comparison operators.<=> 
Corollary 4: From Fallback and Ambiguity of Legacy, it follows that by using a fallback function, the user is asserting that
and<
implement the corresponding ordering.== 
Corollary 5: From Customisation and the definition of customisation point, it follows that
functions must be specified as does not participate in overload resolution when they cannot be synthesized according to the above rules.* _order 
Corollary 6: From Corollary 4 and Corollary 5 it follows that the fallbacks and the customisation points cannot be the same functions, as their roles are fundamentally incompatible. To illustrate: the fallback function for synthesizing
must exist wheneverstrong_ordering
and<
do, but the==
customisation point must not be synthesized purely from those.strong_order
In addition, we have made the following observations:

Given [D1186R1] provides a method of generating a
operator from<=>
and<
, we should (due to Consistency) defer to that method for synthesizing the fallback functions.== 
If
is a customisation point for providing a stronger order thanstrong_order
does, data structures that recurse to their contents for<=>
should also recurse for<=>
.strong_order 
Given that the
operator is not being provided for any of the types in the standard library C++20, we are deferring proposing this until such time as<=>
is proposed for them as well.<=>
5. Discussion
5.1. Discussion of the Customisation principle
The arguments around whether
should be a customisation point have centered around the following questions:

Is it even useful?

Given that it is viral, is it worth the implementation effort?

Should all of the comparison algorithms be customisation points?

How can this be taught?
5.1.1. Is it useful?
There are many algorithms and data strucutres that do not care about ordering
per se, but do require some arbitrary order. Examples of these include
,
, and fast implementations of set algorithms (union, intersection,
difference, etc), which are typically based on ordered sequences.
There also exist types for which there is no natural strong ordering, such as
and
. Even though these types do not have a natural strong
ordering, it is nevertheless very useful to provide an arbitrary strong
ordering for them, e.g. so that they can be used in containers such as
and
. Having an arbitrary strong ordering is in fact so useful that Stepanov and Mc Jones included it it in their definition of Regular in Elements of Programming.
In order to make it possible to use IEC559 floatingpoint types in
s and
s, the existing
comparison algorithm includes a special rule for IEC559 floating point types. This works well for simple sets of
floating point numbers, but it breaks down quickly when we try more complicated
examples such as
or
. To make
these examples work, we need to customise
for
,
and other container types, and for that to be permitted
must be a customisation point.
Having an agreedupon customisation point for an arbitrary order is long
overdue. It is time to define what that customisation point is, so it can be
provided and used consistently across C++ libraries and applications. That name
should be
, since
as a distinct customisation
point was rejected by LEWG in San Diego in favor of the design in R0 of this
paper.
5.1.2. Given that it is viral, is it worth the implementation effort?
Given that any customisation point we designate has to potentially be overloaded for all the generic wrappers in the standard library, is it worth the effort of defining them?
This paper does not propose any such wrappers, because the standard library does not even support
for such wrapper types yet. This paper only proposes that
be established as a customisation point.
5.1.3. How can I teach this?
For types that endeavour to be Regular or something like it (as in, have sane value semantics), do the following.
5.1.3.1. Writing new types:

defines what "strong equality" means. This is because copies must compare equal, andoperator ==
should be the finest relation that observes this rule. EOP defines it as "must represent the same value in the domain of the type."== 
if
if and only if( x <=> y ) == 0
, thenx == y
should returnoperator <=>
, otherwise it should returnstrong_ordering
(unless it only defines a partial order, and then it must returnweak_ordering
anyway).partial_ordering 
If your type does not provide an order, you should still provide an overload of
that defines an arbitrary order consistent withstrong_order
.== 
If you are obeying the rule of zero, writing
will give you the correctauto operator <=> (...) = default
and==
without any additional work. In most cases, this should already be enough, since<=>
will result in a<=>
.strong_ordering 
If you are writing a generic wrapper, or your constituent types have an overloaded
, you must then also definestrong_order
to be:strong_order
strong_ordering strong_order ( T x , T y ) { if ( auto ord = strong_order ( x . a , y . a ); is_neq ( ord )) { return ord ; } if ( auto ord = strong_order ( x . b , y . b ); is_neq ( ord )) { return ord ; } // ... for all members return strong_ordering :: equal ; }
5.1.3.2. Using orderings:
Generic algorithms should require and call
,
or
(depending on the ordering requirements of the algorithm) after a
.
These will find the most appropriate ordering available, or SFINAE away if no suitable ordering is available. For example, if an algorithm calls
on a type which has
returning
, does not provide an overload of
, but does overload
, then
will end up being called. The intent is that these "always do the right thing".
5.2. Discussion of the Fallback principle
The arguments on whether we need to provide the fallback functions for legacy types center around a few questions:

How do we make it easy to define
for types which have members which only define<=>
and<
, but not==
?<=> 
How should generic code work with types that may or may not define
, but are assumed to have the requisite preconditions on<=>
and<
?== 
In a context where we need to pass an ordering type as a parameter to a function, but we need to obtain it from a legacy type, how do we do that?
[D1186R1] makes the first of these trivial, and defines the algorithms necessary to make use of the legacy type’s
and
operators. Helpfully, it defines the
specification macro, which contains the core of its fallback logic.
The second two questions boil down to the same thing: if we have a type that implements
and
, and we know it has a particular ordering, how do we convert that into a value of the appropriate
type? We expect this to become a common problem, and therefore the standard should provide convenience functions that call
and
and return an
value representing the result. In specifying these functions, we can reuse the
from [D1186R1], both for convenience and consistency.
However, as C++ applications and libraries are updated to implement
for their types, the need for these fallback functions should diminish. On the other hand, the customisation points are a feature with permenant utility. Due to customziation points having a longer term utility, they should get the
names, and we should find new names for fallback functions.
6. Questions for LEWG:

Is there consensus that the Customisation premise (as above) is correct and should be adopted?

If not, then should the IEC559 exception bullet in the current working draft be removed?


Is there consensus that the Fallback premise (as above) is correct and should be adopted?

Rejecting this means that we are rejecting the rationale for their inclusion in the current working draft and that they should be removed.

(The Consistency, Weakening and Ambiguity of Legacy are true from a good design, mathematical, and empirical point of view, respectively, so they are not subject to poll).
7. Proposal
7.1. Remove the strong_equal
and weak_equal
comparison algorithms
If we accept [P1185R0]'s rationale for not calling
when the user only
needs equality (as EWG did in San Diego), we should also avoid doing so in the
library. However, without making assumptions about the behaviour of
, there
is no way to implement
and
without calling
.
Therefore, we propose removing the
and
algorithms.
7.2. Make strong_order
and friends customisation points
For the functions
,
and
we propose to:

Replace the functions with Customsation Point Objects.

Remove the fallbacks to
and== < 
Have the functions not participate in overload resolution (instead of being defined as deleted) if there is no strong order available.
7.3. Replace the IEC559 rule in strong_order
with separate overloads
Since
is a customisation point, the strong order for floating
point types should be provided as overloads of
rather than being
baked into the generic
function.
We propose that the bullet point regarding
be removed from the
algorithm, and that the following three overloads for
are added:

strong_order ( float , float ); 
strong_order ( double , double ); 
strong_order ( long double , long double );
These overloads should implement the
operation as specified in
ISO/IEC/IEEE 60559, and should not participate in overload resolution if
is false
for the type of their arguments.
7.4. Make the weaker customisation points call stronger customizatoin points
To handle cases such as where a type provides a
from
and a
overload, if a customisation point cannot get an
appropriate result from calling
, it should try to call a customisation
point for an order stronger than its own. Specifically:

should fall back to callingweak_order strong_order 
should fall back to callingpartial_order weak_order
7.5. Add fallback functions
To avoid losing the functionality of the existing comparison algorithms, we propose to keep them under new names, with the following changes to their behaviour:

They will, in preference to anything else, return the result of calling the corresponding customisation point.

They will not attempt to call
directly, as this is called by the customisation point.<=> 
They will fall back to
and==
using the language mechanism proposed by [D1186R1] instead of calling<
and==
directly.<
As per the original comparison algorithms, they will be defined as deleted if
neither the corresponding customisation point nor the
and
operators
are available.
Following the same reasoning as in §7.1 Remove the strong_equal and weak_equal comparison algorithms, there will be no fallback
functions for
and
.
We propose naming the fallback functions
,
and
.
Other options to consider:

assumed_X_order 
X_order_assume 
assume_X_order 
fallback_X_order 
X_order_fallback
See the fallback discussion on why the
names should be given to the customisation points.
8. Proposed Wording
Change the current
to
(but see bikeshedding section):
 # Effects: Compares two values and produces a result of type
:strong_ordering  (1.1) If
is true, returns a result of typenumeric_limits < T >:: is_iec559
that is consistent with the totalOrder operation as specified in ISO/IEC/IEEE 60559.strong_ordering  (#.1) If the expression
is wellformed and convertible tostrong_order ( a , b )
, return the result of the expression,strong_ordering  (1.2) Otherwise, returns
if that expression is wellformed and convertible toa <=> b
.strong_ordering  (#.2) Otherwise, if the expression
is wellformed, return the result of the expression,3 WAY < strong_ordering > ( a , b )  (1.3) Otherwise, if the expression a <=> b is wellformed, then the function is defined as deleted.
 (1.4) Otherwise, if the expressions a == b and a < b are each wellformed and convertible to bool, then
 (1.4.1) if a == b is true, returns
;strong_ordering :: equal  (1.4.2) otherwise, if a < b is true, returns
;strong_ordering :: less  (1.4.3) otherwise, returns
.strong_ordering :: greater
 (1.4.1) if a == b is true, returns
 (#.53) Otherwise, the function shall be defined as deleted.
 (1.1) If
Change the current
to
(but see bikeshedding section):
 # Effects: Compares two values and produces a result of type
:weak_ordering  (#.1) If the expression
is wellformed and convertible toweak_order ( a , b )
, return the result of the expression,weak_ordering  (2.1) Returns
if that expression is wellformed and convertible toa <=> b
.weak_ordering  (#.2) Otherwise, if the expression
is wellformed, return the result of the expression,3 WAY < weak_ordering > ( a , b )  (2.2) Otherwise, if the expression a <=> b is wellformed, then the function is defined as deleted.
 (2.3) Otherwise, if the expressions a == b and a < b are each wellformed and convertible to bool, then
 (2.3.1) if a == b is true, returns
;weak_ordering :: eqivalen  (2.3.2) otherwise, if a < b is true, returns
;weak_ordering :: less  (2.3.3) otherwise, returns
.weak_ordering :: greater
 (2.3.1) if a == b is true, returns
 (#.43) Otherwise, the function shall be defined as deleted.
 (#.1) If the expression
Change the current
to
(but see bikeshedding section):
 # Effects: Compares two values and produces a result of type
:partial_ordering  (#.1) If the expression
is wellformed and convertible topartial_order ( a , b )
, return the result of the expression,partial_ordering  (2.1) Returns
if that expression is wellformed and convertible toa <=> b
.partial_ordering  (#.2) Otherwise, if the expression
is wellformed, return the result of the expression,3 WAY < partial_ordering > ( a , b )  (2.2) Otherwise, if the expression a <=> b is wellformed, then the function is defined as deleted.
 (2.3) Otherwise, if the expressions a == b and a < b are each wellformed and convertible to bool, then
 (2.3.1) if a == b is true, returns
;partial_ordering :: eqivalen  (2.3.2) otherwise, if a < b is true, returns
;partial_ordering :: less  (2.3.3) otherwise, returns
.partial_ordering :: greater
 (2.3.1) if a == b is true, returns
 (#.43) Otherwise, the function shall be defined as deleted.
 (#.1) If the expression
From section 24.x.4, Comparison Algorithms [cmp.alg], remove
and
:
template < class T > constexpr strong_equality strong_equal ( const T & a , const T & b );
 4 Effects: Compares two values and produces a result of type
:strong_equality  (4.1) Returns a <=> b if that expression is wellformed and convertible to
.strong_equality  (4.2) Otherwise, if the expression a <=> b is wellformed, then the function is defined as deleted.
 (4.3) Otherwise, if the expression a == b is wellformed and convertible to bool, then
 (4.3.1) if a == b is true, returns
;strong_equality :: equal  (4.3.2) otherwise, returns
.strong_equality :: nonequal
 (4.3.1) if a == b is true, returns
 (4.4) Otherwise, the function is defined as deleted.
 (4.1) Returns a <=> b if that expression is wellformed and convertible to
weak_equality
:
 (5.1) Returns a <=> b if that expression is wellformed and convertible to
.weak_equality  (5.2) Otherwise, if the expression a <=> b is wellformed, then the function is defined as deleted.
 (5.3) Otherwise, if the expression a == b is wellformed and convertible to bool, then
 (5.3.1) if a == b is true, returns
;weak_equality :: equivalent  (5.3.2) otherwise, returns
.weak_equality :: nonequivalent
 (5.3.1) if a == b is true, returns
 (5.4) Otherwise, the function is defined as deleted.
Then add the
customisation point object:
strong_order
denotes a customisation point object. The expression std :: strong_order ( E , F )
for some subexpressions E
and F
with type T
is expressionequivalent to:
 (#.1)
if it is a valid expression,strong_order ( E , F )  (#.2) Otherwise,
if it is a valid expression and its type is convertible toE <=> F
,strong_ordering  (#.3) Otherwise,
is illformed. [Note: This case can result in substitution failure whenstd :: strong_order ( E , F )
appears in the immediate context of a template instantiation. end note]strong_order ( E , F )
std :: strong_order
is a valid expression, its type is convertible to strong_ordering
. end note]
Add overloads for IEC559 types:
strong_order ( T , T )
when T
is a type for which std :: numeric_limits < T >:: is_iec559
is true
shall be a valid expression, whose value shall be consistent with the totalOrder operation as specified in ISO/IEC/IEEE 60559. Add the
customisation point object:
weak_order
denotes a customisation point object. The expression std :: weak_order ( E , F )
for some subexpressions E
and F
with type T
is expressionequivalent to:
 (#.1)
if it is a valid expression,weak_order ( E , F )  (#.2) Otherwise,
if it is a valid expression and its type is convertible toE <=> F
,weak_ordering  (#.3) Otherwise,
if it is a valid expression,std :: strong_order ( E , F )  (#.4) Otherwise,
is illformed. [Note: This case can result in substitution failure whenstd :: weak_order ( E , F )
appears in the immediate context of a template instantiation. end note]weak_order ( E , F )
std :: weak_order
is a valid expression, its type is convertible to weak_ordering
. end note]
Add the
customisation point object:
partial_order
denotes a customisation point object. The expression std :: partial_order ( E , F )
for some subexpressions E
and F
with type T
is expressionequivalent to:
 (#.1)
if it is a valid expression,partial_order ( E , F )  (#.2) Otherwise,
if it is a valid expression and its type is convertible toE <=> F
,partial_ordering  (#.3) Otherwise,
if it is a valid expression,std :: weak_order ( E , F )  (#.4) Otherwise,
is illformed. [Note: This case can result in substitution failure whenstd :: partial_order ( E , F )
appears in the immediate context of a template instantiation. end note]partial_order ( E , F )
std :: partial_order
is a valid expression, its type is convertible to partial_ordering
. end note]
9. Acknowledgments
We would like to thank

Roger Orr for bringing this to our attention;

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

Sam Finch for thoroughly breaking the original 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 (mutually opposing) guidance on customisation 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 a committee meeting when Gašper could not make it in person, and guidance with direction;

Barry Revzin for representing the paper at a committee meeting when Gašper could not make it in person, and his various papers that touch ours, and for prereviewing our wording and suggesting we make the customisation points CPOs, and reworking his paper to support the
syntax.3 WAY < strength > ( x , y ) 
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 us to remember whose shoulders we are standing on.
Thank you all!
Appendix A: Proof strong_order
is not a valid customisation 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.