question on vector<char>::difference_type

[subramanian100in]

I wrote the following program for learning purpose only.

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]

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?

V

 

[James Kanze]

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

 

[Bo Persson]

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

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]

(e-mail address removed), 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 ) )

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.

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]

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:[email protected]
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]

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:[email protected]
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

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]

(e-mail address removed), 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 ) )

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]

(e-mail address removed), 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]

On Aug 3, 9:52 am, "(e-mail address removed), 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 ?

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