Remove/Add items to/from a list while iterating it

Question

First, I know this isn't possible out of the box because of obvious reasons.

foreach(string item in myListOfStrings) {
    myListOfStrings.Remove(item);
}

The snipped above is one of the most horrible things I've ever seen. So, how do you achieve it then? You could iterate through the list backwards using for, but I don't like this solution either.

What I'm wondering is: Is there a method/extensions that returns an IEnumerable from the current list, something like a floating copy? LINQ has numerous extension methods that do exactly this, but you always have to do something with it, such as filtering (where, take...).

I'm looking forward to something like this:

foreach(string item in myListOfStrings.Shadow()) {
   myListOfStrings.Remove(item);
}

where as .Shadow() is:

public static IEnumerable<T> Shadow<T>(this IEnumerable<T> source) {
    return new IEnumerable<T>(source);
    // or return source.Copy()
    // or return source.TakeAll();
}

Example

foreach(ResponseFlags flag in responseFlagsList.Shadow()) {
    switch(flag) {
        case ResponseFlags.Case1:
            ...
        case ResponseFlags.Case2:
            ...
    }
    ...
    this.InvokeSomeVoidEvent(flag)
    responseFlagsList.Remove(flag);
}

---

Solution

This is how I solved it, and it works like a charm:

public static IEnumerable<T> Shadow<T>(this IEnumerable<T> source) where T: new() {
    foreach(T item in source)
        yield return item;
}

It's not that super fast (obviously), but it's safe and exactly what I intended to do.

Answer 1

Removing multiple elements from a list 1 by 1 is a C# anti-pattern due to how lists are implemented.

Of course, it can be done with a for loop (instead of foreach). Or it can be done by making a copy of the list. But here is why it should not be done. On a list of 100000 random integers, this takes 2500 ms on my machine:

       foreach (var x in listA.ToList())
            if (x % 2 == 0)
                listA.Remove(x);

and this takes 1250 ms:

        for (int i = 0; i < listA.Count; i++)
            if (listA[i] % 2 == 0)
                listA.RemoveAt(i--);

while these two take 5 and 2 ms respectively:

        listB = listB.Where(x => x % 2 != 0).ToList();

        listB.RemoveAll(x => x % 2 == 0);

This is because when you remove an element from a list, you are actually deleting from an array, and this is O(N) time, as you need to shift each element after the deleted element one position to the left. On average, this will be N/2 elements.

Remove(element) also needs to find the element before removing it. So Remove(element) will actually always take N steps - elementindex steps to find the element, N - elementindex steps to remove it - in total, N steps.

RemoveAt(index) doesn't have to find the element, but it still has to shift the underlying array, so on average, a RemoveAt is N/2 steps.

The end result is O(N^2) complexity either way, as you're removing up to N elements.

Instead, you should use Linq, which will modify the entire list in O(N) time, or roll your own, but you should not use Remove (or RemoveAt) in a loop.

Answer 2

Why not just do:

foreach(string item in myListOfStrings.ToList()) 
{
    myListOfStrings.Remove(item);
}

To create a copy of the original and use for iterating, then remove from the existing.

If you really need your extension method you could perhaps create something more readable to the user such as:

 public static IEnumerable<T> Shadow<T>(this IEnumerable<T> items)
 {
     if (items == null)
        throw new NullReferenceException("Items cannot be null");

     List<T> list = new List<T>();
     foreach (var item in items)
     {
         list.Add(item);
     }
     return list;
 }

Which is essentially the same as .ToList().

Calling:

foreach(string item in myListOfStrings.Shadow())

Answer 3

You do not LINQ extension methods for this - you can create a new list explicitly, like this:

foreach(string item in new List<string>(myListOfStrings)) {
    myListOfStrings.Remove(item);
}

Answer 4

You have to create a copy of the original list while iterating as below:

        var myListOfStrings = new List<string>();

        myListOfStrings.Add("1");
        myListOfStrings.Add("2");
        myListOfStrings.Add("3");
        myListOfStrings.Add("4");
        myListOfStrings.Add("5");

        foreach (string item in myListOfStrings.ToList())
        {
            myListOfStrings.Remove(item);
        }