Jump to content

  • Log In with Google      Sign In   
  • Create Account

Remove any items from a list while iterating


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 Josh Klint   Crossbones+   -  Reputation: 1349

Like
0Likes
Like

Posted 03 May 2013 - 09:56 PM

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, 03 May 2013 - 09:56 PM.

Build mobile games with native code

http://www.leadwerks.com


Sponsor:

#2 frob   Moderators   -  Reputation: 21155

Like
3Likes
Like

Posted 03 May 2013 - 10:46 PM

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.
Check out my personal indie blog at bryanwagstaff.com.

#3 Álvaro   Crossbones+   -  Reputation: 13309

Like
3Likes
Like

Posted 04 May 2013 - 01:59 AM

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());
}


#4 Weton   Members   -  Reputation: 255

Like
-1Likes
Like

Posted 04 May 2013 - 04:24 AM

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)



#5 rip-off   Moderators   -  Reputation: 8211

Like
5Likes
Like

Posted 04 May 2013 - 07:11 AM

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.



#6 Paradigm Shifter   Crossbones+   -  Reputation: 5370

Like
1Likes
Like

Posted 04 May 2013 - 07:29 AM

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, 04 May 2013 - 07:30 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#7 Bacterius   Crossbones+   -  Reputation: 8836

Like
2Likes
Like

Posted 04 May 2013 - 08:16 AM

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.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#8 FLeBlanc   Crossbones+   -  Reputation: 3101

Like
1Likes
Like

Posted 04 May 2013 - 09:01 AM

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.

#9 Josh Klint   Crossbones+   -  Reputation: 1349

Like
0Likes
Like

Posted 04 May 2013 - 09:15 AM

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.

Build mobile games with native code

http://www.leadwerks.com


#10 Josh Klint   Crossbones+   -  Reputation: 1349

Like
0Likes
Like

Posted 04 May 2013 - 09:55 AM

There IS a way to do this, and it's quite elegant. biggrin.png

Build mobile games with native code

http://www.leadwerks.com


#11 Khaiy   Crossbones+   -  Reputation: 1342

Like
1Likes
Like

Posted 04 May 2013 - 09:58 AM

It's not especially elegant, but you could build a new list and copy any elements you don't want deleted to it. Then you can replace the original list with the new one. If you want an in-place solution, it's unfortunately beyond me to think of one that hasn't been mentioned yet.



#12 NightCreature83   Crossbones+   -  Reputation: 2823

Like
1Likes
Like

Posted 04 May 2013 - 11:24 AM

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.

If your list only stores pointers remove the object and replace is with a null pointer, make sure your update function skips the null pointers. Once you are done updating remove all null pointers from the list or replace them with new instances if you need to add new ones.
Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#13 Josh Klint   Crossbones+   -  Reputation: 1349

Like
-1Likes
Like

Posted 04 May 2013 - 11:28 AM

Here's what I came up with. The hardest situation is breaking from the loop without doing any kind of cleanup on the iterator. I tried doing some smart pointer stuff, but I generally stay away from stuff like that:
List list;
        Link* link[3];
        ListIterator it;
        int i;
 
        //============================================
        // Test: Remove first element
        //============================================
 
        i=0;
 
        link[0] = list.AddLast(1);
        link[1] = list.AddLast(2);
        link[2] = list.AddLast(3);
 
        it = list.Begin();
 
        for (it = list.Begin(); it != list.End(); it++)
        {
                System::Print(it.link->value);
                if (link[i])
                {
                        link[i]->Release();
                        link[i]=NULL;
                }
        }
 
        //Check
        for (i=0; i<3; i++)
        {
                if (link[i]) Debug::Assert(link[i]->refcount==1);
        }
 
        list.Clear();
 
        //============================================
        // Test: Remove second element
        //============================================
 
        i=1;
 
        link[0] = list.AddLast(1);
        link[1] = list.AddLast(2);
        link[2] = list.AddLast(3);
 
        it = list.Begin();
 
        for (it = list.Begin(); it != list.End(); it++)
        {
                System::Print(it.link->value);
                if (link[i])
                {
                        link[i]->Release();
                        link[i]=NULL;
                }
        }
 
        it = ListIterator();
 
        //Check
        for (i=0; i<3; i++)
        {
                if (link[i]) Debug::Assert(link[i]->refcount==1);
        }
 
        list.Clear();
       
        //============================================
        // Test: Remove third element
        //============================================
 
        i=2;
 
        link[0] = list.AddLast(1);
        link[1] = list.AddLast(2);
        link[2] = list.AddLast(3);
 
        it = list.Begin();
 
        for (it = list.Begin(); it != list.End(); it++)
        {
                System::Print(it.link->value);
                if (link[i])
                {
                        link[i]->Release();
                        link[i]=NULL;
                }
        }
       
        //Check
        for (i=0; i<3; i++)
        {
                if (link[i]) Debug::Assert(link[i]->refcount==1);
        }
 
        list.Clear();
 
        //============================================
        // Test: Break during loop
        //============================================
 
        i=2;
 
        link[0] = list.AddLast(1);
        link[1] = list.AddLast(2);
        link[2] = list.AddLast(3);
 
        it = list.Begin();
 
        for (it = list.Begin(); it != list.End(); it++)
        {
                break;
        }
        it = ListIterator();
       
        //Check
        for (i=0; i<3; i++)
        {
                if (link[i]) Debug::Assert(link[i]->refcount==1);
        }
 
        list.Clear();
However, there are a lot of problems you can cause unless that code above isn't followed strictly. rip-off's suggestion was probably the best. Still, this strikes me as a really fundamental problem that ought to have a good solution.

Edited by Josh Klint, 04 May 2013 - 01:40 PM.

Build mobile games with native code

http://www.leadwerks.com


#14 iMalc   Crossbones+   -  Reputation: 2306

Like
0Likes
Like

Posted 04 May 2013 - 11:50 PM

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.

That still wont cut it in this scenario, as the OP says"

It could also result in removing other objects from the list

That would mean that it's possible that the iterator obtained before doStuffWith(it); pointed to the item which got removed, which means that iterator is now invalid.
In fact if the current item was not removed but the next item was, then you must only advance the iterator at the end of the iteration, as per normal iteration.

The problem is that in the case being described, there is no way to know whether the current item it being deleted or the next item is being deleted. So you don't know whether to get the advanced iterator at the beginning of or the end of each iteration.

Hence it is not solvable without at least some information about what is deleted coming back to the code in this loop. If you don't know the current item or the next item is always still there at the end of each iteration, then you can't do it.

Edited by iMalc, 04 May 2013 - 11:52 PM.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#15 NightCreature83   Crossbones+   -  Reputation: 2823

Like
0Likes
Like

Posted 07 May 2013 - 02:13 AM

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.

That still wont cut it in this scenario, as the OP says"

It could also result in removing other objects from the list

That would mean that it's possible that the iterator obtained before doStuffWith(it); pointed to the item which got removed, which means that iterator is now invalid.
In fact if the current item was not removed but the next item was, then you must only advance the iterator at the end of the iteration, as per normal iteration.

The problem is that in the case being described, there is no way to know whether the current item it being deleted or the next item is being deleted. So you don't know whether to get the advanced iterator at the beginning of or the end of each iteration.

Hence it is not solvable without at least some information about what is deleted coming back to the code in this loop. If you don't know the current item or the next item is always still there at the end of each iteration, then you can't do it.

 

 

Why not move the delete back into the class that has the original list via a callback, this will allow you to know exactly which item to delete and what the iterator needs to do. Better is to mark that object as dead though and leave it in the list and then after update remove the values you don't need, as indicated before.

 

Generally you don't remove or insert objects into your containers (lists, queue and others that invalidate your iterator) whilst you are updating them, you do this as a post step to the update. Which means having a dead list and new list around, or marking dead ones in the list and having a new list, in the object that contains the actual container. Having objects being out by one frame is hardly noticeable on 30fps and even less so on higher frame rates.
 


Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS