Re: [boost] Proposed patch for boost::counting_iterator

From: David Abrahams (dave_at_[hidden])
Date: 2008-03-27 19:05:27

on Thu Mar 20 2008, "Sebastian Theophil" <stheophil-AT-think-cell.com> wrote:

>> > char* c0=(char*)0;
>> > char* c1=(char*)UIntToPtr(std::numeric_limits<size_t>::max());
>> > ptrdiff_t d=c1-c0;
>> > char* c2=d+c0;
>> >
>> > d overflows and in practice is -1 as well. Thus c2==c1.
>> 
>> Yes, but in practice no such array can exist, so it's not a problem.
>> On
>> the other hand, someone *can* reasonably make two
>> counting_iterator<short>s and iterate from SHORT_MIN to SHORT_MAX.  So
>> in that case, representing the difference correctly could be important.
>
> My argument was precisely that on the architectures I'm aware of you
> can do the latter even when difference_type is short because shorts
> behave like a modulo space although they aren't required to do so. 

Yes, you can do the iteration, regardless of the difference_type.
However, you can't accurately measure the distance between two such
iterators unless the difference_type can represent numbers outside the
range of SHRT_MIN..SHRT_MAX.  On the other hand, with a
difference_type of ptrdiff_t you *can* accurately measure the distance
between any two pointers that can be legally subtracted or compared in
C++.

> On the other hand I can iterate over all memory addresses I have
> although I couldn't allocate as much memory for myself. 

Not legally in C++.  Iterating off the end of an array of objects is
undefined behavior.

> Representing the difference between two pointers would be just as
> important.
>
>> > The same holds for
>> >
>> > int n0=INT_MIN;
>> > int n1=INT_MAX;
>> > int dn=n1-n0;
>> > int n2=dn+n0;
>> >
>> > dn is -1 and n2==n1.
>> 
>> Yes, that's because you specified int!  The whole point of
>> numeric_traits<int>::difference_type is to do better than that.
>
> My point is actually that INT_MAX - (-INT_MIN) is defined to be int

No, it's not defined to be anything.  In fact, it's undefined behavior
because, if I remember the standard language correctly, "the result is
outside the representable range of the result type," i.e. an overflow or
underflow.

> because all operands are ints 

It's that way because C does it that way.

> and in this case I think the standard is with me. Please correct me if
> there's a subtlety I missed.

You missed the fact that it's undefined behavior to even mention
-INT_MIN on a 2s compliment machine.  Try throwing this program at the
comeau online compiler:

  #include <climits>
  unsigned x = -INT_MIN;

It's being extra nice and warning you instead of launching a missile or
overwriting your hard drive.

>> >
>> > Of course, the overflow behavior is implementation dependent and it
>> doesn't have to work that nicely. However, my argument is that this
>> fact didn't cause anybody on the standards committee to change the
>> definition for ptrdiff_t.
>> 
>> That's because it's up to QOI.  In other words, an implementor
>> interested in a high-quality implementation will ensure, if possible,
>> that ptrdiff_t works for practical situations on his platform.
>> That's exactly what we tried to do with counting_iterator.
>
> So your argument is ptrdiff_t shouldn't be int in the MSVC library
> implementation because that's a bad choice on a 32 bit system?

No, I'm not.  ptrdiff_t is a perfectly good choice for representing any
distance between pointers that can be measured in C++ without invoking
undefined behavior, as long as the system's dynamic allocator won't
give you a block of memory whose size is outside the representable range
of ptrdiff_t and as long as the same goes for the implementation limits
for declaring arrays in the compiler.

>> > In both cases it can return iterator_traits<T>::difference_type.
>> std::iterator_traits<int>::difference_type is specialized to be int.
>> 
>> I would be shocked if you could demonstrate that
>> std::iterator_traits<int>::difference_type is specialized to be int in
>> the standard, or indeed any implementation of C++.
>
> I don't find any specialization for iterator_traits<int> in the
> standard but of course I checked my STL headers and found this
> directly in <xutility>
>
>
> template<> struct iterator_traits<short>
> 	{	// get traits from integer type
> 	typedef _Int_iterator_tag iterator_category;
> 	typedef short value_type;
> 	typedef short difference_type;
> 	typedef short distance_type;
> 	typedef short * pointer;
> 	typedef short& reference;
> 	};
>
> template<> struct iterator_traits<unsigned short>
> 	{	// get traits from integer type
> 	typedef _Int_iterator_tag iterator_category;
> 	typedef unsigned short value_type;
> 	typedef unsigned short difference_type;
> 	typedef unsigned short distance_type;
> 	typedef unsigned short * pointer;
> 	typedef unsigned short& reference;
> 	};
>
> template<> struct iterator_traits<int>
> 	{	// get traits from integer type
> 	typedef _Int_iterator_tag iterator_category;
> 	typedef int value_type;
> 	typedef int difference_type;
> 	typedef int distance_type;	
> 	typedef int * pointer;
> 	typedef int& reference;
> 	};

Wow, I'm impressed.  Not sure why they'd do that, but there you go.

>
> /*
>  * Copyright (c) 1992-2005 by P.J. Plauger.  ALL RIGHTS RESERVED.
>  * Consult your license regarding permissions and restrictions.
>  */
> /*
>  * This file is derived from software bearing the following
>  * restrictions:
>  *
>  * Copyright (c) 1994
>  * Hewlett-Packard Company
>  *
> ...
> */
>
> So that's HP and P.J. Plauger who agree with me :-)

No, it's just Bill Plaugher, unless you can show that the code was
present in the HP implementation.

> BTW, did I read right that the boost numeric_traits difference_type
> definition for unsigned int would be intmax_t which again is int64
> although the standard says unsigned integers are a modulo space?

Probably.  The intended behavior of numeric_traits' difference_type is
that it's a type that's best able to represent the integer difference
between any two numbers of a given type.  It's not supposed to account
for modulo arithmetic.  If you want that behavior for unsigned int, it's
trivial to get it, so why would we need numeric_traits for that?

> I know my arguments rely on "observed behavior", i.e. on the fact that
> integers behave like a modulo space on Intel processors which MSVC is
> kind of limited to. 

What is the modulus for int?  How do you account for the fact that
INT_MIN != -INT_MAX?

> The only other argument I can make is that counting_iterator should in
> my view be an iterator interface to the integral types with their
> well-known limitations. 

Why?

> I can iterate from SHORT_MIN to SHORT_MAX *and* I can compute the
> differences just as well as I can with shorts themselves. 

Not so, as Steven pointed out, because of integral promotion.

> If my implementation handles overflows fine, I don't have any
> problems. 

Seriously?

Suppose you adapt a counting_iterator with a transform iterator that
applies a monotonically increasing function.  Now binary search in a
range of these adapted iterators for the place where the function's
result crosses zero.  What do you think will happen if, when measuring
the distance from the beginning to the end of a valid range,
binary_search sees a negative number?
             
> If it doesn't, why should counting_iterator try to be "betterer" than
> ptrdiff_t?

Why not try to do as well as we can?

-- 
Dave Abrahams
Boost Consulting
http://boost-consulting.com