CS 70

Example Two: Danger When Erasing from a List

Many containers in the C++ standard library have a function named erase.

erase generally takes an iterator and removes the item that iterator “points to” in the container.

erase doesn't make any changes to the iterator: it just removes an item from the container at the position given by the iterator.

What do you think about this code?

std::list<string> l;                                    //  1
l.push_front("Moo");                                    //  2
l.push_front("Baa");                                    //  3

std::list<string>::iterator iter1 = l.begin();          //  4
std::list<string>::iterator iter2 = l.begin();          //  5

l.erase(iter1);   // Remove front item from list        //  6

cout << *iter1 << " " << *iter2 << endl;                //  7

iter1 ceases to be valid on line

iter2 ceases to be valid on line

This example is tricky, but important: erase doesn't just cause the iterator passed in to no longer be valid—any iterator that referred to the removed data is also no longer valid.

So in this example, both iterators cease to be valid after line 6.

The following video might help to explain why both iterators are invalid.

Content Note: The video uses the term “invalidation”, which we're trying to avoid saying these days because it can be interpreted as “something actively happens to the iterator” to make it invalid.

Any time we say “invalidated” or “invalidation”, just substitute “can no longer be trusted” in your head.

Key Takeaways

  • We can pass an iterator into the erase function to remove an item from the list.
  • When erase returns, we know that the passed iterator no longer refers to accessible data!
  • Thus any other iterators pointing to that location can also no longer give access to that item, so all of those iterators are now invalid, too.

Bonus: Not Losing Your Place

  • Horse speaking

    Woah! So, if I erase something in the list, I lose my place?

  • Bjarne speaking

    Actually, the C++ standard library has a clever workaround for this issue.

In the C++ standard library, erase typically returns an iterator; specifically, an iterator to the item that would have been next before erase was called. So if you want to erase an item but still have a valid iterator, you can do something like

iter = l.erase(iter); // Erase item at iter's location, set iter to an iterator at next location.

Though the original value of iter stops being valid, it is immediately reassigned to be a valid iterator.

  • Goat speaking

    Meh. That doesn't do anything for any of the other iterator objects referring to the same location—they're still no longer valid, and there's nothing you can do about it!

  • LHS Cow speaking

    Yes, that's right. In general, it's good to think about not just the iterators we're working with directly, but any others we're keeping around.

  • Bjarne speaking

    For what it is worth, if you plan on keeping iterators around while you do things to the data structure, std::list is probably a better choice than std::vector.

  • LHS Cow speaking

    And those container-specific differences are our next topic!

(When logged in, completion status appears here.)