Me wrote:
> [ Note: Forwarded to C++ Committee. -sdc ]
>
> 20.3.3/8 "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."
>
> The standard should do much better than guarantee that these provide a
> total order, it should guarantee that it can be used to test if memory
> overlaps, i.e. write a portable memmove. You can imagine a platform
> where the built-in operators use a uint32_t comparison (this tests for
> overlap on this platform) but the less<T*> functor is allowed to be
> defined to use a int32_t comparison.

This is already guaranteed (and your implementation is illegal if any
objects cross the signed/unsigned address boundary).

The standard already requires that if (p1<p2) is a valid test,
less(p1,p2) return the same result.  The other operators have the same
requirement.

This is sufficient to detect overlap.  It could allow overlap to be
falsely reported, but that doesn't make memmove wrong.  It might make
memmove less than optimal (ie on an architecture where copy-left was
cheaper than copy-right).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Note to mods: I totally botched the part in the middle up, can you
forward this correction please?

> 20.3.3/8 "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."
>
> The standard should do much better than guarantee that these provide a
> total order, it should guarantee that it can be used to test if memory
> overlaps, i.e. write a portable memmove. You can imagine a platform
> where the built-in operators use a uint32_t comparison (this tests for
> overlap on this platform) but the less<T*> functor is allowed to be
> defined to use a int32_t comparison. On this platform, if you use
> std::less with the intent of making a portable memmove, comparison on
> an array that straddles the 0x7FFFFFFF/0x8000000 boundary can give
> incorrect results.
>
> Resolution: Add a footnote to 20.3.3/8 saying:

Given p1 and p2 such that p1 points to N objects of type T and p2
points to M objects of type T. If and only if [p1,p1+N) does not
overlap [p2,p2+M), less returns the same value when comparing all
pointers in [p1,p1+N) to all pointers in [p2,p2+M). Otherwise, these
ranges overlap in some way and the total ordering produces the expected
results. It is also guaranteed that this total order yields p1[i] <
p1[i+1] for i in [0,N-1) (and similarly for p2). For the sake of
completeness, the null pointer value (4.10) for T is considered to be
pointing to 1 object of type T that doesn't overlap with any valid
non-null pointer to T. less_equal, greater, greater_equal, equal_to,
and not_equal_to give the expected results based on the total ordering
semantics of less. For T of void, treat it as having similar semantics
as T of char i.e. less<cv T*>(a, b) gives the same results as less<cv
void*>(a, b) which gives the same results as less<cv char*>((cv
char*)(cv void*)a, (cv char*)(cv void*)b) if a and b are pointers to
objects of type cv T.

> I'm also thinking there should be a footnote to 20.3.3/1 saying that if
> A and B are similar types (4.4/4), comp<A>(a,b) returns the same value
> as comp<B>(a,b) (where comp is less, less_equal, etc.). But this might
> be problematic if there is some really funky operator overloading going
> on that does different things based on cv (that should be undefined
> behavior if somebody does that though). This at least should be
> guaranteed for all POD types (especially pointers) that use the
> built-in comparison operators.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> > The standard should do much better than guarantee that these provide a
> > total order, it should guarantee that it can be used to test if memory
> > overlaps, i.e. write a portable memmove. You can imagine a platform
> > where the built-in operators use a uint32_t comparison (this tests for
> > overlap on this platform) but the less<T*> functor is allowed to be
> > defined to use a int32_t comparison.
>
> This is already guaranteed (and your implementation is illegal if any
> objects cross the signed/unsigned address boundary).

5.9/2 "If two pointers p and q of the same type point to different
objects that are not members of the same object or elements of the same
array or to different functions, or if only one of them is null, the
results of p<q, p>q, p<=q, and p>=q are unspecified."

Doesn't look guaranteed to me. Nor can I find anything that says that
objects objects crossing that boundary is illegal.

> The standard already requires that if (p1<p2) is a valid test,
> less(p1,p2) return the same result.  The other operators have the same
> requirement.

Where does it say that?

> This is sufficient to detect overlap.  It could allow overlap to be
> falsely reported, but that doesn't make memmove wrong.  It might make
> memmove less than optimal (ie on an architecture where copy-left was
> cheaper than copy-right).

Well it's not for implementing an efficient memmove, detecting correct
overlap is useful in other cases (especially in debug code for
asserting that 2 objects/arrays don't overlap, think about restricted
pointers in C99, which may make it to C++).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Me wrote:
> > > The standard should do much better than guarantee that these provide a
> > > total order, it should guarantee that it can be used to test if memory
> > > overlaps, i.e. write a portable memmove. You can imagine a platform
> > > where the built-in operators use a uint32_t comparison (this tests for
> > > overlap on this platform) but the less<T*> functor is allowed to be
> > > defined to use a int32_t comparison.
> >
> > This is already guaranteed (and your implementation is illegal if any
> > objects cross the signed/unsigned address boundary).
>
> 5.9/2 "If two pointers p and q of the same type point to different
> objects that are not members of the same object or elements of the same
> array or to different functions, or if only one of them is null, the
> results of p<q, p>q, p<=q, and p>=q are unspecified."
>
> Doesn't look guaranteed to me.

5.9p2 describes ">" and ">=", "<" and "<=". In the last case covered by
that paragraph, the results of "p<q" are completely unspecified in the
last case covered by 5.9p2. Howevever, the results of less<>(p,q),
while individually just as unspecified as the results of p<q, are
collectively required to produce a total order (20.3.3p8). If "p<q"
doesn't produce a total order on the possible values of p and q, this
implies that less<>(p,q) must, in some cases, produce different results
than p<q.

> ... Nor can I find anything that says that
> objects objects crossing that boundary is illegal.

He didn't say that objects crossing that boundary are illegal. In fact,
the existence of an object crossing that boundary is assumed as the
premise of his statement. The conclusion of his statement is that your
example implementation of less<> would be non-conforming. That's
because p<q and less(p,q) would produce different results for two
pointers within the same object, if one pointer pointed below that
boundary, and the other pointed above that boundary.

> > The standard already requires that if (p1<p2) is a valid test,
> > less(p1,p2) return the same result.  The other operators have the same
> > requirement.
>
> Where does it say that?

20.3.3p5: "operator() returns x<y".

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Me wrote:
> > The standard already requires that if (p1<p2) is a valid test,
> > less(p1,p2) return the same result.  The other operators have the same
> > requirement.
>
> Where does it say that?

20.3.3/5 ... less ... returns x < y.

so if x<y is a valid expression, std::less better give the same answer.
 Paragraph 8 says std::less sometimes works even when x<y doesn't.  It
doesn't give std::less license to return something different when x<y
succeeds.

>
> > This is sufficient to detect overlap.  It could allow overlap to be
> > falsely reported, but that doesn't make memmove wrong.  It might make
> > memmove less than optimal (ie on an architecture where copy-left was
> > cheaper than copy-right).
>
> Well it's not for implementing an efficient memmove, detecting correct
> overlap is useful in other cases (especially in debug code for
> asserting that 2 objects/arrays don't overlap, think about restricted
> pointers in C99, which may make it to C++).

AFAICT a segmented architecture (where objects may not cross segment
boundaries) could implement std::less (and siblings) in such a way that
the pointer was treated as an integer, with the segment number being
the least-significant part of the integer.  Within any segment (and
therefor any object) comparisons would match x<y, but tests might make
objects in different segments appear to overlap.  Note that std::equal
would still indicate that no address in either object matched (and a
binary search could be used to detect this in your debug code).

However, I find such an implementation extremely unlikely, and not
worth adding extra verbage in the standard.

I still believe your particular example implementation (objects may
cross the signed/unsigned boundary and for such objects x<y gives
different answers than less(x,y)) is already illegal.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

<wade@stoner.com> skrev i meddelandet
news:1118234038.360273.197460@g43g2000cwa.googlegroups.com...
>
>
>>
> AFAICT a segmented architecture (where objects may not cross segment
> boundaries) could implement std::less (and siblings) in such a way
> that
> the pointer was treated as an integer, with the segment number being
> the least-significant part of the integer.  Within any segment (and
> therefor any object) comparisons would match x<y, but tests might make
> objects in different segments appear to overlap.  Note that std::equal
> would still indicate that no address in either object matched (and a
> binary search could be used to detect this in your debug code).
>
> However, I find such an implementation extremely unlikely, and not
> worth adding extra verbage in the standard.
>

A more likely implementation of a segmented memory is a handle:offset
pair. Here operator< can compare the offsets cheaply, while doing a full
compare in less<T*> might involve an OS call to resolve the handles, and
the paging scheme backing that. It could be *very* expensive to detect
an overlap of objects from different segments.



Bo Persson


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> 20.3.3/5 ... less ... returns x < y.
>
> so if x<y is a valid expression, std::less better give the same answer.
>  Paragraph 8 says std::less sometimes works even when x<y doesn't.  It
> doesn't give std::less license to return something different when x<y
> succeeds.

Ah, that's the thing I was missing.

> AFAICT a segmented architecture (where objects may not cross segment
> boundaries) could implement std::less (and siblings) in such a way that
> the pointer was treated as an integer, with the segment number being
> the least-significant part of the integer. Within any segment (and
> therefor any object) comparisons would match x<y, but tests might make
> objects in different segments appear to overlap.Note that std::equal
> would still indicate that no address in either object matched (and a
> binary search could be used to detect this in your debug code).

The total order restriction requires !less(a,b) && !less(b,a) ==
equal_to(a,b) which would be inconsistent with the builtin == operator.
So this example is wrong given your above interpretation.

> However, I find such an implementation extremely unlikely, and not
> worth adding extra verbage in the standard.

Actually, with your above interpretation of less<T*>, which I
believe/hope is the correct one, it can be used to detect overlap since
it requires less(p,p+1) to always be true for valid array elements (and
returning the same result for cv similar types), which is basically the
constraint I needed.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

[ Note: Forwarded to C++ Committee. -sdc ]

20.3.3/8 "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."

The standard should do much better than guarantee that these provide a
total order, it should guarantee that it can be used to test if memory
overlaps, i.e. write a portable memmove. You can imagine a platform
where the built-in operators use a uint32_t comparison (this tests for
overlap on this platform) but the less<T*> functor is allowed to be
defined to use a int32_t comparison. On this platform, if you use
std::less with the intent of making a portable memmove, comparison on
an array that straddles the 0x7FFFFFFF/0x8000000 boundary can give
incorrect results.

Resolution: Add a footnote to 20.3.3/8 saying:

Given a p1 and p2 such that p1 points to N objects of type T and p2
points to M objects of type T. If [p1,p1+N) does not overlap [p2,p2+M),
less returns the same value when comparing all pointers in [p1,p1+N) to
all pointers in [p2,p2+M). Otherwise, there is a value Q and a value R
such that less returns the same value when comparing all pointers in
[p1,p1+Q) to all pointers in [p2,p2+R) and an opposite value when
comparing all pointers in [p1+Q,p1+N) to all pointers in [p2+R,p2+M).
For the sake of completeness, the null pointer value (4.10) for T is
considered to be an array of 1 object that doesn't overlap with any
non-null pointer to T. less_equal, greater, greater_equal, equal_to,
and not_equal_to give the expected results based on the total ordering
semantics of less. For T of void, treat it as having similar semantics
as T of char i.e. less<cv T*>(a, b) gives the same results as less<cv
void*>(a, b) which gives the same results as less<cv char*>((cv
char*)(cv void*)a, (cv char*)(cv void*)b).


I'm also thinking there should be a footnote to 20.3.3/1 saying that if
A and B are similar types (4.4/4), comp<A>(a,b) returns the same value
as comp<B>(a,b) (where comp is less, less_equal, etc.). But this might
be problematic if there is some really funky operator overloading going
on that does different things based on cv (that should be undefined
behavior if somebody does that though). This at least should be
guaranteed for all POD types (especially pointers) that use the
built-in comparison operators.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]