Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Must size() == end() - begin()? What about the cast?

Tags:

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

like image 858
user541686 Avatar asked Jul 26 '12 00:07

user541686


People also ask

How does vector end work?

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.

Where does end iterator point to?

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.

How do you remove a specific element from a vector in C++?

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.

What happens if you try to move an iterator past-the-end of a sequence?

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.


2 Answers

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.

like image 52
chris Avatar answered Oct 14 '22 12:10

chris


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.

like image 41
AnT Avatar answered Oct 14 '22 12:10

AnT