Are Non Dereferenced Iterators Past the "One Past-The-End" Iterator of an Array Undefined Behavior

Are non dereferenced iterators past the one past-the-end iterator of an array undefined behavior?

Yes, your program has undefined behaviour if you form such a pointer.

That's because the only way you can do so is to increment a valid pointer past the bounds of the object it points inside, and that is an undefined operation.

[C++14: 5.7/5]: When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, provided they exist. Moreover, 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, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

An uninitialised pointer is not the same thing because you never did anything to "get" that pointer, other than declaring it (which is obviously valid). But you can't even evaluate it (not dereference — evaluate) without imbuing your program with undefined behaviour. Not until you've assigned it a valid value.

As a sidenote, I would not call these "past-the-end" iterators/pointers, a term in C++ which specifically means the "one past-the-end" iterator/pointer, which is valid (e.g. cend(foo) itself). You're waaaay past the end. ;)

Is &*vector::end() undefined behavior?

It's undefined behaviour. That is, behaviour not defined by the C++ standard. It may be defined by the implementation. More likely, it will happen to work by chance in some situations and not others.

In this case, if the iterator is a raw pointer the compiler will likely optimise &*i into a no-op, so it will likely work. Stroustrup may have known his vector used raw pointers as iterators.

Even if the compiler doesn't optimise it away, in practice, it's only likely to fail if the vector's memory happens to be allocated to end at a segment boundary. (Or if the iterator implementation is written to check for being non-dereferenceable, eg for debugging purposes.)

In C++11 this should be written as:

sort(container.data(), container.data()+container.size()); 

c++ what's the result of iterator + integer when past-end-iterator?

It's Undefined Behavior. Anything may happen. Just to name a few of the options: Nothing at all, program exits, exception, crash.

Why is comparing against end() iterator legal?

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

value of set::find() if not found in container

auto a2 = s1.find(100);
cout << "find(100) : " << *a2 << endl;

Here you dereference (*a2) the end iterator. That is undefined behaviour - remember that s1.end() points to one past the last element and must not be dereferenced.

You're unlucky that you got a value from that dereference - it would be more convenient if your program crashed or otherwise reported the problem. But UB doesn't have to be diagnosed in any way.

You might have spotted the problem if you had run your program using Valgrind's memory checker (or your preferred equivalent). But there's a good chance that's unable to detect it (if the set has over-allocated, which is likely).

Should I allow my custom iterator to go past the end?

It doesn't really matter.

To conform to STL conventions, you need a begin() method which returns an iterator to the start of the collection, and an end() method which returns an iterator to one past the last element. So advancing to end() and comparing for equality is well-defined. However advancing beyond end() is not well-defined. It's better to throw an error, but not necessary, especially if that involves otherwise redundant checks. If people don't use the iterators correctly, you are not responsible for any bugs.

---

Related Topics