Why does vector::pop_back invalidate the iterator (end() - 1)?

Question

Note: The question applies to erase, too. See bottom.

---

What's the reason behind the fact that the end() - 1 iterator is invalidated after pop_back is called on a vector?

To clarify, I'm referring to this situation:

std::vector<int> v;
v.push_back(1);
v.push_back(2);

std::vector<int>::iterator i1 = v.begin(), i2 = v.end() - 1, i3 = v.begin() + 1;

v.pop_back();

// i1 is still valid
// i2 is now invalid
// i3 is now invalid too

std::vector<int>::iterator i4 = v.end();

assert(i2 == i4);  // undefined behavior (but why should it be?!)
assert(i3 == i4);  // undefined behavior (but why should it be?!)

Why does this happen? (i.e. when would this invalidation ever prove beneficial for the implementation?)

(Note that this isn't just a theoretical problem. Visual C++ 2013 -- and probably 2012 too -- display an error if you try to do this in debug mode, if you have _ITERATOR_DEBUG_LEVEL set to 2.)

---

Regarding erase:

Note that the same question applies to erase:
Why does erase(end() - 1, end()) invalidate end() - 1?

(So please don't say, "pop_back invalidates end() - 1 because it is equivalent to calling erase(end() - 1, end())"; that's just begging the question.)

Answer 1

The interesting question is really what does it mean for an iterator to be invalidated. And I truly don't have a good answer from the standard. What I do know is that to some extent the standard considers an iterator not as a pointer to a location inside the container, but rather as a proxy to a particular element that lives within the container.

With that in mind, after erasing of a single element in the middle of a vector, all iterators after the point of removal become invalidated as they no longer refer to the same element that they referred to before.

Support for this line of reasoning comes from the iterator invalidation clauses of other operations in the container. For example, on insert, the standard guarantees that if there is no reallocation the iterators before the point of insertion remain valid. Exceptio probat regulam in casibus non exceptis, it invalidates all iterators after the point of insertion.

If the validity of iterators was only related to the fact that there is an element of the container where the iterator points, then none of the iterators would be invalidated with that operation (again, in the absence of reallocations).

Going even further in that line of reasoning, if you consider iterator validity as pointer validity, then none of the iterators into a vector would be invalidated during an erase operation. The end()-1 iterator would become non-dereferencable, but it could remain valid, which is not the case.

Answer 2

pop_back is usually defined in terms of erase(end()-1, end()).

When you erase a range of iterators from a vector, all iterators from the first erased and forward are invalidated. This includes a range of one.

In general, a valid derefencable non input iterator always refers to the same data 'location' until it becomes invalidated. In the case of erase, all non-invalid iterators afterwards have the same value and location currently.

Both of the above rules would have to be amended to get the behavior you want. The first to something like 'unless you erase the last element in so doing, in which case the first erased element becomes the one-past-the-end iterator'. And the still valid iterator will become not dereferencable, a possibly unique state change for an iterator that is, as far as I know, without precedent in C++.

The cost is both extra tricky verbage in the standard to cover your requested behavior and sanity checks for strict iterators. The benefit -- well, I do not see one: in every situation you will have to know exactly what just happened (a very particular iterator just became one past the end instead of being invalidated), and if you know that is the case you could just talk about end.

And words are required. When you call erase( a, b ), every iterator from a on will have its state changed in some way (*a will not return the same value, and how that changes must be specified). C++ takes the easy way, and simply states that every iterator whose state is changed by erase becomes invalid, and using it is undefined behavior: this allows the maximium latitude to the implementer.

In theory, it can also allow for optimizations. If you dereference an iterator before and after an erase operation, the value you get can be considered the same! (assuming no possible indirect modification of the container within object destructors, which can be proven as well).