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.

score 2 · Accepted Answer · answered Jul 04 '12 at 22:13

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

AnT stands with Russia · Answer 2 · 2012-07-04T23:40:19.620

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.

Your first point is what I meant by 'subject to the usual invalidation rules.' Your second point is illuminating: an `insert_iterator` may invalidate its _own_ internal iterator, via the call to `insert()`, only to revalidate it by exploiting the fact that `insert()` returns a valid iterator. However, at every sequence point in the standard insertion algorithm you describe, I believe that the iterators are both valid or invalid; thus I believe the if-and-only-if (and accepted answer) still holds. — nknight, Jul 04 '12 at 23:36
@nknight: I'm not sure I understand what you mean by *"at every sequence point in the standard insertion algorithm you describe, I believe that the iterators are both valid or invalid"* — AnT stands with Russia, Jul 04 '12 at 23:43
I was referring to the first line of your first code snippet. There is a sequence point just before the call to `container->insert()`, another just after returning and having made a local copy of the return value, and then another after the assignment (overwrite) of `it`. I was arguing that at any of these three sequence points, both `it` and its enclosing `insert_iterator` would be considered both valid or both invalid. I was saying that while this behavior is a useful aspect of an `insert_iterator`, I don't think it is a counterexample to the if-and-only-if claim. — nknight, Jul 05 '12 at 17:35

insert_iterator invalidation rules

2 Answers2