insert_iterator invalidation rules

Question

What actions to an STL container can invalidate a C++ std::insert_iterator referencing that container? Is an insert_iterator valid iff its underlying iterator (protected member iter) is, subject to the usual Iterator invalidation rules?

Related: std::insert_iterator and iterator invalidation gives an example of an invalid insert_iterator but did not elucidate the rules.

Answer 1

Is an insert_iterator valid iff its underlying iterator (protected member iter) is,

You are correct, that's the reason that protected member is listed in the spec and the functions that work on the insert_iterator (specifically, operator=, since the rest is no-ops) are defined in terms of functions that access iter

Answer 2

Well, the answer depends on what specifically you are asking about.

(To get this out of the way, I'd like to immediately note that your "Related" link is completely unrelated. The problem with the code at that link has absolutely nothing to do with insert_iterator invalidation. The author of that question misinterpreted the issue and ended up trying to solve a non-existent problem, while the real problem persisted. I provided an extra answer to that question as well.)

If you create an insert_iterator ins from a valid iterator container::iterator it and then independently do something to the container that would invalidate it, then ins will also get invalidated. This is something that is natural to expect. The ins has no way to know that something happened to the container if you do it independently.

However, at the same time insert_iterator has self-repairing properties when it is used for insertion. For example, if you use insert_iterator ins to insert data into a vector, ins remains valid even if vector goes through reallocation. I.e. even though vector reallocation is a massive iterator-invalidating event, it does not damage ins (assuming, of course, that the reallocation was triggered by an insertion performed through ins).

This follows from the standard insertion algorithm

it = container->insert(it, value);
++it;

where it is the underlying insertion point iterator stored inside insert_iterator. Front-inserting and back-inserting iterators also have the same "self-healing" properties. A potentially invalid internal iterator gets immediately re-validated.

To illustrate the difference, consider this simple example

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;

for (unsigned n = 20; n > 0; --n)
  v.insert(it, rand());

This code is generally invalid, since it is very likely that the container will reallocate during insertion cycle, thus invalidating it and rendering all further insertions invalid.

At the same time this code

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

is guaranteed to work fine, regardless of whether the vector reallocates or not.