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