Why is comparing against "end()" iterator legal?

Question

According to C++ standard (3.7.3.2/4) using (not only dereferencing, but also copying, casting, whatever else) an invalid pointer is undefined behavior (in case of doubt also see this question). Now the typical code to traverse an STL containter looks like this:

std::vector<int> toTraverse;
//populate the vector
for( std::vector<int>::iterator it = toTraverse.begin(); it != toTraverse.end(); ++it ) {
    //process( *it );
}

std::vector::end() is an iterator onto the hypothetic element beyond the last element of the containter. There's no element there, therefore using a pointer through that iterator is undefined behavior.

Now how does the != end() work then? I mean in order to do the comparison an iterator needs to be constructed wrapping an invalid address and then that invalid address will have to be used in a comparison which again is undefined behavior. Is such comparison legal and why?

Answer 1

Huh? There's no rule that says that iterators need to be implemented using nothing but a pointer.

It could have a boolean flag in there, which gets set when the increment operation sees that it passes the end of the valid data, for instance.

Answer 2

The only requirement for end() is that ++(--end()) == end(). The end() could simply be a special state the iterator is in. There is no reason the end() iterator has to correspond to a pointer of any kind.

Besides, even if it were a pointer, comparing two pointers doesn't require any sort of dereference anyway. Consider the following:

char[5] a = {'a', 'b', 'c', 'd', 'e'};
char* end = a+5;
for (char* it = a; it != a+5; ++it);

That code will work just fine, and it mirrors your vector code.

Answer 3

The implementation of a standard library's container's end() iterator is, well, implementation-defined, so the implementation can play tricks it knows the platform to support.
If you implemented your own iterators, you can do whatever you want - so long as it is standard-conform. For example, your iterator, if storing a pointer, could store a NULL pointer to indicate an end iterator. Or it could contain a boolean flag or whatnot.

Answer 4

Besides what was already said (iterators need not be pointers), I'd like to point out the rule you cite

According to C++ standard (3.7.3.2/4) using (not only dereferencing, but also copying, casting, whatever else) an invalid pointer is undefined behavior

wouldn't apply to end() iterator anyway. Basically, when you have an array, all the pointers to its elements, plus one pointer past-the-end, plus one pointer before the start of the array, are valid. That means:

int arr[5];
int *p=0;
p==arr+4; // OK
p==arr+5; // past-the-end, but OK
p==arr-1; // also OK
p==arr+123456; // not OK, according to your rule

Answer 5

Simple. Iterators aren't (necessarily) pointers.

They have some similarities (i.e. you can dereference them), but that's about it.

Answer 6

One past the end is not an invalid value (neither with regular arrays or iterators). You can't dereference it but it can be used for comparisons.

std::vector<X>::iterator it;

This is a singular iterator. You can only assign a valid iterator to it.

std::vector<X>::iterator it = vec.end();

This is a perfectly valid iterator. You can't dereference it but you can use it for comparisons and decrement it (assuming the container has a sufficient size).

Answer 7

You're right that an invalid pointer can't be used, but you're wrong that a pointer to an element one past the last element in an array is an invalid pointer - it's valid.

The C standard, section 6.5.6.8 says that it's well defined and valid:

...if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object...

but cannot be dereferenced:

...if the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated...