Lecture Notes for CS 509, Advanced Programming II

17 February 2004, Iterator Invalidation

Outline

• Iterator invalidation.

  • Distinguishing features.

  • Examples

• Iterator-Invalidation Origins

  • Common invalidation patterns.

  • Container-specific invalidation patterns.

• Avoiding 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 sometimes it isn't.

• Iterator invalidation varies with containers.

  • An operation invalidating iterators in one container may be ok for a different container.

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

• Invalidation problems are hard to recognize and to find.

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, erase 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
  

Points to Remember

• Iterator invalidation is the analog to dangling pointers.

  • But it's sneakier because deletion is not obvious.

• Distinguishing Features

• Iterator-Invalidation Origins

• Common Invalidation Patterns

• STL Containers vary in their iterator invalidation patterns.

  • This is a useful way to choose among the containers.

• To avoid invalidation, generate iterators as needed.

  • Storing iterators is begging for trouble.

This page last modified on 19 February 2004.