Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509, Advanced Programming II

9 October 2003, Iterator Invalidation

Iterator Invalidation

The iterator version of the dangling pointer problem.

Distinguishing Features

Iteration invalidation results from complex and variable background behavior.
Iteration invalidation can be inconsistent.
- Sometimes an iterator is invalidated, and some times it isn't.
The behavior of operations on an invalid iterator is undefined.
- This doesn't mean you can't use them; it just means their behavior is undefined
- Don't expect compiler help.

Example 1 - List Filtering

Given a predicate p() and a list of integers il,
remove all elements of il satisfying p().
- This operation is known as filtering.

Oh heck, that's easy - even I can do that:


typedef std::list<int>  int_list
typedef int_list::iterator ilst_iter

filter(int_list & il, predicate p) 

  ilst_iter i
  for (i = il.begin(); i != il.end(); i++)
    if (p(*i))
      il.erase(i)

Example 2 - Overwriting-Inserting Iterators

This example taken from Overwrite Iterators by Ray Virzi, C/C++ Users Journal, page 37, December 2002.
Sometimes you want to overwrite a value in a container, and sometimes you want to push back a new value.
- It depends on the container element referenced by the iterator.

An overwrite iterator manages the difference itself.

struct overwrite_iterator {

  Container & c;
  Container::iterator iter;

  operator = (val) 
    if (iter == c.end())
      c.push_back(val)
    else
      *iter++ = val
  }

Iterator-Invalidation Origins

Invalidation originates in the way containers manage their dynamic storage.
- Different container types manage their dynamic storage in different ways.
- This is an important characteristic for distinguishing among containers.
Iterator implementations.
- Iterator implementations contain pointers to dynamic storage within containers.
- Iterators may or may not themselves be pointers.

Common Invalidation Patterns

Some invalidation patterns are common to all containers.
- They always invalidate the iterator involved.
- And others too, possibly.
Erasing an element always invalidates the iterator involved.
Clearing a container invalidates all iterators into the container.

Container-Specific Invalidation Patterns

Vectors and strings.
- .insert() and .erase() invalidate all iterators to the right of the involved iterator.
- Don't forget .resize() and .reserve(), which may invalidate all interators (or may not).
Deques
- Insert and erase may invalidate all iterators.
Lists have no extra invalidation behavior.
Maps have no extra invalidation behavior.
- Sorted associative containers in general have no extra invalidation behavior.

Avoiding Iterator Invalidation

Choose the container to match the iterator use and insert and erase behavior.
Don't assign iterators to variables.
- Iterators quickly go stale.
- Rely on functions to create and return iterators.
- Pass iterators around as function parameters.
Pay attention to .end().
- It can be invalidated.
- Similarly for .begin().

Example 1 Revisited - List Filtering

The original code:

filter(int_list & il, predicate p) 

  ilst_iter i
  for (i = il.begin(); i != il.end(); i++)
    if (p(*i))
      il.erase(i)

The problem:

Erasing *i invalidates i; neither i != nor i++ have defined behavior.

ilst_iter i
for (i = il.begin(); i != il.end(); i++)
  if (p(*i))
    il.erase(i)

The fixed code:

Go to the next element, delete the previous element.

ilst_iter i = intl.begin()
while i != intl.end()
  ilst_iter this = i++
  if p(*this)
    intl.erase(this)

Example 2 Revisited - Overwrite Iterators

The orginal code:

struct overwrite_iterator {

  Container & c;
  Container::iterator iter;

  operator = (val) 
    if (iter == c.end())
      c.push_back(val)
    else
      *iter++ = val
  }

The problem:
- .push_back() invalidates the .end() iterator stored in iter.

The fixed code:

if (iter == c.end())
  c.push_back(val)
  iter = c.end()
else
  *iter++ = val

This page last modified on 17 November 2003.