Efficiently deleting item from within 'foreach'

Question

For now, the best I could think of is:

bool oneMoreTime = true;
while (oneMoreTime)
{
    ItemType toDelete=null;
    oneMoreTime=false;
    foreach (ItemType item in collection)
    {
        if (ShouldBeDeleted(item))
        {
            toDelete=item;
            break;
        }
    }
    if (toDelete!=null)
    {
        collection.Remove(toDelete);
        oneMoreTime=true;
    }
}

I know that I have at least one extra variable here, but I included it to improve the readability of the algorithm.

possible duplicate of [How to conditionally remove items from a .NET collection](http://stackoverflow.com/questions/653596/how-to-conditionally-remove-items-from-a-net-collection) — Igby Largeman, Jan 09 '12 at 17:29

Eric Lippert · Accepted Answer · 2012-01-09T16:42:17.067

36

The "RemoveAll" method is best.

Another common technique is:

var itemsToBeDeleted = collection.Where(i=>ShouldBeDeleted(i)).ToList();
foreach(var itemToBeDeleted in itemsToBeDeleted)
    collection.Remove(itemToBeDeleted);

Another common technique is to use a "for" loop, but make sure you go backwards:

for (int i = collection.Count - 1; i >= 0; --i)
    if (ShouldBeDeleted(collection[i]))
        collection.RemoveAt(i);

Another common technique is to add the items that are not being removed to a new collection:

var newCollection = new List<whatever>();
foreach(var item in collection.Where(i=>!ShouldBeDeleted(i))
    newCollection.Add(item);

And now you have two collections. A technique I particularly like if you want to end up with two collections is to use immutable data structures. With an immutable data structure, "removing" an item does not change the data structure; it gives you back a new data structure (that re-uses bits from the old one, if possible) that does not have the item you removed. With immutable data structures you are not modifying the thing you're iterating over, so there's no problem:

var newCollection = oldCollection;
foreach(var item in oldCollection.Where(i=>ShouldBeDeleted(i))
    newCollection = newCollection.Remove(item);

or

var newCollection = ImmutableCollection<whatever>.Empty;
foreach(var item in oldCollection.Where(i=>!ShouldBeDeleted(i))
    newCollection = newCollection.Add(item);

And when you're done, you have two collections. The new one has the items removed, the old one is the same as it ever was.

edited Jan 09 '12 at 16:42

answered Jan 09 '12 at 16:28

Eric Lippert

647,829
179
1,238
2,067

Have you ever used the `Reverse` extension using a foreach - I just came across it here http://stackoverflow.com/a/10541025/706363 ? Why would it not be a more widely used option? Is there some kind of serious performance implications or something going on there? – Piotr Kula Apr 29 '14 at 10:12
@ppumkin: Try writing an implementation of `Reverse` for an `IEnumerable` that does not implement `IList`, `ICollection`, and so on. What is the memory and time performance of your implementation? – Eric Lippert Apr 29 '14 at 12:55
My implementation is not time or resource critical. I am using the `IEnumerable.Reverse` extension in Linq on a List, and it seems to work fine within a `foreach` - Thats why I ask, why is this not used an example more frequently, as opposed to all these for (i to 0) in reverse instead, like in your answer. Is using Reverse Extension a valid option? Can you add it to your answer or is there something wrong with using the Reverse Extension from Linq in combination with foreach? Just thought, that your opinion will make carry most weight because of your experience. – Piotr Kula Apr 29 '14 at 13:10
1

@ppumkin: Since reversing an IEnumerable requires creating a copy of the entire IEnumerable (hence why you can modify the original collection in the foreach loop), there is little point; you may as well just make a copy of the collection without reversing it, possibly by calling `ToList`. Apologies to Eric for sabotaging his lesson. – Brian Apr 29 '14 at 13:26
The c++ std algoritm, if I remember correctly, swapped items to remove to the end of the list and then truncated it. O(n) in time , no extra memory but not stable. – adrianm Apr 29 '14 at 14:28
isn't using Remove or RemoveAt within a foreach loop extremely slow (because the entire structure is shifted to the left every single time something is removed)? – BenKoshy Oct 03 '17 at 22:26
2

@BKSpurgeon: It sure is! All the elements *higher* than the removed element need to be shifted one spot down. If you need to perform this operation efficiently then *don't use a list*. Use an unordered type, like a hash set, or an ordered type that supports this operation efficiently, like a doubly-linked list, a catenable deque, and so on. – Eric Lippert Oct 03 '17 at 22:34

score 14 · Answer 2 · answered Jan 09 '12 at 16:19

14

Just as I finished typing I remembered that there is lambda-way to do it.

collection.RemoveAll(i=>ShouldBeDeleted(i));

Better way?

answered Jan 09 '12 at 16:19

Daniel Mošmondor

19,718
12
58
99

2

Just an FYI: this can be converted to a method group. collection.RemoveAll(ShouldBeDeleted). – ahawker Jan 09 '12 at 17:47

score 2 · Answer 3 · answered Jan 09 '12 at 17:15

2

A forward variation on the backward for loop:

for (int i = 0; i < collection.Count; )
    if (ShouldBeDeleted(collection[i]))
        collection.RemoveAt(i)
    else
        i++;

answered Jan 09 '12 at 17:15

phoog

42,068
6
79
117

Mitch · Answer 4 · 2012-01-09T16:43:38.437

1

The lambda way is good. You could also use a regular for loop, you can iterate lists that a for loop uses within the loop itself, unlike a foreach loop.

for (int i = collection.Count-1; i >= 0; i--)
{
    if(ShouldBeDeleted(collection[i])
        collection.RemoveAt(i);
}

I am assuming that collection is an arraylist here, the code might be a bit different if you are using a different data structure.

edited Jan 09 '12 at 16:43

answered Jan 09 '12 at 16:29

Mitch

399
1
5

score 1 · Answer 5 · answered Jan 09 '12 at 16:29

You cannot delete from a collection inside a foreach loop (unless it is a very special collection having a special enumerator). The BCL collections will throw exceptions if the collection is modified while it is being enumerated.

You could use a for loop to delete individual elements and adjust the index accordingly. However, doing that can be error prone. Depending on the implementation of the underlying collection it may also be expensive to delete individual elements. For instance deleting the first element of a List<T> will copy all the remaning elements in the list.

The best solution is often to create a new collection based on the old:

var newCollection = collection.Where(item => !ShouldBeDeleted(item)).ToList();

Use ToList() or ToArray() to create the new collection or initialize your specific collection type from the IEnumerable returned by the Where() clause.

Efficiently deleting item from within 'foreach'

5 Answers5

Linked

Related