9.3.6. Container Operations May Invalidate Iterators

Operations that add or remove elements from a container can invalidate pointers, references, or iterators to container elements. An invalidated pointer, reference, or iterator is one that no longer denotes an element. Using an invalidated pointer, reference, or iterator is a serious programming error that is likely to lead to the same kinds of problems as using an uninitialized pointer (§ 2.3.2, p. 54).

After an operation that adds elements to a container

• Iterators, pointers, and references to a vector or string are invalid if the container was reallocated. If no reallocation happens, indirect references to elements before the insertion remain valid; those to elements after the insertion are invalid.

• Iterators, pointers, and references to a deque are invalid if we add elements anywhere but at the front or back. If we add at the front or back, iterators are invalidated, but references and pointers to existing elements are not.

• Iterators, pointers, and references (including the off-the-end and the before-the-beginning iterators) to a list or forward_list remain valid,

It should not be surprising that when we remove elements from a container, iterators, pointers, and references to the removed elements are invalidated. After all, those elements have been destroyed. After we remove an element,

• All other iterators, references, or pointers (including the off-the-end and the before-the-beginning iterators) to a list or forward_list remain valid.

• All other iterators, references, or pointers to a deque are invalidated if the removed elements are anywhere but the front or back. If we remove elements at the back of the deque, the off-the-end iterator is invalidated but other iterators, references, and pointers are unaffected; they are also unaffected if we remove from the front.

• All other iterators, references, or pointers to a vector or string remain valid for elements before the removal point. Note: The off-the-end iterator is always invalidated when we remove elements.

Writing Loops That Change a Container

Loops that add or remove elements of a vector, string, or deque must cater to the fact that iterators, references, or pointers might be invalidated. The program must ensure that the iterator, reference, or pointer is refreshed on each trip through the loop. Refreshing an iterator is easy if the loop calls insert or erase. Those operations return iterators, which we can use to reset the iterator:

// silly loop to remove even-valued elements and insert a duplicate of odd-valued elements
vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin(); // call begin, not cbegin because we're changing vi
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter);  // duplicate the current element
        iter += 2; // advance past this element and the one inserted before it
    } else
        iter = vi.erase(iter);          // remove even elements
        // don't advance the iterator; iter denotes the element after the one we erased
}

This program removes the even-valued elements and duplicates each odd-valued one. We refresh the iterator after both the insert and the erase because either operation can invalidate the iterator.

After the call to erase, there is no need to increment the iterator, because the iterator returned from erase denotes the next element in the sequence. After the call to insert, we increment the iterator twice. Remember, insert inserts before the position it is given and returns an iterator to the inserted element. Thus, after calling insert, iter denotes the (newly added) element in front of the one we are processing. We add two to skip over the element we added and the one we just processed. Doing so positions the iterator on the next, unprocessed element.

Avoid Storing the Iterator Returned from end

When we add or remove elements in a vector or string, or add elements or remove any but the first element in a deque, the iterator returned by end is always invalidated. Thus, loops that add or remove elements should always call end rather than use a stored copy. Partly for this reason, C++ standard libraries are usually implemented so that calling end() is a very fast operation.

As an example, consider a loop that processes each element and adds a new element following the original. We want the loop to ignore the added elements, and to process only the original elements. After each insertion, we’ll position the iterator to denote the next original element. If we attempt to “optimize” the loop, by storing the iterator returned by end(), we’ll have a disaster:

// disaster: the behavior of this loop is undefined
auto begin = v.begin(),
     end = v.end(); // bad idea, saving the value of the end iterator
while (begin != end) {
    // do some processing
    // insert the new value and reassign begin, which otherwise would be invalid
    ++begin;  // advance begin because we want to insert after this element
    begin = v.insert(begin, 42);  // insert the new value
    ++begin;  // advance begin past the element we just added
}

The behavior of this code is undefined. On many implementations, we’ll get an infinite loop. The problem is that we stored the value returned by the end operation in a local variable named end. In the body of the loop, we added an element. Adding an element invalidates the iterator stored in end. That iterator neither refers to an element in v nor any longer refers to one past the last element in v.

Rather than storing the end() iterator, we must recompute it after each insertion:

// safer: recalculate end on each trip whenever the loop adds/erases elements
while (begin != v.end()) {
    // do some processing
    ++begin;  // advance begin because we want to insert after this element
    begin = v.insert(begin, 42);  // insert the new value
    ++begin;  // advance begin past the element we just added
}