296

I've got code that looks like this:

for (std::list<item*>::iterator i = items.begin(); i != items.end(); i++) { bool isActive = (*i)->update(); //if (!isActive) // items.remove(*i); //else other_code_involving(*i); } items.remove_if(CheckItemNotActive);

I'd like remove inactive items immediately after update them, in order to avoid walking the list again. But if I add the commented-out lines, I get an error when I get to i++: "List iterator not incrementable". I tried some alternates which didn't increment in the for statement, but I couldn't get anything to work.

What's the best way to remove items as you are walking a std::list?

Improve this question
1
  • I haven't seen any solution based on iterating backwards. I posted one such. Commented Mar 13, 2019 at 4:53

15 Answers 15

Reset to default
358

You have to:

  1. Increment the iterator (with i++).
  2. Remove the previous element (e.g., by using the returned value from i++).

You can change the code to a while loop like so:

std::list<item*>::iterator i = items.begin(); while (i != items.end()) { bool isActive = (*i)->update(); if (!isActive) { items.erase(i++); // alternatively, i = items.erase(i); } else { other_code_involving(*i); ++i; } }
Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

Actually, that's not guaranteed to work. With "erase(i++);", we only know that the pre-incremented value is passed to erase(), and the i is incremented before the semi-colon, not necessarily before the call to erase(). "iterator prev = i++; erase(prev);" is sure to work, as is use the return value
No James, i is incremented before calling erase, and the previous value is passed to the function. A function's arguments have to be fully evaluated before the function is called.
@ James Curran: That's not correct. ALL arguments are fully evaluated before a function is called.
Martin York is correct. All arguments to a function call are fully evaluated before a function is called, no exceptions. That is simply how function work. And it has nothing to do with your foo.b(i++).c(i++) example (which is undefined in any case)
The alternate usage i = items.erase(i) is safer, because it's equivalent for a list, but will still work if someone changes the container to a vector. With a vector, erase() moves everything to the left to fill the hole. If you try to remove the last item with code that increments the iterator after erasing, the end moves to the left, and the iterator moves to the right-- past the end. And then you crash.
|
165

You want to do:

i= items.erase(i);

That will correctly update the iterator to point to the location after the iterator you removed.

Improve this answer

6 Comments

Be warned that you can't just drop that code into your for-loop. Otherwise you'll skip an element every time you remove one.
can he not do i--; each time following his piece of code to avoid skipping?
@enthusiasticgeek, what happens if i==items.begin()?
@enthusiasticgeek, at that point you should just do i= items.erase(i);. It's the canonical form and takes care of all those details already.
Michael points out a huge 'gotcha', I had to deal with the same thing just now. Easiest method of avoiding it that I found was just decomposing the for() loop into a while() and being careful with the incrementing
|
30

You need to do the combination of Kristo's answer and MSN's:

// Note: Using the pre-increment operator is preferred for iterators because // there can be a performance gain. // // Note: As long as you are iterating from beginning to end, without inserting // along the way you can safely save end once; otherwise get it at the // top of each loop. std::list< item * >::iterator iter = items.begin(); std::list< item * >::iterator end = items.end(); while (iter != end) { item * pItem = *iter; if (pItem->update() == true) { other_code_involving(pItem); ++iter; } else { // BTW, who is deleting pItem, a.k.a. (*iter)? iter = items.erase(iter); } }

Of course, the most efficient and SuperCool® STL savy thing would be something like this:

// This implementation of update executes other_code_involving(Item *) if // this instance needs updating. // // This method returns true if this still needs future updates. // bool Item::update(void) { if (m_needsUpdates == true) { m_needsUpdates = other_code_involving(this); } return (m_needsUpdates); } // This call does everything the previous loop did!!! (Including the fact // that it isn't deleting the items that are erased!) items.remove_if(std::not1(std::mem_fun(&Item::update)));
Improve this answer

4 Comments

I did consider your SuperCool method, my hesitation was that the call to remove_if does not make it clear that the goal is to process the items, rather than remove them from the list of active ones. (The items aren't being deleted because they are only becoming inactive, not unneeded)
I suppose you are right. On one hand I'm inclined to suggest changing the name of 'update' to remove the obscurity, but the truth is, this code is fancy with the functors, but it is also anything but non-obscure.
Fair comment, either fix the while loop to use end or delete the unused definition.
Side-note: std::not1 and std::mem_fun have been deprecated.
14

I have sumup it, here is the three method with example:

1. using while loop

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

2. using remove_if member funtion in list:

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

3. using std::remove_if funtion combining with erase member function:

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

4. using for loop , should note update the iterator:

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
Improve this answer

1 Comment

In C++20 you can use just std::erase_if(lst, pred). It basically same as options 2 & 3, but shorter and works for any type of container.
10

Use std::remove_if algorithm.

Edit:
Work with collections should be like:

  1. prepare collection.
  2. process collection.

Life will be easier if you won't mix this steps.

  1. std::remove_if. or list::remove_if ( if you know that you work with list and not with the TCollection )
  2. std::for_each
Improve this answer

4 Comments

std::list has a remove_if member function which is more efficient than the remove_if algorithm (and doesn't require the "remove-erase" idiom).
@brianneal That depends if you have access to C++20 features, otherwise C++17 only offers std::remove_if en.cppreference.com/w/cpp/algorithm/remove
@Antonio I'm talking about std::list's remove_if member function. I've been away from C++ a long time but when I wrote my comment (more than 11 years ago!) that was a thing and I'm pretty sure it still is. cplusplus.com/reference/list/list/remove_if
@BrianNeal Yep, I don't know I misinterpreted your comment which in fact was very clear.
5

The alternative for loop version to Kristo's answer.

You lose some efficiency, you go backwards and then forward again when deleting but in exchange for the extra iterator increment you can have the iterator declared in the loop scope and the code looking a bit cleaner. What to choose depends on priorities of the moment.

The answer was totally out of time, I know...

typedef std::list<item*>::iterator item_iterator; for(item_iterator i = items.begin(); i != items.end(); ++i) { bool isActive = (*i)->update(); if (!isActive) { items.erase(i--); } else { other_code_involving(*i); } }
Improve this answer

5 Comments

That's what I've used, too. But I'm not sure if it's guaranteed to work if the element to be removed is the first element in the container. For me, it works, I think, but I'm not sure if it's portable across platforms.
I didn't do "-1", however, list iterator can not decrement? At least I've got assertion from Visual Studio 2008.
As long as the linked list is implemented as a circular double linked list having a head/stub node (used as end() rbegin() and when empty used as begin() and rend() too) this will work. I can't remember in which platform I was using this, but it was working for me too, as the implementation named above is the most common implementation for a std::list. But anyways, it's almost sure that this was exploiting some undefined (by the C++ standard) behavior, so better don't use it.
re: iterator cannot be decremented The erase method needs a random access iterator. Some collection implementations provide a forward only iterator which causes the assertion.
@Jesse Chisholm the question was about an std::list, not an arbitrary container. std::list provides erase and bidirectional iterators.
5

Here's an example using a for loop that iterates the list and increments or revalidates the iterator in the event of an item being removed during traversal of the list.

for(auto i = items.begin(); i != items.end();) { if(bool isActive = (*i)->update()) { other_code_involving(*i); ++i; } else { i = items.erase(i); } } items.remove_if(CheckItemNotActive);
Improve this answer

Comments

5

With C++20, you can use std::erase_if:

std::erase_if(items, [](auto& i){ if (!i.update()) { return true; } other_code_involving(i); return false; };
Improve this answer

Comments

3

Removal invalidates only the iterators that point to the elements that are removed.

So in this case after removing *i , i is invalidated and you cannot do increment on it.

What you can do is first save the iterator of element that is to be removed , then increment the iterator and then remove the saved one.

Improve this answer

1 Comment

Using post-increment is far more elegant.
3

Iterating backwards avoids the effect of erasing an element on the remaining elements to be traversed:

typedef list<item*> list_t; for ( list_t::iterator it = items.end() ; it != items.begin() ; ) { --it; bool remove = <determine whether to remove> if ( remove ) { items.erase( it ); } }

PS: see this, e.g., regarding backward iteration.

PS2: I did not thoroughly tested if it handles well erasing elements at the ends.

Improve this answer

1 Comment

re: avoids the effect of erasing an element on the remaining elements for a list, probably yes. For a vector maybe not. That isn't something guaranteed on arbitrary collections. For example, a map may decide to rebalance itself.
2

If you think of the std::list like a queue, then you can dequeue and enqueue all the items that you want to keep, but only dequeue (and not enqueue) the item you want to remove. Here's an example where I want to remove 5 from a list containing the numbers 1-10...

std::list<int> myList; int size = myList.size(); // The size needs to be saved to iterate through the whole thing for (int i = 0; i < size; ++i) { int val = myList.back() myList.pop_back() // dequeue if (val != 5) { myList.push_front(val) // enqueue if not 5 } }

myList will now only have numbers 1-4 and 6-10.

Improve this answer

1 Comment

Interesting approach but I am afraid that it may be slow though.
1

You can write

std::list<item*>::iterator i = items.begin(); while (i != items.end()) { bool isActive = (*i)->update(); if (!isActive) { i = items.erase(i); } else { other_code_involving(*i); i++; } }

You can write equivalent code with std::list::remove_if, which is less verbose and more explicit 

items.remove_if([] (item*i) { bool isActive = (*i)->update(); if (!isActive) return true; other_code_involving(*i); return false; });

The std::vector::erase std::remove_if idiom should be used when items is a vector instead of a list to keep compexity at O(n) - or in case you write generic code and items might be a container with no effective way to erase single items (like a vector)

items.erase(std::remove_if(begin(items), end(items), [] (item*i) { bool isActive = (*i)->update(); if (!isActive) return true; other_code_involving(*i); return false; }));
Improve this answer

Comments

1

do while loop, it's flexable and fast and easy to read and write.

auto textRegion = m_pdfTextRegions.begin(); while(textRegion != m_pdfTextRegions.end()) { if ((*textRegion)->glyphs.empty()) { m_pdfTextRegions.erase(textRegion); textRegion = m_pdfTextRegions.begin(); } else textRegion++; }
Improve this answer

1 Comment

This is inefficient - it restarts the list from the beginning every time it erases one.
1

I'd like to share my method. This method also allows the insertion of the element to the back of the list during iteration

#include <iostream> #include <list> int main(int argc, char **argv) { std::list<int> d; for (int i = 0; i < 12; ++i) { d.push_back(i); } auto it = d.begin(); int nelem = d.size(); // number of current elements for (int ielem = 0; ielem < nelem; ++ielem) { auto &i = *it; if (i % 2 == 0) { it = d.erase(it); } else { if (i % 3 == 0) { d.push_back(3*i); } ++it; } } for (auto i : d) { std::cout << i << ", "; } std::cout << std::endl; // result should be: 1, 3, 5, 7, 9, 11, 9, 27, return 0; }
Improve this answer

Comments

-4

I think you have a bug there, I code this way:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin(); itAudioChannel != audioChannels.end(); ) { CAudioChannel *audioChannel = *itAudioChannel; std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel; itAudioChannel++; if (audioChannel->destroyMe) { audioChannels.erase(itCurrentAudioChannel); delete audioChannel; continue; } audioChannel->Mix(outBuffer, numSamples); }
Improve this answer

1 Comment

I'm guessing this was downvoted for style preferences, as it appears to be functional. Yes, sure, (1) it uses an extra iterator, (2) the iterator increment is in an odd place for a loop without a good reason for putting it there, (3) it does the channel work after the decision to delete instead of before like in the OP. But it is not a wrong answer.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.