Maybe remove the StrictTotallyOrdered constraint on std::less, default algorithm relations to a new std::totally_ordered_less

[ericniebler]

No description provided.

[asutton]

I'm against this. If the intent is to allow less to be used for
partial orders, then I would prefer to define a less constrained
functor called before (or something like that).

Andrew Sutton

On Wed, May 6, 2015 at 3:44 PM, Eric Niebler notifications@github.com wrote:

—
Reply to this email directly or view it on GitHub.

[ericniebler]

I feel likewise, but there is strong resistance on the committee for std::less requiring anything other than operator<

[ericniebler]

BTW, I like the before<T> suggestion. I don't think it'll fly.

[ericniebler]

Holding off on this one until I know which way the core language is going on the defaulted comparison operators proposal.

[tvaneerd]

I'd be a big fan of having a std::order<T> that the STL uses (and imposes requirements on). And have std::less<T> really just mean "a function object that uses <".

[sean-parent]

The requirement should be that operator<() is a natural total order.
std::less should be operator<() if defined, otherwise a representational
ordering (this is consistent with the current wording for std::less<T*>.

On Fri, Jul 31, 2015 at 1:34 PM, tvaneerd-rim notifications@github.com
wrote:

I'd be a big fan of having a std::order that the STL uses (and imposes
requirements on). And have std::less really just mean "a function
object that use <".

—
Reply to this email directly or view it on GitHub
#21 (comment).

[tvaneerd]

Yes, I suspect we've had this conversation. I agree that makes sense for current STL, but we might have an opportunity here to get std::less back to having only one meaning instead of two.
As a mathematician and DSL writer, '<' shouldn't always need to be a total order. But std::less should always be '<'‎. The resolution is introducing std::order. Which can default to std::less (for backwards compatibility) . Ideally std::less always uses <, and should never be overridden.

Sent from my BlackBerry 10 smartphone on the TELUS network.
From: Sean Parent
Sent: Friday, July 31, 2015 7:28 PM
To: ericniebler/stl2
Reply To: ericniebler/stl2
Cc: Tony Van Eerd
Subject: Re: [stl2] Maybe remove the TotallyOrdered constraint on std::less, defaut algorithm relations to a new std::totally_ordered_less (#21)

The requirement should be that operator<() is a natural total order.
std::less should be operator<() if defined, otherwise a representational
ordering (this is consistent with the current wording for std::less<T*>.

On Fri, Jul 31, 2015 at 1:34 PM, tvaneerd-rim notifications@github.com
wrote:

I'd be a big fan of having a std::order that the STL uses (and imposes
requirements on). And have std::less really just mean "a function
object that use <".

—
Reply to this email directly or view it on GitHub
#21 (comment).

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/21#issuecomment-126834406.

[tomaszkam]

If we get some form of the lifting-operator accepted into language (like N3617 and P0119R0), then we could use operator< or []operator< as a syntax for a functor that just calls < and supports partial ordering, which seems to be pretty natural.

That would allow us to have both raw wrapper ([]operator<) and semantic wrapper (std::less<>) for comparison operators.

[ericniebler]

If the core language gets defaulted or automatically generated comparison operators, then the issue is moot (I think). This issue is on the back burner until core picks a direction.

[tomaszkam]

If the core language gets defaulted or automatically generated comparison operators, then the issue is moot (I think). This issue is on the back burner until core picks a direction.

Current default comparison operators paper N4475 supports operator< representing partial order, by specifying that a <= b is equivalent to a < b || a == b instead of !(a>b). So even if the proposal will be accepted, there will be still semantic difference between operator< and std::less<>.

[ericniebler]

Defaulted comparison operations in the core language is dead. @CaseyCarter believes the function objects (less, equal_to) are incorrect to require EqualityComparable and StrictTotallyOrdered. I may agree with him. This discussion also bears on #34.

[sean-parent]

My summary of the issue -
Because floating point types have NaN, which is unordered, there is some desire to have operator<() and by extension std::less<>() to not require strict weak ordering. I believe this logic is flawed and NaN should be treated more as an invalid value. Outside the domain of the operator concepts. I would require that operator<() be a natural total ordering (not just strict-weak) and std::less<>() should be a total ordering though not necessarily natural (it could be representational). This is currently how the standard handles std::less<>() for pointer types (you cannot compare two pointers legally with operator< unless they are within the same array, but you can use std::less<>() - this is because operator< doesn't provide a natural total order because comparing two pointers two different blocks gives an indeterminate result across runs of the application. The punt option is to move the requirements of the operators() to be preconditions int the algorithms. That is, if operator< is used in std::sort then it must be a strict-weak ordering for the values being sorted.

[tvaneerd]

I'd say default comparison operations are dead for now. I'm still pushing for == (ASAP), and opt-in operator< et al, with same generation as P0221 (ie <= is < || ==)

[sean-parent]

<= should not be < || ==. That is an unnecessary comparison by default and it simply means people will be recommended to not write <= but instead write !>.

[sean-parent]

If you want to support partial ordering, add an operator ⪯ ()

[ericniebler]

To be clear, I'm not suggesting that we drop the "strict weak order" requirement on less. I'm questioning what that means from a type-checking perspective. Right now, it means that the class template less can only be instantiated on types that provide all the relational operators. Or, it can be instantiated on void, in which case, the function call operator is constrained with the cross-type StrictTotallyOrdered, which requires that the two types satisfy Common, and that the common type also satisfy StrictTotallyOrdered. This is arguably a needlessly high bar. This issue is mostly about trying to find the right place to set the dial for the function objects.

[tvaneerd]

Two thoughts, neither fully formed:

• maybe less has no (semantic) requirements. It is purely syntax - a way to turn the syntax of "<" into a function object. What has requirements are the places that use less. If I want to use less in my DSL (where "<" isn't an ordering at all), who cares?
  Only when less is used in places that need ordering - then the requirements exist. Somewhat like "noexcept(auto)" less is as ordered as the "<" within it.

I know that goes again the general idea of semantic vs syntactic concepts/constraints. But I wonder if we are placing the constraints in the right place.

• And....
  Nope, that's only one thought. The other was "do we have this backwards - who is constraining whom", but that is either the same as the above or even less (pun) fully formed.

[CaseyCarter]

maybe less has no (semantic) requirements. It is purely syntax - a way to turn the syntax of "<" into a function object.

If I was to respecify less today, it would look like:

// The much-maligned "LessThanComparable"
template <class T, class U>
concept bool __LessThanComparable = // exposition only
  requires(const T& t, const U& u) {
    t < u; // note: library-wide wording implicitly requires this expression
           // to be equality-preserving and to not modify t or u
  };

template <class T, class U>
concept bool __LWG2450 = // exposition only
  __LessThanComparable<T, U> && see below;

template <class T = void>
requires
  Same<T, void>() || __LessThanComparable<T, T>
struct less {
  constexpr decltype(auto) operator()(const T& x, const T& y) const
    noexcept(noexcept(x < y))
  { return x < y; }

  constexpr bool operator()(const T& x, const T& y) const noexcept
    requires __LWG2450<T, T>;
};

template <>
struct less<void> {
  __LessThanComparable{T, U}
  constexpr decltype(auto) operator()(const T& x, const U& y) const
    noexcept(noexcept(x < y))
  { return x < y; }

  __LWG2450{T, U}
  constexpr bool operator()(const T& x, const U& y) const noexcept;
};

1 __LWG2450<T, U> is satisfied iff t < u invokes a builtin comparison operator for pointers.

2 User specializations of less are forbidden.

  template <class T>
  constexpr bool less<T>::operator()(const T& x, const T& y) const noexcept
    requires __LWG2450<T, T>;

  template <>
  __LWG2450{T, U}
  constexpr bool less<void>::operator()(const T& x, const U& y) const noexcept;

3 Returns: x < y if it is well-defined. Otherwise [bit handwavy here], true if and only if x precedes y in the implementation-defined total pointer ordering.

Note that __LessThanComparable is exposition only because it is intentionally useless: requiring a type T to be __LessThanComparable would allow you to instantiate less<T> and call its operator(), but there's no way to use the result. To use less effectively you must specify requirements on either the parameter types with which you will use it or the result of the specialization. e.g.:

template <class T>
bool foo(T x, T y) {
  return less<T>{}(x, y); // Nope, underconstrained.
}

template <StrictTotallyOrdered T>
bool foo(T x, T y) {
  return less<T>{}(x, y); // Ok: StrictTotallyOrdered subsumes __LessThanComparable
                          // and requires the result type to satisfy Boolean.
}

template <class T, StrictWeakOrder<T> C = less<T>>
bool foo(T x, T y) {
  return less<T>{}(x, y); // Ok: we've explicitly required less<T> to induce a
                          // strict weak order on T.

  return less<>{}(x, y); // Also ok: less<void>::operator()(T, T) is equivalent
                         // to less<T>::operator()(T, T).
}

We've lost nothing relative to the current specification, and gained the ability to use less with other kinds of orderings / meanings that meet the minimal requirement of equality preservation.

[sean-parent]

I'm a proponent of strong semantics and enforcing those semantics to the
extent possible. Raise the bar as high as possible. I also teach developers
to provide specializations of std::less<> for types where there is a
representational total ordering but no natural total ordering (and have
done so for over a decade).

On Thu, Nov 3, 2016 at 2:06 PM, Casey Carter notifications@github.com
wrote:

maybe less has no (semantic) requirements. It is purely syntax - a way to
turn the syntax of "<" into a function object.

If I was to respecify less today, it would look like:

// The much-maligned "LessThanComparable"template <class T, class U>
concept bool __LessThanComparable = // exposition only
requires(const T& t, const U& u) {
t < u; // note: library-wide wording implicitly requires this expression
// to be equality-preserving and to not modify t or u
};
template <class T, class U>
concept bool __LWG2450 = // exposition only
__LessThanComparable<T, U> && see below;
template
requires
Same<T, void>() || __LessThanComparable<T, T>struct less {
constexpr decltype(auto) operator()(const T& x, const T& y) const
noexcept(noexcept(x < y))
{ return x < y; }

constexpr bool operator()(const T& x, const T& y) const noexcept
requires __LWG2450<T, T>;
};
template <>struct less {
__LessThanComparable{T, U}
constexpr decltype(auto) operator()(const T& x, const U& y) const
noexcept(noexcept(x < y))
{ return x < y; }

__LWG2450{T, U}
constexpr bool operator()(const T& x, const U& y) const noexcept;
};

1 __LWG2450<T, U> is satisfied iff t < u invokes a builtin comparison
operator for pointers.

2 User specializations of less are forbidden.

template
constexpr bool less::operator()(const T& x, const T& y) const noexcept
requires __LWG2450<T, T>;

template <>
__LWG2450{T, U}
constexpr bool less::operator()(const T& x, const U& y) const noexcept;

3 Returns: x < y if it is well-defined. Otherwise [bit handwavy here],
true if and only if x precedes y in the implementation-defined total
pointer ordering.

Note that __LessThanComparable is exposition only because it is
intentionally useless: requiring a type T to be __LessThanComparable
would allow you to instantiate less and call its operator(), but
there's no way to use the result. To use less effectively you must
specify requirements on either the parameter types with which you will use
it or the result of the specialization. e.g.:

template bool foo(T x, T y) {
return less{}(x, y); // Nope, underconstrained.
}
template bool foo(T x, T y) {
return less{}(x, y); // Ok: StrictTotallyOrdered subsumes __LessThanComparable
// and requires the result type to satisfy Boolean.
}
template <class T, StrictWeakOrder C = less>bool foo(T x, T y) {
return less{}(x, y); // Ok: we've explicitly required less to induce a
// strict weak order on T.

return less<>{}(x, y); // Also ok: less::operator()(T, T) is equivalent
// to less::operator()(T, T).
}

We've lost nothing relative to the current specification, and gained the
ability to use less with other kinds of orderings / meanings that meet
the minimal requirements for equality preservation and returning a
referenceable type.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#21 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACLJLA1P-YfCe-fZ2wEXB5brPlkT1wn7ks5q6kzXgaJpZM4ERmAB
.

[CaseyCarter]

I also teach developers to provide specializations of std::less<> for types where there is a
representational total ordering but no natural total ordering (and have
done so for over a decade).

C++14's <void> specializations seem to have inadvertently killed this practice. Sure, one can easily specialize std::less<foo>, but how do you keep the behavior of std::less<void>::operator() consistent with that of std::less<T>::operator()? The committee itself has had a hard time doing so for pointers (LWG2450, LWG2562).

I don't think we can continue the practice of using less for both < and "total ordering." The two responsibilities have begun to diverge.

[sean-parent]

Why would less break things. I would nievly assume it simply deduces
T and calls through to less.

[tomaszkam]

Why would less<void> break things. I would nievly assume it simply deduces T and calls through to less<T>.

std::less<void> is calling < on the exact types of arguments that was provided to the call, including the case in which they are different. This was the basis for having heterogeneous container lookup, and allowing std::string to be compare with char const* without creating an temporary std::string.

[ericniebler]

I would nievly assume it simply deduces T and calls through to less<T>.

Casey and tomaszkam already answered this, but at least in the case that the two arguments have the same type — which is the common case, I would guess — dispatching to less<T> seems like a reasonable thing to do.

[CaseyCarter]

N4606 [comparisons.less]/2:

template <> struct less<void> {
  template <class T, class U> constexpr auto operator()(T&& t, U&& u) const
   -> decltype(std::forward<T>(t) < std::forward<U>(u));

  using is_transparent = unspecified;
};

template <class T, class U> constexpr auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) < std::forward<U>(u));

2 Returns: std::forward<T>(t) < std::forward<U>(u)

I would love to have a design for less<void>::operator(T, U) that dispatches to less<C>::operator() when the < operator which would be invoked (after implicit conversions) would be that for C. My sole motivation for wanting to forbid user specializations is to maintain consistency between less<T> and less<void> - I don't want another vector<bool>. If anyone has suggestions, please speak up ;)

[tvaneerd]

<=> is the new black. Lots of talk of spaceship operator (returns -1 / 0 / +1) within the committee.

[NicolBolas]

With the spaceship operator and opt-in generation of spaceship comparisons in C++20, is this issue effectively moot?

[ericniebler]

Not quite because of legacy code, but it certainly gives us an easy answer to give people who don't want to spam out a bunch of operator overloads: change your operator< to an operator<=>.

[ericniebler]

Closing this since we settled on a constrained std::ranges::less and friends.