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

Answer 5

Your example removes all items from the string, so it's equivalent to:

myListOfStrings.Clear();

It is also equivalent to:

myListOfStrings.RemoveAll(x => true); // Empties myListOfStrings

But what I think you're looking for is a way to remove items for which a predicate is true - which is what RemoveAll() does.

So you could write, for example:

myListOfStrings.RemoveAll(x => x == "TEST"); // Modifies myListOfStrings

Or use any other predicate.

However, that changes the ORIGINAL list; If you just want a copy of the list with certain items removed, you can just use normal Linq:

// Note != instead of == as used in Removeall(), 
// because the logic here is reversed.

var filteredList = myListOfStrings.Where(x => x != "TEST").ToList(); 

Answer 6

Picking up on the answer of svinja I do believe the most efficient way of solving this problem is by doing:

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

It improves on the answer by removing unnecessary sums and subtractions.