CODEWITHSUNDEEP
c#.netcollections
Daniel Mošmondor
Daniel Mošmondor

Reputation: 19956

Efficiently deleting item from within 'foreach'

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.

Upvotes: 14

Views: 28070

Answers (5)

phoog
phoog

Reputation: 43046

A forward variation on the backward for loop:

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

Upvotes: 2

Mitch
Mitch

Reputation: 399

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.

Upvotes: 1

Eric Lippert
Eric Lippert

Reputation: 659994

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.

Upvotes: 36

Martin Liversage
Martin Liversage

Reputation: 106816

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.

Upvotes: 1

Daniel Mošmondor
Daniel Mošmondor

Reputation: 19956

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

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

Better way?

Upvotes: 14

Related Questions