Removal of elements during iteration through a list - safety

Question

I was wondering if something like this is safe...

// Iterating through a <list>
while ( iter != seq.end()) {
  if ( test ) {
    iter = seq.erase( iter );
  } else {
    ++iter;
 }

I know that iterating through a vector in this way would invalidate the iterator, but would the same thing occur in a list? I assume not since a list is sequential through pointers rather than being "next" to each other in memory, but any reassurance would be helpful.

Answer 1

Yes, this is the standard way to do that. See Effective STL, Item 9 (p. 46).

Answer 2

This is just fine because the erase method returns a new valid iterator.

Answer 3

Yes, this is totally safe. The erase() function returns an iterator to the element succeeding the one which was erased. Had you not reassigned the result of erase() to iter, you'd have trouble.

Answer 4

Yes -- std::list::erase(): "Invalidates only the iterators and references to the erased elements."

That said, you probably shouldn't do this at all -- you seem to be trying to imitate std::remove_if().

Answer 5

The standard defines erase behaviour for every STL container. For std::list only iterators to the erased elements are invalidated. The return value of erase needn't be a dereferencable one, though (it could be list.end()).

Therefore, to erase all elements in a list the following is absolutely valid:

.. it = l.begin();
while(it != l.end()) {
   it = l.erase(it);
}

BUT beware of something like this (dangerous pitfall):

for (.. it  = l.begin; it != l.end(); ++it) {
      it = l.erase(it);
   }

If it is l.end(), it is incremented twice (second time by the loop head). Baamm.

Answer 6

As others have explained, your code does not invalidate the iterator used in the function. However, it does invalidate other iterators if the collection is a vector, but not if the collection is a list.

Answer 7

As others have mentioned, yes, it will work. But I'd recommend using list::remove_if instead, as it's more expressive.