List Iterator Remove()

Question

I have a list iterator that goes through a list and removes all the even numbers. I can use the list iterator to print out the numbers fine but I cannot use the list's remove() and pass in the dereferenced iterator.

I noticed that when the remove() statement is in effect, *itr gets corrupted? Can somebody explain this?

#include <iostream>
#include <list>

#define MAX 100

using namespace std;

int main()
{
    list<int> listA;
    list<int>::iterator itr;

    //create list of 0 to 100
    for(int i=0; i<=MAX; i++)
        listA.push_back(i);

    //remove even numbers
    for(itr = listA.begin(); itr != listA.end(); ++itr)
    {
        if ( *itr % 2 == 0 )
        {
            cout << *itr << endl;
            listA.remove(*itr);    //comment this line out and it will print properly
        }
    }
}

Solution 1

There are a few issues with your code above. Firstly, the remove will invalidate any iterators that are pointing at the removed elements. You then go on to continue using the iterator. It is difficult to tell which element(s) remove would erase in the general case (although not in yours) since it can remove more than one.

Secondly, you are probably using the wrong method. Remove will iterate through all of the items in the list looking for any matching elements - this will be inefficient in your case because there is only one. It looks like you should use the erase method, you probably only want to erase the item at the position of the iterator. The good thing about erase is it returns an iterator which is at the next valid position. The idiomatic way to use it is something like this:

//remove even numbers
for(itr = listA.begin(); itr != listA.end();)
{
    if ( *itr % 2 == 0 )
    {
        cout << *itr << endl;
        itr=listA.erase(itr);
    }
    else
      ++itr;
}

Finally, you could also use remove_if to do the same as you are doing:

bool even(int i) { return i % 2 == 0; }

listA.remove_if(even);

Solution 2

You can't use an iterator after you delete the element it referred to.

However, list iterators which refer to non-deleted items after a remove() should remain valid.

Comments

[David]

This will work for std::list iterators because those iterators are only invalidated when the element they are pointing to is deleted. But this will not work for std::vector iterators because those iterators are invalidated when the element they are pointing to or any element before the one they are pointing to is deleted.