CODEWITHSUNDEEP
c++list
johnbakers
johnbakers

Reputation: 24771

Erasing while iterating an std::list

If I'm using an iterator in a for loop and I use erase on a current iteration of iterator, the for loop should continue fine and access the rest of the list elements?

From what I have read, this should be the case and is a primary distinguishing characteristic of list vs deque or vector. For my purposes, a queue might work but I need this behavior.

Here is the loop I am considering:

    std::list<Sequence>::iterator iterator;
    iterator=m_concurrents.begin();
    for (;iterator!=m_concurrents.end();++iterator){
        if (iterator->passes()){
            m_concurrents.erase(iterator);
        }
    }

Upvotes: 24

Views: 37283

Answers (3)

Jayhello
Jayhello

Reputation: 6602

If you just want to use for iterator, you can use it this way, for example:

list<int> lst{4, 1, 2, 3, 5};

for(auto it = lst.begin(); it != lst.end();++it){
    if ((*it % 2) == 1){
        it = lst.erase(it);  erase and go to next(erase will return the next iterator)
        --it;  // as it will be add again in for, so we go back one step
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

But erase in while iterator will be more clear:

list<int> lst{4, 1, 2, 3, 5};

auto it = lst.begin();
while (it != lst.end()){
    if((*it % 2) == 1){
        it = lst.erase(it);// erase and go to next
    } else{
        ++it;  // go to next
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

You can also use member function remove_if：

list<int> lst{4, 1, 2, 3, 5};

lst.remove_if([](int a){return a % 2 == 1;});

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

Or use std::remove_if conbine with erase funtion:

list<int> lst{4, 1, 2, 3, 5};

lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
    return a % 2 == 1;
}), lst.end());

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

You can also reference to this question: Removing item from vector, while in C++11 range 'for' loop?

Upvotes: 0

Frank Hou
Frank Hou

Reputation: 1818

for (auto i = list.begin(); i != list.end(); ++i) {
    if (condition) {
        list.erase(i);
        --i;
    }
}

Upvotes: 0

David
David

Reputation: 28178

The idiomatic way to write that loop would be:

for (auto i = list.begin(); i != list.end();) {
    if (condition)
        i = list.erase(i);
    else
        ++i;
}

You can do the same thing with a set, multiset, map, or multimap. For these containers you can erase an element without affecting the validity to any iterators to other elements. Other containers like vector or deque are not so kind. For those containers only elements before the erased iterator remain untouched. This difference is simply because lists store elements in individually allocated nodes. It's easy to take one link out. vectors are contiguous, taking one element out moves all elements after it back one position.

Your loop is broken because you erase the element at i on some given condition. i is no longer a valid iterator after that call. Your for loop then increments i, but i is not valid. Hell upon earth ensues. This is the exact situation that is why erase returns the iterator to the element after what was erased... so you can continue traversing the list.

You could also use list::remove_if:

list.remove_if([](auto& i) { return i > 10; });

In the lambda, return true if the element should be removed. In this example, it would remove all elements greater than 10.

Upvotes: 57

Related Questions