C++ Logo

SG12

Advanced search

Subject: Re: [ub] Justification for < not being a total order on pointers?
From: Nevin Liber (nevin_at_[hidden])
Date: 2013-10-15 17:39:01


On 10 October 2013 20:37, Gabriel Dos Reis <gdr_at_[hidden]> wrote:

| As observed by Sean Parent in another discussion, std::less<T*> as a
> | total order was never meant to be synonymous for operator< on
> pointers.
>

But his rule states that if it is provided for a type, it should be a
natural total order for objects of that type. That obviously isn't true
for pointers, so now we have an irregular guideline: "Except for pointers,
don't provide operator< for a type unless it is the natural total order for
that type."

It gets worse in C++14. std::less<> (aka std::less<void>) uses operator<,
not std::less<T> under the covers, and even though that has weasel words
about comparing pointers, it is not useable if your type does not have an
operator<.

So now what should the guideline be? Tell people to ignore instead of
embrace this addition to C++14 (in which case, shouldn't we pull it from
C++14 and put it into the Lib Fundamentals TS until we understand the
ramifications better? It isn't like anyone brought up this point when it
was discussed in Bristol)? Or should it read: "Except for pointers, don't
provide operator< for a type unless it is the natural order for that type,
unless you wish to allow people to use std::less<>, in which case provide
an operator< anyway."

The only way to make the language and library novice-friendly is to make
simpler, more regular rules with fewer exception cases.

The current rule of "calling operator< on pointers can invoke ub at the
drop of a hat", while historically necessary, is a horrible, horrible rule.

Changing the rule to "pointers are totally ordered with respect to the
comparison operators" is much more sane (and is only one step to
unravelling the expert-only mess we have with relation operators in the
standard).

> | Sean also says in [c++std-lib-ext-550]: The definition
> of std::less should be
> | "a representational order if no natural total order (operator <) is
> available,
> | otherwise the natural total order". He goes on: "They are named
> separately,
> | operator<() is the natural total order and std::less<> is the natural
> total
> | order if one exists, otherwise it is a representational order."
> |
> | Pointers clearly violate those rules.
>
> Sean will speak for himself, but I don't think he was making the point
> that operator< on pointers was a total order.

In other words, operator< on pointers violates his own rule, as it is NOT
the natural (or even necessarily any) total order on pointers. I'm
positive Sean will never have a problem living with this contradiction.
But he's an expert...

> I must confess I do not understand why saying that for "p < q" to make
> sense, the addresses must be related is an expert-level thing.
>

It's the subtle difference between std:less<T*> and operator< that makes it
an expert-level thing.

>
> Certainly, we don't claim that for two random iterators p and q, the
> expression p < q must make sense whether p and q are related. Are we?
>

Pointers are used for more than just iteration, and we already say that
pointers are totally ordered with respect to std::less<T*> and std::less<>
(as well as the other ordered comparators).

> I've not seen novices wanting to do anything sensible in a conditional
> based on p < q when the addresses are not related.

Really? I've seen novices ask questions like "does pointer p point to an
object inside array a?" A natural (but wrong) way to write it is:

bool isInArray = std::begin(a) <= p && p < std::end(a);

Can you even write this w/o possibly invoking ub? The only way I can think
of is O(n), as in:

bool isInArray = false;
for (auto q = std::begin(a); q != std::end(a); ++q)
    if (p == q) {
        isInArray = true;
        break;
    }

Do we intend such simple questions to have such complicated answers?

-- 
 Nevin ":-)" Liber  <mailto:nevin_at_[hidden]>  (847) 691-1404



SG12 list run by herb.sutter at gmail.com