Menu
From what I understand, the purpose of size_type and difference_type is not merely the sign -- it was also meant to address e.g. segmented architectures and such, where they might be of different sizes.
With that context, if I have a container with random-access iterators, is it safe for me to perform a static_cast between its difference_type and size_type values at will, on the grounds that end() - begin() must always be equal to size(), when either is casted?
(The use case, for example, is to create a container whose size is equal to the number of elements between two iterators, or the reverse: to copy a container of a certain size onto a range delimited by iterators.)
Anything I should watch out for before casting (e.g. loss of data)?
858
The C++ function std::vector::end() returns an iterator which points to past-the-end element in the vector container. The past-the-end element is the theoretical element that would follow the last element in the vector.
end() does not return the iterator to the last element, rather it returns iterator to past-the-last-element. The iterator to the last element is just before it; that is, if it points to the last element, then ++it makes it to point to past-the-last-element. The language specification calls it past-the-end iterator.
The C++ vector has many member functions. Two of these member functions are erase() and pop_back(). pop_back() removes the last element from the vector. In order to remove all the elements from the vector, using pop_back(), the pop_back() function has to be repeated the number of times there are elements.
Obviously if the iterator is advanced past the last element inside the loop the comparison in the for-loop statement will evaluate to false and the loop will happily continue into undefined behaviour.
Here's what the C++11 standard has to say on various things here:
§ 23.2.1
Expression: difference_type
Return Type: signed integer type
Operational Semantics: -
Assertion/note, pre-/post-condition: is identical to the difference type of iterator and const_iterator
Complexity: compile-time
Expression: size_type
Return Type: unsigned integer type
Operational Semantics: -
Assertion/note, pre-/post-condition: size_type can represent any non-negative value of difference_type
Complexity: compile-time
Expression: size()
Return Type: size_type
Operational Semantics: distance(begin(),end())
Assertion/note, pre-/post-condition: -
Complexity: constant
Let's make sure size() is equivalent to end() - begin():
§ 24.4.4/4
distance():
Effects: If InputIterator meets the requirements of random access iterator,
returns (last - first); otherwise, returns the number of increments needed
to get from first to last
Since your container has random-access iterators, this holds true. That's that. As you can see in the first box,
size_type can represent any non-negative value of difference_type
From that, we have that the cast from difference_type to size_type should be valid for all non-negative values.
52
I don't think it is always safe. This historical issue existed since first specification of C language, where ptrdiff_t is not guaranteed to cover the entire positive range of size_t. For obvious reasons, this issue carries over to the specification of std::vector.
With standard C++ containers, it is guaranteed that size_type covers the non-negative range of difference_type, but the reverse coverage is not guaranteed.
However, the relationship between size() and end() - begin() for a standard container can be guaranteed by other means. The implementation is free to impose its own limitations on the maximum container size, which are exposed through container::max_size() function. It can artificially restrict the maximum size to make sure the subtraction never overflows.
P.S. I'd say that the reason for difference_type's existence is just the sign and nothing else. To be completely "safe" difference_type should be 1 bit longer than size_type. This is often difficult to achieve in practice, which is why it is not required by the language specification.
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
