C++ Logo

SG12

Advanced search

Subject: Re: [ub] Justification for < not being a total order on pointers?
From: Christopher Jefferson (chris_at_[hidden])
Date: 2013-10-16 16:15:43


On 16 October 2013 00:14, Gabriel Dos Reis <gdr_at_[hidden]> wrote:
> Nevin --
> Are you asking that operator< be a total order on std::deque<T>::iterator?
>

On a practical note, I believe this would arise naturally, if
operator< was a total order on pointers. I have written code which
assumes operator< on std::deque<T>::iterator is a total ordering
(because I know it is for systems I use). Also at the moment there
isn't an alternative, because there isn't a
std::less<std::deque<T>::iterator>.

Chris

> -- Gaby
>
> | -----Original Message-----
> | From: ub-bounces_at_[hidden] [mailto:ub-bounces_at_[hidden]] On Behalf
> | Of Nevin Liber
> | Sent: Tuesday, October 15, 2013 3:39 PM
> | To: ub_at_[hidden]
> | Subject: Re: [ub] Justification for < not being a total order on pointers?
> |
> | On 10 October 2013 20:37, Gabriel Dos Reis <gdr_at_[hidden]
> | <mailto: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]
> | <mailto:nevin_at_[hidden]> > (847) 691-1404 <tel:%28847%29%20691-
> | 1404>
> _______________________________________________
> ub mailing list
> ub_at_[hidden]
> http://www.open-std.org/mailman/listinfo/ub


SG12 list run by herb.sutter at gmail.com