C++ Logo

SG12

Advanced search

Subject: Re: [ub] Justification for < not being a total order on pointers?
From: Gabriel Dos Reis (gdr_at_[hidden])
Date: 2013-10-15 18:14:29


Nevin --
Are you asking that operator< be a total order on std::deque<T>::iterator?

-- 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>


SG12 list run by herb.sutter at gmail.com