24

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);
        }
    }
johnbakers
  • 24,158
  • 24
  • 130
  • 258

3 Answers3

57

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.

David
  • 27,652
  • 18
  • 89
  • 138
  • in this example, you are stopping iteration once it has been erased, therefore not iterating through the list to potentially review other elements. I am interesting in iterating the whole list, and removing entries as desired. From what I understand, this is safe with a `list` but not with other containers. That is the heart of my question, sorry if that wasn't clear. – johnbakers Apr 29 '13 at 00:54
  • 2
    This will not work for non-C++11 compilers. The erase member methods only return `void` in C++03. Changing `i = list.erase(i)` to `list.erase(i++)` will fix it. – Casey Apr 29 '13 at 01:12
  • 1
    I'm confused, sorry. You are incrementing the iterator only if it is `!cheesecake`. So how does it get incremented when it *is* `cheesecake`? – johnbakers Apr 29 '13 at 03:48
  • ahh, i see. `i` is automatically incremented upon the return of `erase`. I see that you are using `auto` to specify `i` as an `iterator` implicitly. still does not explain why the loop in my Q is "broken". It would seem I am doing similar, just with different style. – johnbakers Apr 29 '13 at 03:52
  • @SebbyJohanns Dave's loop is perhaps simpler, but I don't see why yours wouldn't work also. I think your question is what happens to the iterator sequence when one of the iterator elements is erased. I don't think you've gotten that answer yet. – Jerome Baldridge Apr 29 '13 at 04:48
  • @Casey, you're thinking of the associative containers, which have `void Assoc::erase(Assoc::iterator)` in C++03 – Jonathan Wakely Apr 29 '13 at 13:56
  • @JonathanWakely Hmm that was very inconsistent. Glad it was fixed. I guess the normal use case for associative containers is erasing something you just found, not during a traversal. – David Apr 29 '13 at 14:02
  • @Dave, the docs at the link you gave disagree with these: http://www.cplusplus.com/reference/map/map/erase/. Also, my compiler (GNU C++ 4.6.3) says erase returns void. *sigh* I can't wait until my project moves to C++11. – Adam Crume Aug 08 '14 at 01:43
  • @AdamCrume There are 2 tabs in those docs, click the C++11 one. Also, cppreference is better, IMO. – David Aug 08 '14 at 14:11
  • @Dave, I know that it returns non-void in C++11. The point is that in pre-C++11, it returns void. – Adam Crume Aug 08 '14 at 17:48
  • @AdamCrume True for map, not for list. I linked for list. C++11 made them consistent. – David Aug 08 '14 at 19:51
  • @Dave: Ah, I see. Why should C++ be consistent? – Adam Crume Aug 08 '14 at 21:00
  • 2
    Also consider `list.erase(std::remove_if(list.begin(), list.end(), condition), list.end())` – Taywee Jun 20 '16 at 17:07
0
for (auto i = list.begin(); i != list.end(); ++i) {
    if (condition) {
        list.erase(i);
        --i;
    }
}
Frank Hou
  • 1,688
  • 1
  • 16
  • 11
0

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?

Jayhello
  • 5,931
  • 3
  • 49
  • 56