Jump to content
  • Advertisement
Sign in to follow this  
JoshKlint_34394

Remove any items from a list while iterating

This topic is 1869 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Has anyone found a way to remove any item from a list as it is iterating?

Normally a loop to iterate through a linked list looks like this:

for ( it = list.begin(); it != list.end(); it++ )
{
}

 

 

If you want to be able to remove an item from the list while it is iterating, you can always do this:

it = list.begin();
while (it != list.end() )
{
	if (condition)
	{
		it = list.erase(it);
	}
	else
	{
		it++;
	}
}

 

 

But what if the code in your loop called other code that could result in the removal of the object from the list, with no way to tell it occurred? It could also result in removing other objects from the list, with no way of knowing it happened. In that case, our previous trick would not be enough to prevent any possible problems, because the code might be removing the next item in the list after we have forwarded the iterator.

Has anyone come up with a solution to this?

Edited by Josh Klint

Share this post


Link to post
Share on other sites
Advertisement

Has anyone come up with a solution to this?


Yes.

Don't do it.


You can allow multiple readers of containers, but when a container must be modified all access must be locked to a single place.

This simple rule is true for all objects, and especially true in multi-processing applications where objects may be shared by a thread.

Share this post


Link to post
Share on other sites
You may want to read this: http://en.wikipedia.org/wiki/Erase-remove_idiom

In C++11 you can use lambda expressions to describe the condition:
void remove_odd(std::list<int> &list) {
  list.erase(std::remove_if(list.begin(), list.end(),
                            [](int i){
                              // Place any code here which returns a                           
                              // bool indicating whether the item                              
                              // should be removed                                             
                              return i%2 != 0;
                            }
                            ),
             list.end());
}

Share this post


Link to post
Share on other sites

I'm really not sure if it works, but have you tried going from the back of the list to the front?

(This worked for me once with ArrayLists in Java)

Share this post


Link to post
Share on other sites

You can erase items from a list as your iterating it, you just need to stash the next iterator before you do stuff to the current one.

 

auto it = myList.begin();

while(it != myList.end())
{
    auto nextIt = it;
    ++nextIt;

    doStuffWith(it);

    it = nextIt;
}

I'm using auto to save typing but if you not got C++11 support it's easy to change.

 

EDIT: This wont work with vector or any other container that can cause stuff to be copied or moved around in the container.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

I'm really not sure if it works, but have you tried going from the back of the list to the front?

(This worked for me once with ArrayLists in Java)

 

This works fine for array-based collections but once you get to more complex datastructures it can get difficult to delete anything without disrupting the iterator.

Share this post


Link to post
Share on other sites

It could also result in removing other objects from the list, with no way of knowing it happened.

This line here is the killer. You can safely handle the case of the object under consideration being removed (as previous posters have demonstrated) but if other arbitrary objects in the list can be removed by the same deletion then you're stuck. You'll need to build a more sane object removal traversal. Mark an object for removal, traverse the list to remove it. If that object needs to remove other objects then have the object in turn mark them so that you can remove them in subsequent passes rather than in the same pass.

Share this post


Link to post
Share on other sites

One solution is for the objects to mark themselves as "dead", perhaps using a flag or adding themselves (e.g. index or pointer) to a separate "dead list". The master loop can clear dead objects at a convenient time.

Yeah, this is the only solution I've found. Basically, I just put all objects that should be deleted into a list and then call something like Collect() after the list is done iterating.

I can't help thinking there's got to be a simple solution that handles all possible cases.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!