STL30-CPP. Use Valid Iterators

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. Consequently, the values of existing iterators are 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));

Risk Assessment

Using invalid iterators yields undefined results.

References

[[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.

STL00-CPP. Understand how container classes are stored      14. Templates and the STL (TPL)      STL31-CPP. Use Valid Iterator Ranges