question on vector<char>::difference_type
subramanian100in@yahoo.com, India
consider the following program named x.cpp :
#include <cstdlib>
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main()
{
cout << "numeric_limits< vector<char>::size_type >::max() = "
<< numeric_limits< vector<char>::size_type >::max()
<< endl;
cout << "numeric_limits< vector<char>::difference_type >::max
() = "
<< numeric_limits< vector<char>::difference_type >::max()
<< endl;
vector<char> v((numeric_limits< vector<char>::size_type >::max() -
1)/2 + 3, 100);
cout << "vector size = " << v.size() << endl;
vector<char>::const_iterator first = v.begin();
vector<char>::const_iterator last = v.end();
cout << "vector<char>::difference_type = " << last - first <<
endl;
return EXIT_SUCCESS;
}
I compiled it with g++3.4.3 as
g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
and ran it under RedHat Linux on a Pentium Dual Core processor-based
machine.
It produced the following output:
numeric_limits< vector<char>::size_type >::max() = 4294967295
numeric_limits< vector<char>::difference_type >::max() = 2147483647
vector size = 2147483650
vector<char>::difference_type = -2147483646
The actual difference between last and first would be the size of the
vector which is 2147483650. Since the vector<type
name>::difference_type is a signed quantity whose maximum on my
machine and the implementation that I am using, is displayed to be
2147483647, I happen to see a wrong value displayed for 'last -
first'.
Why is the difference_type not large enough to hold the distance
between any two iterators ?
Kindly explain.
Thanks
V.Subramanian
Victor Bazarov
> Why is the difference_type not large enough to hold the distance
> between any two iterators ?
That's a good question you should most likely be asking the implementors
of the standard library you're using. The quantities and the types are
implementation-defined. Some implementors *could* decide to use a
larger signed type for 'difference_type' just to satisfy that
requirement. Apparently in the particular implementation you use, they
didn't. Why?... How should we know?
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
James Kanze
> subramanian10...@yahoo.com, India wrote:
> > I wrote the following program for learning purpose only.
> > [..]
> > Why is the difference_type not large enough to hold the
> > distance between any two iterators ?
> That's a good question you should most likely be asking the
> implementors of the standard library you're using. The
> quantities and the types are implementation-defined. Some
> implementors *could* decide to use a larger signed type for
> 'difference_type' just to satisfy that requirement.
> Apparently in the particular implementation you use, they
> didn't. Why?... How should we know?
Does the implementation actually have a choice? I can't find
any concrete requirement in the C standard saying that ptrdiff_t
must have the same size as size_t, but this would seem to be the
intent. Particularly as the standard says that subtraction of
two pointers is undefined behavior if the result is not
representable in a ptrdiff_t---the standard explicitly caters to
the case in question.
Of course, the code in question dealt with std::vector and a
difference between two iterators. In this case, the C++
standard is somewhat less explicit, but it does say that a
precondition to the expression is "there exists a value n of
Distance such that a + b == b[...]"; in the case in question,
the pre-condition is not met, so the behavior is undefined.
Logically, of course, the error is using two types, size_t and
ptrdiff_t, rather than just ptrdiff_t. Still, an implementation
could detect the error (although I suspect that most consider it
too rare to be worth the bother), or simply refuse to allocate a
container so large that the error could occur, making max_size()
equal to:
min( numeric_limits< ptrdiff_t >::max(),
numeric_limits< size_t >::max() / sizeof( T ) )
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Bo Persson
In addition to this, i belive the OP's result is Linux specific, in
that it allows him to actually pretend to allocate a vector that
large.
On Windows I would expect either a length_error exception telling us
that we are out of user address space, or (if allocating a few bytes
less) a bad_alloc saying that it isn't available anyway.
That's just another instance of the undefined behavior, of course.
Bo Persson
James Kanze
Not necessarily Linux specific, but it obviously depends on the
OS and the hardware. And I'm not sure what you mean by
"pretend"; if Linux is configured correctly (it usually isn't),
or if there's enough memory and other processes aren't using it
all (usually the case on the machines I use), there's no
problem; the vector is real, and fully usable.
> On Windows I would expect either a length_error exception
> telling us that we are out of user address space, or (if
> allocating a few bytes less) a bad_alloc saying that it isn't
> available anyway.
Yes. Depending on the implementation of the library, I'd expect
either length_error or bad_alloc under Windows, because Windows
limits 32 bit programs to half of the address space. But that's
just a particularity of Windows---Linux limits them to 3/4 (I
think), and Solaris allows 100% of the address space, at least
on a Sparc.
> That's just another instance of the undefined behavior, of
> course.
If you attempt to extend the vector beyond max_size(), the
behavior isn't undefined. Nor if the vector can't allocate the
necessary memory.
subramanian100in@yahoo.com, India
> James Kanze (GABI Software) email:james.ka...@gmail.com
> Conseils en informatique orientée objet/
> Beratung in objektorientierter Datenverarbeitung
> 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
The following question is related to the program description given at
the beginning of the original post in this thread.
Given C++ Standard Library implementations like g++ 3.4.3(Under RedHat
Linux) wherein the the maximum value that can be stored in
vector<char>::difference_type is smaller than the maximum value that
can be stored in vector<char>::size_type, what should I do to
calculate the difference between two iterators in such a way that the
correct distance between the iterators is returned - that is, how do I
calculate the difference between two iterators when the difference
overflows or underflows the maximum or minimum values of
vector<char>::difference_type (as it overflows in the example program
I have given) ?
Is it possible to know whether such a difference between iterators
would overflow or underflow ?
Is it possible to write code which uses implementation-defined types
like vector<T>::difference_type and at the same time portable across
different implementations of the C++ Standard library ?
Kindly explain.
Thanks
V.Subramanian
Juha Nieminen
> Given C++ Standard Library implementations like g++ 3.4.3(Under RedHat
> Linux) wherein the the maximum value that can be stored in
> vector<char>::difference_type is smaller than the maximum value that
> can be stored in vector<char>::size_type, what should I do to
> calculate the difference between two iterators in such a way that the
> correct distance between the iterators is returned - that is, how do I
> calculate the difference between two iterators when the difference
> overflows or underflows the maximum or minimum values of
> vector<char>::difference_type (as it overflows in the example program
> I have given) ?
The difference type is signed because when you do a "iter2 - iter1",
it accounts for the possibility that iter1 is larger (or, more
precisely, points to a value which is at a higher position in the
vector) than iter2, in which case the [iter1,iter2] range is actually
reversed.
If you know for sure that iter2 will always be >= iter1, then an
unsigned difference type could be used for their difference, in which
case you get the whole range of the maximum capacity of the vector.
If your target system uses integers using two's complement
representation (as basically all computers in this universe do), you can
simply cast the result of the difference to an unsigned type (size_t)
and you'll get the correct result even if the temporary value (before
the cast) had overflowed.
subramanian100in@yahoo.com, India
In the expression,
min( numeric_limits< ptrdiff_t >::max(),
numeric_limits< size_t >::max() / sizeof( T ) )
numeric_limits< ptrdiff_t >::max() is of 'int' type whereas
numeric_limits< size_t >::max() / sizeof( T ) is of 'unsigned' type.
So how do I compare a signed type with an unsigned type(The g++3.4.3
compiler gives warning message for comparing signed and unsigned
types). Is it correct to compare signed and unsigned types ?
Kindly clarify.
Thanks
V.Subramanian
James Kanze
> The following question is related to the program description
> given at the beginning of the original post in this thread.
> Given C++ Standard Library implementations like g++
> 3.4.3(Under RedHat Linux) wherein the the maximum value that
> can be stored in vector<char>::difference_type is smaller than
> the maximum value that can be stored in
> vector<char>::size_type, what should I do to calculate the
> difference between two iterators in such a way that the
> correct distance between the iterators is returned - that is,
> how do I calculate the difference between two iterators when
> the difference overflows or underflows the maximum or minimum
> values of vector<char>::difference_type (as it overflows in
> the example program I have given) ?
It depends on how portable you need to be. For 32 bit g++, on a
PC, casting the values returned by size() to long long would do
the trick. For 64 bit g++, no.
> Is it possible to know whether such a difference between
> iterators would overflow or underflow ?
if ( vect.size() > std::numeric_limits< ptrdiff_t >::max() ) {
// iterator difference can overflow...
}
> Is it possible to write code which uses implementation-defined
> types like vector<T>::difference_type and at the same time
> portable across different implementations of the C++ Standard
> library ?
Yes. Just don't create containers with more than
std::numeric_limits< ptrdiff_t >::max() elements, and there's no
problem.
--
James Kanze (GABI Software) email:james...@gmail.com
James Kanze
> subramanian10...@yahoo.com, India wrote:
[...]
> The difference type is signed because when you do a "iter2 -
> iter1", it accounts for the possibility that iter1 is larger
> (or, more precisely, points to a value which is at a higher
> position in the vector) than iter2, in which case the
> [iter1,iter2] range is actually reversed.
> If you know for sure that iter2 will always be >= iter1, then
> an unsigned difference type could be used for their
> difference, in which case you get the whole range of the
> maximum capacity of the vector.
And how do you get the subtraction of two iterators to give you
an unsigned type?
> If your target system uses integers using two's complement
> representation (as basically all computers in this universe
> do),
Except those that don't. (Unisys mainframes. And perhaps
others.)
> you can simply cast the result of the difference to an
> unsigned type (size_t) and you'll get the correct result even
> if the temporary value (before the cast) had overflowed.
The results of converting a ptrdiff_t into a size_t are strictly
defined by the standard, and result in the same results as you
would get from a 2's complement machine, regardless of the
hardware representation. The problem comes earlier: the
subtraction of the iterators is undefined behavior. In the case
of std::vector, there's a very good chance that it will
work---the iterators will behave very much like pointers. In
the case of other containers (e.g. std::deque), it's less
certain.
--
James Kanze (GABI Software) email:james...@gmail.com
James Kanze
<subramanian10...@yahoo.com> wrote:
[...]
> In the expression,
> min( numeric_limits< ptrdiff_t >::max(),
> numeric_limits< size_t >::max() / sizeof( T ) )
> numeric_limits< ptrdiff_t >::max() is of 'int' type whereas
> numeric_limits< size_t >::max() / sizeof( T ) is of 'unsigned' type.
> So how do I compare a signed type with an unsigned type(The g++3.4.3
> compiler gives warning message for comparing signed and unsigned
> types). Is it correct to compare signed and unsigned types ?
The compiler is being a bit paranoic (although I really don't
blame it). It's perfectly safe to compare signed and unsigned
types *IF* the signed types only contain non-negative values.
Which is guaranteed for numeric_limits<...>::max(). If the
signed type might contain a negative value, on the other hand,
the issue is tricker, and things like:
unsigned i = 3 ;
int j = -1 ;
if ( i < j ) ...
give rather surprising results.
If the warning bothers you:
min( static_cast< size_t >(
numeric_limits< ptrdiff_t >::max() ),
numeric_limits< size_t >::max() / sizeof( T ) )
(Actually, if min is std::min, you probably need to do this to
get it to compile anyway.)
--
James Kanze (GABI Software) email:james...@gmail.com