Issue 2562: Consistent total ordering of pointers by comparison functors (original) (raw)

This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

2562. Consistent total ordering of pointers by comparison functors

Section: 22.10.8 [comparisons] Status: C++17 Submitter: Casey Carter Opened: 2015-11-18 Last modified: 2017-07-30

Priority: 3

View other active issues in [comparisons].

View all other issues in [comparisons].

View all issues with C++17 status.

Discussion:

N4567 22.10.8 [comparisons]/14 specifies that the comparison functors provide a total ordering for pointer types:

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >=do not.

It notably does not specify:

• whether the specializations of all of the named templates for a given pointer type yield the same total order
• whether the total order imposed respects the partial order imposed by the built-in operators
• whether the total order imposed is consistent with the partition induced by ==

All of which are important for sane semantics and provided by common implementations, since the built-in operators provide a total order and the comparison functors yield that same order.

It would be extremely confusing — if not outright insane — for e.g.:

• less<int*> and greater<int*> to yield different orders
• less<int*> to disagree with < on the relative order of two pointers for which <is defined
• less<int*> to order a before b when a == b, i.e., not preserve equality.

Consistent semantics for the various comparison functors and the built-in operators is so intuitive as to be assumed by most programmers.

Related issues: 2450(i), [2547](lwg-active.html#2547 "Container requirements (and other library text) should say "strict total order", not just "total order" (Status: New)")(i).

Previous resolution [SUPERSEDED]:

This wording is relative to N4567.

1. Alter 22.10.8 [comparisons]/14 to read:

   For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield athe same total order, even if the built-in operators <, >, <=, >= do not. The total order shall respect the partial order imposed by the built-in operators.

[2016-05-20, Casey Carter comments and suggests revised wording]

The new proposed wording is attempting to address the issue raised in the 2016-02-04 telecon.

The real issue I'm trying to address here is ensure that "weird" implementations provide the same kind of consistency for pointer orderings as "normal" implementations that use a flat address spaces and have totally ordered <. If a < b is true for int pointers a and b, then less<int*>(a, b), less_equal<int*>(a, b), less<char*>(a, b), less<void*>(a, b), and greater<int*>(b, a) should all hold. I think this wording is sufficient to provide that.

Previous resolution [SUPERSEDED]:

This wording is relative to N4582.

1. Alter 22.10.8 [comparisons] to read:

   -14- For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield athe same total order. That total order is consistent with the partial order imposed by, even if the built-in operators <, >, ≤, and > do not. [Note: When a < b is well-defined for pointers a and b of type P, this implies (a < b) == less<P>(a, b), (a > b) == greater<P>(a, b), and so forth. — _end note_]For template specializations greater<void>, less<void>, greater_equal<void>, and less_equal<void>, if the call operator calls a built-in operator comparing pointers, the call operator yields a total order.

[2016-08-04 Chicago LWG]

LWG discusses and concludes that we are trying to accomplish the following:

1. T* a = /* ... /;
   T b = /* ... */;
   if a < b is valid, a < b == less<T*>(a, b), and analogously for >, <=, >=.

2. less(a, b) == less<T*>(a, b);
   less<T*>(a, b) == greater<T*>(b, a);
   etc.

3. less<T*> produces a strict total ordering with which the other three function objects are consistent
4. less<void> when applied to pointers produces a strict total ordering with which the other three are consistent
5. less<void> when applied to pointers of the same type produces the same strict total ordering as less<T*>, and analogously for the other three
6. we are not addressing less<void> (and the other three) when applied to pointers of differing types

Walter and Nevin revise Proposed Wording accordingly.

[2016-08 - Chicago]

Thurs PM: Moved to Tentatively Ready

Proposed resolution:

This wording is relative to N4606.

1. Change 22.10.8 [comparisons] p14 as indicated:

   -14- For templates greater, less, greater_equal, and less_equalless, greater, less_equal, and greater_equal, the specializations for any pointer type yield a strict total orderthat is consistent among those specializations and is also consistent with the partial order imposed by , even if the built-in operators <, >, <=, >= do not. [_Note:_When a < b is well-defined for pointers a and b of type P, this implies (a < b) == less<P>(a, b), (a > b) == greater<P>(a, b), and so forth. — _end note_] For template specializations greater<void>, less<void>, greater_equal<void>, and less_equal<void>less<void>, greater<void>,less_equal<void>, and greater_equal<void>, if the call operator calls a built-in operator comparing pointers, the call operator yields a strict total order that is consistent among those specializations and is also consistent with the partial order imposed by those built-in operators.