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

From: David Abrahams (dave_at_[hidden])
Date: 2008-03-20 12:59:02

Sebastian Theophil wrote:
> Hello Dave,
> 

We really ought to be having this discussion in public, so let's please
move to the Boost developers' list.

> I took another look at the standard to make the argument clearer.
>  
>> I don't follow.  Let's try code.
>>
>>  counting_iterator<int> i0(INT_MIN), i1(INT_MAX);
>>  std::iterator_traits<counting_iterator<int> >::difference_type d
>>   = i1-i0;
>>
>> Are you claiming that it's acceptable for d to be -1?
> 
> Yes, that was what I tried to say. Because for all practical purposes 
> 
> 	i0 + d == i1 (Although the behavior is undefined it will work on most systems.)

Here's where you get into the difference between theoretical and actual
portability.

> The other property I tried to express was that comparing two differences for their absolute values is meaningless if d is allowed to be -1 because of overflow.

Ouch; your mailer doesn't wrap lines.

What do you mean by "comparing two differences for their absolute value?"

>>> My fundamental argument is that int is a modulo space which is exactly
>>> why 1) works if B-A is still int. 
> 
>> No, int is not a modulo space.  Overflows induce undefined behavior.
>> Only unsigned integers are a modulo space in C++.
> 
> OK, I believe you know the standard way better than I do, so I admit defeat in this point.

OK.

>>> This is also why (T* - T*) = ptrdiff_t
>>> = int 
> 
>> No, ptrdiff_t is long on most platforms
> 
>>> and not int64. 
> 
>> And it may be a 64-bit int (especially on 64-bit platforms)
> 
> The last point is clear and I should have written that ptrdiff_t = word size or something like that. 
> But back to what the standard says about ptrdiff_t in section 5.7 on Additive Operators
> 
> "When two pointers to elements of the same array object are subtracted, the result is the difference of the subscripts of
> the two array elements. The type of the result is an implementation-defined signed integral type; this type shall be the
> same type that is defined as std::ptrdiff_t in the <cstddef> header (18.1). As with any other arithmetic overflow,
> if the result does not fit in the space provided, the behavior is undefined. In other words, if the expressions P and Q point
> to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i− j provided the
> value fits in an object of type std::ptrdiff_t."
> 
> Clearly, there's no strict requirement on ptrdiff_t except that it is a signed integral type. It clearly doesn’t have to be large enough to prevent overflows so it may have the same size as a processor word be that 4 bytes or 8. In practice that seems to be the preferred way although with a word length ptrdiff_t 

Generally it has nothing to do with the (data) word length.  It is
usually an integral type whose size corresponds to the size of a pointer.

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

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

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

There's a difference between what the standard mandates and what an
implementor should do.  The standard also doesn't say that you have to
support dynamic allocation of more than 10 bytes total.

> I think counting_iterator<T> should behave exactly the same way when T is an integer than when it is an iterator. 

It does, whenever possible.  An iterator's difference type is usually a
type that can be used to represent the difference between any two such
iterators that belong to the same sequence.  That's exactly what we try
to do with counting_iterator<int>.

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

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