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.

Solution 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.

Solution 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())

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

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

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

View more solutions

Comments

[Atrotygma]

Well, it would be nice if I could use something like this for every object that implements IEnumerable (or IList, ICollection...). So wouldn't be an extension method a more beautiful way?

[Sergey Kalinichenko]

@Atrotygma It's up to you. ToList extension always makes a copy, too, but the readers may get confused for a moment on why you must convert a list to list. Of course if you simply need to remove some items from the list as you go through its items, a common trick of iterating backwards may be better suited for what you are trying to do.

[Atrotygma]

Close. Yes, the example above removes all items from the list, and I'm aware of using predicates. But your suggestion wouldn't cover every case, especially more complex ones. See question above, I've added an example. What if I have to do more than just filter/simple action? Or when I don't even have to filter, but doing something for every item?

[pensono]

Iterating in reverse removes the need to adjust the index in your second example.

[Ed Landau]

Is this still the case in 2015? Is the use of Linq so much faster ? I've read that Linq is a higher-level language and therefore took more time...

[svinja]

It is still the case because the algorithm which removes items one by one from a List is simply bad (my answer explains why), not because there is anything special about Linq.