CODEWITHSUNDEEP
c++stl
Siarhei Fedartsou
Siarhei Fedartsou

Reputation: 1873

Can I remove elements from std::list, when I'm iterating on it?

Can I remove elements from std::list, when I'm iterating on it? For example so:

std::list<int> lst;
//....
for (std::list<int> itr = lst.begin(); itr != lst.end(); itr++)
{
    if (*itr > 10)
         lst.remove(*itr);
}

? And why?

Upvotes: 17

Views: 19979

Answers (5)

Vlad
Vlad

Reputation: 35584

The correct code is the following:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); /*nothing*/)
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

When you delete an item from the list, you may invalidate the iterator (if it points to the item being deleted.) Therefore you need to delete using erase (which returns a valid iterator pointing to the next item).

Even better idea would be using std::remove_if:

bool greater_than_10(int x)
{
    return x > 10;
}

lst.remove_if(greater_than_10);

If your compiler supports lambdas, you can put it even shorter:

lst.remove_if([](int x){ return x > 10; });

(I didn't test this code, as my compiler is not so new; the lambda function is thankfully stolen from @John Dibling's answer.)

Actually, erasing from list invalidates only the iterators pointing to the item being deleted. Beware however that other STL containers don't have this property.

So, in short: generally speaking, you should not delete the items from the list while iterating through it, because the deletion may invalidate the iterator (and the program will possibly crash). If you are however completely sure that the items which you delete are not the values referenced by any of the iterators which you use at the moment of deletion, you may delete.

Beware that for the other STL containers (e.g. vectors) the constraint is even more strict: deleting from the container invalidates not only iterators pointing to the deleted item, but possibly other iterators, too! So deleting from that containers while iterating through them is even more problematic.

Upvotes: 37

John Dibling
John Dibling

Reputation: 101456

No, you can't.

But you can (and should) use std::remove_if along with a functor that says "greater than 10`, like this:

#include <list>
#include <algorithm>


int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), std::bind2nd(std::greater<int>(), 10)), lst.end());
}

Another, more generic way to do this is to write your own custom functor. Here is a functor is_a_match that returns true if the value being checked is greater than 10. You can redefine operator() to return true to correspond to whatever it means in your case to "match":

#include <list>
#include <algorithm>
#include <functional>

struct is_a_match : public std::unary_function<int, bool>
{
    is_a_match(int val) : val_(val) {};
    bool operator()(int victim) const { return victim > val_; }
private:
    int val_;
};

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), is_a_match(10) ));
}

If you have the benefit of a C++0x conformant compiler, you can also use lambdas, which makes it possible to get rid of the functor and write more expressive code in many cases

#include <list>
#include <algorithm>

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), [](int v) {return v > 10;}));
}

Upvotes: 3

TreDubZedd
TreDubZedd

Reputation: 2556

See http://www.cppreference.com/wiki/iterator/start for a description of iterators.

A couple of notes:

  • You should be using the pre-increment operator (++itr) instead of the post-increment operator (itr++)
  • Invalidation depends on the exact implementation of the iterator and its associated collection.

Upvotes: 0

aschepler
aschepler

Reputation: 72271

No. The example code invalidates itr, causing undefined behavior. But this would work:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); )
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

Upvotes: 9

Jack
Jack

Reputation: 133567

I think you can, but you have to reassign the iterator after the removal of the element, which can be done with erasemethod instead that remove.

Otherwise it will be unsafe and shouldn't be done.

Upvotes: 0

Related Questions