3431. <=> for containers should require three_way_comparable<T> instead of <=>

Section: 23.2.2.4 [container.opt.reqmts] Status: WP Submitter: Jonathan Wakely Opened: 2020-04-17 Last modified: 2023-11-22

Priority: 2

View all issues with WP status.

Discussion:

The precondition for <=> on containers is:

"Either <=> is defined for values of type (possibly const) T, or < is defined for values of type (possibly const) T and < is a total ordering relationship."

I don't think <=> is sufficient, because synth-three-way won't use <=> unless three_way_comparable<T> is satisfied, which requires weakly-equality-comparable-with<T, T> as well as <=>.

So to use <=> I think the type also requires ==, or more precisely, it must satisfy three_way_comparable.

The problem becomes clearer with the following example: 

#include <compare>
#include <vector>

struct X
{
  friend std::strong_ordering operator<=>(X, X) { return std::strong_ordering::equal; }
};

std::vector<X> v(1);
std::strong_ordering c = v <=> v;

This doesn't compile, because despite X meeting the preconditions for <=> in [tab:container.opt], synth-three-way will return std::weak_ordering.

Here is another example: 

#include <compare>
#include <vector>

struct X
{
  friend bool operator<(X, X) { return true; } // The return value is intentional, see below
  friend std::strong_ordering operator<=>(X, X) { return std::strong_ordering::equal; }
};

std::vector<X> v(1);
std::weak_ordering c = v <=> v;

This meets the precondition because it defines <=>, but the result of <=> on vector<X> will be nonsense, because synth-three-way will use operator< not operator<=> and that defines a broken ordering.

So we're stating a precondition which implies "if you do this, you don't get garbage results" and then we give garbage results anyway.

The proposed resolution is one way to fix that, by tightening the precondition so that it matches what synth-three-way actually does.

[2020-04-25 Issue Prioritization]

Priority to 2 after reflector discussion.

Previous resolution [SUPERSEDED]:

This wording is relative to N4861.

  1. Modify 23.2.2 [container.requirements.general], Table [tab:container.opt], as indicated:

    Table 75: Optional container operations [tab:container.opt]
    Expression Return type Operational
    semantics    		 Assertion/note
    pre-/post-condition    		 Complexity
    …
    a <=> b synth-three-way-result<value_type> lexicographical_compare_three_way(
    a.begin(), a.end(), b.begin(), b.end(),
    synth-three-way)         		Preconditions: Either <=> is defined for
    values of type (possibly const)
    T satisfies three_way_comparable,
    or < is defined for values of type
    (possibly const) T and
    < is a total ordering relationship.     		linear
    …

[2022-04-24; Daniel rebases wording on N4910]

Previous resolution [SUPERSEDED]:

This wording is relative to N4910.

  1. Modify 23.2.2.4 [container.opt.reqmts] as indicated:

    a <=> b

    -2- Result: synth-three-way-result<X::value_type>.

    -3- Preconditions: Either <=> is defined for values of type (possibly const) T satisfies three_way_comparable, or < is defined for values of type (possibly const) T and < is a total ordering relationship.

    -4- Returns: lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), synth-three-way)

    [Note 1: The algorithm lexicographical_compare_three_way is defined in Clause 27. — end note]

    -5- Complexity: Linear.

[2023-06-13; Varna]

The group liked the previously suggested wording but would prefer to say "models" instead of "satisfies" in preconditions.

[2023-06-14 Varna; Move to Ready]

[2023-11-11 Approved at November 2023 meeting in Kona. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4950.

  1. Modify 23.2.2.4 [container.opt.reqmts] as indicated:

    a <=> b

    -2- Result: synth-three-way-result<X::value_type>.

    -3- Preconditions: Either <=> is defined for values of type (possibly const) T models three_way_comparable, or < is defined for values of type (possibly const) T and < is a total ordering relationship.

    -4- Returns: lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(), synth-three-way)

    [Note 1: The algorithm lexicographical_compare_three_way is defined in Clause 27. — end note]

    -5- Complexity: Linear.