CS 70

Container-Specific Rules

Sometimes the validity of iterators after a disruptive operation depend on the specific kind of list-like container you are using.

Array-Backed Lists

For instance, remember that std::vector is an array-backed list. Behind-the-scenes, a vector uses an array and—if the list gets too big—it creates a bigger array and copies everything over (like Quinn's train).

Given that behavior, do you see any issues with the following code?

std::vector<std::string> v;                            //  1
v.push_front("Moo");                                   //  2

std::vector<std::string>::iterator iter = v.begin();   //  3
v.push_front("Baa");                                   //  4

v.erase(iter);                                         //  5
while (iter != v.end()) {                              //  6
    cout << *iter << endl;                             //  7
    ++iter;                                            //  8
}                                                      //  9

iter stops being valid on line

In this example, iter is not guaranteed to be valid after line 4. For an array-backed list, any time you add or remove something from the list, all existing iterators cease to be valid!

This video might help to explain why:

Key Takeaway

Insertion and removal operations might cause the list to move its contents to a different/new array, in which case all iterators that have already been created are referring to deallocated memory!

  • Horse speaking

    Hay wait! You said might…?

  • LHS Cow speaking

    That's true. We don't actually know whether the list will “resize” on this particular operation.

  • RHS Cow speaking

    But that's the point. We don't know!

  • LHS Cow speaking

    We can't safely rely on the iterators afterward, as there's no promise that they're valid.

  • Bjarne speaking

    Actually, because C++'s std::vector provides you with access to the capacity of the underlying array, you can know if a resize operation will occur. Or you could preallocate the capacity you want ahead of time.

  • Rabbit speaking

    But those design choices mean that the vector never shrinks automatically! If you want it to downsize, you have to deliberately use resize() or shrink_to_fit().

  • LHS Cow speaking

    Hush, you two! You may be technically correct, but we don't need to go down those rabbit holes!

Linked Lists

Now imagine we're using a std::list, which is a linked list…

std::list<std::string> l;                           //  1
l.push_front("Moo");                                //  2
std::list<std::string>::iterator iter = l.begin();  //  3
l.push_front("Baa");                                //  4
l.erase(iter);                                      //  5
while (iter != l.end()) {                           //  6
    cout << *iter << endl;                          //  7
    ++iter;                                         //  8
}                                                   //  9

iter stops being valid on line

In this example, iter is invalidated on line 5. Check out this video:

Key Idea

For a linked list, even if you insert something into the list, all the other nodes are unaffected. All the existing iterators will still point to the same item.

However, for any container, erase will invalidate the iterator that is passed in and all others at that location.

  • RHS Cow speaking

    Though there are some common examples of data structures that behave in this way, ultimately it's up to the data-structure's coder to document the operations that do and don't preserve iterator validity.

  • LHS Cow speaking

    And it's up to the user of that data structure to pay attention to that documentation and keep track of which iterators are valid!

  • RHS Cow speaking

    For standard C++ containers, the documentation can be easily found online (e.g., cplusplus.com). For others, read their docs!

(When logged in, completion status appears here.)