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

From: Sebastian Theophil (stheophil_at_[hidden])
Date: 2008-03-20 14:25:33

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

It's portable if arithmetic is implemented using 2's complement if I'm not mistaken. But of course, this is not required to be the case.

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

If differences are represented as ints then 

        INT_MAX - (-INT_MIN) < INT_MAX - 0

If the difference is e.g. an int64 then as expected

        INT_MAX - (-INT_MIN) > INT_MAX - 0

If anyone relies on either behavior, changing the difference type may be a problem. 
 
> > 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. On the other hand I can iterate over all memory addresses I have although I couldn't allocate as much memory for myself. 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 because all operands are ints and in this case I think the standard is with me. Please correct me if there's a subtlety I missed. I would need to upcast explicitly which is what the counting_iterator does. 

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

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

/*
 * 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 :-)

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?

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. 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. I can iterate from SHORT_MIN to SHORT_MAX *and* I can compute the differences just as well as I can with shorts themselves. If my implementation handles overflows fine, I don't have any problems. If it doesn't, why should counting_iterator try to be "betterer" than ptrdiff_t?

Regards
Sebastian

--
Sebastian Theophil · stheophil_at_[hidden]
Software Engineer
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · fax [phone]
Geschäftsführer: Dr. Markus Hannebauer, Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229