CTR32-CPP. Do not use iterators invalidated by container modification

Reallocation can occur when a member function modifies its container. Modifying member functions include reserve() and resize(), push_back(), pop_back(), erase(), clear(), insert(), and others. In addition, assignment operations and modifying algorithms can also cause reallocation. When a container reallocates its elements, their addresses change. This applies only to contiguous-memory iterators, in particular std::vector, std::deque and std::string.

In general iterators on node-based containers such as std::list are not invalidated via modification of the container, unless the element referenced by the iterator is itself erased.

Pointers and references to objects within a container are also invalidated when iterators are invalidated. A single exception applies for the std::deque class: it preserves pointers and references to internal objects upon inserts to either its beginning or its end, but it does not preserve iterators.

Consequently, the values of existing iterators may be invalidated [Kalev 99]. Using invalid iterators yields undefined results.

Non-Compliant Code Example

In this example, the iterator pos is invalidated after the call to insert, and subsequent loop iterations have undefined behavior.

double data[5] = { 2.3, 3.7, 1.4, 0.8, 9.6 };

deque<double> d;
deque<double>::iterator pos = d.begin();

for (size_t i = 0; i < 5; ++i) {
  d.insert(pos++, data[i] + 41);
}

Compliant Solution 1

Update pos each time insert is called to keep the iterators valid, and then increment it:

double data[5] = { 2.3, 3.7, 1.4, 0.8, 9.6 };

deque<double> d;
deque<double>::iterator pos = d.begin();

for (size_t i = 0; i < 5; ++i) {
  pos = d.insert(pos, data[i] + 41);
  ++pos;
}

Compliant Solution 2

Use one of the STL algorithms.

double data[5] = { 2.3, 3.7, 1.4, 0.8, 9.6 };
deque<double> d;

transform(data, data+5,
    inserter(d, d.begin()),
    bind2nd(plus<int>(), 41));

Non-compliant Code Example (std::string::data())

In this non-compliant code example, data is to be considered out-of-scope just after the call to replace.

const char *data = example_string.data();
example_string.replace(0, 2, "bb");
char val = data[1];

Compliant Solution (std::string::data())

In this compliant solution, the data array is created after modifications to the example string are complete. The modification makes the code compliant: replace is called before the call to data().

const char *data = example_string.data();
example_string.replace(0, 2, "bb");
data = example_string.data();
char val = data[1];

Risk Assessment

Using invalid iterators yields undefined results.

Bibliography

[Meyers 01] Item 43: Prefer algorithm calls to hand-written loops.
[Sutter 04] Item 84: Prefer algorithm calls to handwritten loops.
[Kalev 99] ANSI/ISO C++ Professional Programmer's Handbook.
[ISO/IEC 14882-2003] Section 24: Iterators Library.

      06. Containers (CTR)      CTR33-CPP. Guarantee that copies are made into storage of sufficient size