1. WARNING - iterator invalidation is a poorly documented topic; it's quite possible there are errors in these lecture notes. However, it's better to be warned against a poorly defined danger than to be unaware of any danger at all.

2. is this code good or bad

   1. list<T>::iterator tli = tlst.begin(); // Assume tlst.size() > 0
      tlst.erase(tli);
      cout << *tli << endl;                 // Assume T::operator <<() is defined
      

3. invalid iterators - iterators for which their operations are not defined

   1. invalidation turns good iterators bad

   2. the invalidating operation (or operator) - insert() or erase()

   3. the invalidating iterator

4. c.end() is the canonical invalid iterator - inherently invalid

5. operations on an iterator can invalidate the iterator

6. list<T>::iterator tli1 = tlst.begin();   // Assume tlst.size() > 1
   list<T>::iterator tli2 = tlst.end() - 1;
   tlst.erase(tlst.begin(), tlst.end());
   cout << *tli1 << ", " *tli2 << endl;     // Assume T::operator <<() is defined
   

7. operations on containers can invalidate iterators

   1. sometimes it's obvious, sometimes it's not,

   2. it depends on the container and the operator, and how the container is implemented

   3. not all iterators are invalidated all the time

8. vectors

   1. all iterators on or after (to the right of) the invalidating iterator become invalid

   2. and remember: values are inserted before the specified iterator

   3. this is a pain if you want to insert more than one value in the same place

      1. vector<T>::iterator i = 
           tvec.begin() + (tvec.end() - tvec.begin())/2;
         tvec.insert(i, v1); // i is now invalid
         tvec.insert(i, v2); // this has undefined behavior because i is invalid
         

   4. does copying iterators help

      1. vector<T>::iterator i1 = 
           tvec.begin() + (tvec.end() - tvec.begin())/2;
         vector<T>::iterator i2 = i1
         tvec.insert(i1, v1); // i1 and i2 are now invalid
         tvec.insert(i2, v2); // i1 and i2 are now invalid
         

   5. invalidating at an offset - i is behind the invalidation point i + 1

      1. vector<T>::iterator i = 
           tvec.begin() + (tvec.end() - tvec.begin())/2 - 1;
         tvec.insert(i + 1, v1); // i is still valid
         tvec.insert(i + 1, v2); // has defined behavior
         

      2. but note, the value sequence is *i,v2,v1

      3. make sure the offset is positive; make sure it's correct

9. dequeues

   1. the worst case - all iterators are always invalidated

   2. dequeues grow and shrink from either end - it's not clear what changes in response to an insert or erasure

10. lists

    1. lists are the best case - only the invalidating iterator is invalidated

    2. cool - does that mean I can write code like this

       1. for (list<T>::iterator i = tlst.begin(); i != tlist.end(); i++)
            if (p(*i)) tlst.erase(i);
          

    3. unfortunately, it doesn't - i is invalid after the call to erase(), so i++ is undefined

    4. can I can write code like this

       1. for (list<T>::iterator i = tlst.begin(); i + 1 != tlist.end(); i++)
            if (p(*(i + 1))) tlst.erase(i + 1);
          if (p(*tlst.begin()) tlst.erase(tlst.begin());
          

    5. that's fine

11. sets and multisets

    1. sets and multisets are like lists - only the invalidating iterator becomes invalid

    2. but wait - my code broke

       1. for (set<T>::iterator i = tset.begin(); i + 1 != tset.end(); i++)
            if (p(*(i + 1))) tset.erase(i + 1);
          if (p(*i) tset.erase(i);
          

    3. that's right, it did - you have to be more circumspect with bidirectional iterators

       1. set<int>::iterator i = iset.begin();
          while (true) {
            set<int>::iterator i2 = i;
            if (++i2 == iset.end()) break;
            if (odd(*i2)) 
              iset.erase(i2);
            else 
              i++;
            }
          if (odd(*iset.begin())) iset.erase(iset.begin());
          

       2. but wait - copying iterators doesn't help

          1. that's right, it doesn't - so it must not be the copying that's the point here

12. maps and multimaps

    1. maps and multimaps are just special sets

13. it seems like iterators are a pain - is it really that bad

    1. Not really; iterators, like pointers, do need to be used with care; here are some rules to help

    2. avoid using iterators

       1. before writing for loops, stop and search for an equivalent generic algorithm

          1. ilist.erase(remove_if(ilist.begin(), ilist.end(), p), ilist.end());
             

    3. don't declare explicit iterators - many functions return them

       1. tvec.insert(
            tvec.insert(tvec.begin() + (tvec.end() - tvec.begin())/2, v1), v2);
          

    4. give explicitly declared iterators a short lifetime - the longer they live, the more likely they are to be invalidated

This page last modified on 3 August 2000.