Best way to iterate over a list and remove items from it?

Question

I need to iterate over a List<myObject> and remove items that answer a certain condition.

I saw this answer (https://stackoverflow.com/a/1582317/5077434):

Iterate your list in reverse with a for loop:

for (int i = safePendingList.Count - 1; i >= 0; i--)
{
    // some code
    // safePendingList.RemoveAt(i);
}

Example:

var list = new List<int>(Enumerable.Range(1, 10));
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] > 5)
      list.RemoveAt(i);
}
list.ForEach(i => Console.WriteLine(i));

But I understood that for is less efficient than foreach,

So I thought of using the later as follows:

foreach (var item in myList.ToList())
{
    // if certain condition applies:
    myList.Remove(item)
}

Is one method better than the other?

EDIT:

I don't want to use RemoveAll(...), as there is a large amount of code inside the loop, prior to the condition.

Answer 1

Willy-nilly you have to loop over the list, and the for loop is the most efficient one:

  for (int i = safePendingList.Count - 1; i >= 0; --i) 
    if (condition)
      safePendingList.RemoveAt(i);

If you want to remove in range (not in the entire list), just modify for loop:

  // No Enumarable.Range(1, 10) - put them into "for"
  for (int i = Math.Min(11, safePendingList.Count - 1); i >= 1; --i)
    if (condition)
      safePendingList.RemoveAt(i); 

Or if you have to remove items in forward looping:

  for (int i = 0; i < safePendingList.Count;) // notice ++i abscence
    if (condition)
      safePendingList.RemoveAt(i);
    else
      i += 1; // ++i should be here

On the contrary safePendingList.ToList() creates a copy of initial safePendingList and this means memory and CPU overhead:

  // safePendingList.ToList() - CPU and Memory overhead (copying)
  foreach (var item in safePendingList.ToList()) {
    if (condition)
      myList.Remove(item); // Overhead: searching
  }

However, the most reasonable plan in many cases is just to let .Net work for you:

  safePendingList.RemoveAll(item => condition);

Answer 2

to remove items with a certain condition you can use

list.RemoveAll(item => item > 5);

instead of

var list = new List<int>(Enumerable.Range(1, 10));
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] > 5)
        list.RemoveAt(i);
}

Answer 3

The problem is that foreach cannot work with collection while it is being modified this will lead to InvalidOperationException.

Using .ToList() inside foreach allows us to avoid that but this copies the entire collection it result in looping through collection twice (first time when it copies all elements and second time to filter it).

The for loop is better option because we can go through collection once. Apart of that you can filter collection using LINQ Where() method, something among the lines of :

var myFilteredCollection = myList.Where(i => i <= 5).ToList();

If your conditions are complex you can move this logic to separate method :

private bool IsItemOk(myObject item)
{
   ... your complicated logic.
   return true;
}

And use it in your LINQ query :

var myFilteredCollection = myList.Where(i => IsItemOk(i)).ToList();

Other option is to do it vice-versa. Create new collection and add elements based on condition. Than you can use foreach loop :

var newList = new List<MyObject>(myList.Count);

foreach (var item in myList)
{
    // if certain condition does not apply:
    newList.Add(item);
}

P.S.

But as already mentioned .RemoveAll() is better because this way you do not have to 're-invent the wheel'

Answer 4

Neither method shows significant differences. for and RemoveAll looks a bit faster (more likely because using Remove you are duplicating your list and it needs to recreate it... using value types, this also means doubling the needed memory). I made some profiling:

public static void MethodA()
{
    var list = new List<int>(Enumerable.Range(1, 10));
    for (int i = list.Count - 1; i >= 0; i--)
    {
        if (list[i] > 5)
            list.RemoveAt(i);
    }
}

public static void MethodB()
{
    var list = new List<int>(Enumerable.Range(1, 10));
    foreach (var item in list.ToList())
    {
        if (item > 5)
            list.Remove(item);
    }
}

public static void MethodC()
{
    var list = new List<int>(Enumerable.Range(1, 10));
    list.RemoveAll(x => x > 5);
}

public static void Measure(string meas, Action act)
{
    GC.Collect();
    GC.WaitForPendingFinalizers();
    var st = new Stopwatch();
    st.Start();
    for (var i = 0; i < 10000000; i++)
        act();
    st.Stop();
    Console.WriteLine($"{meas}: {st.Elapsed}");
}

static void Main(string[] args)
{
    Measure("A", MethodA);
    Measure("B", MethodB);
    Measure("C", MethodC);
}

The result:

A: 00:00:04.1179163

B: 00:00:07.7417853

C: 00:00:04.3525255

Other runs give even more similar results (note that this is for 10 million iterations on a 10 item list [thus doing 100 million operations]... a difference of ~3 seconds is not what I'd call "significant", but your mileage may vary)

So go with what you think you can read better (I'd personally use the RemoveAll method)

Note: as you grow your list (this is just 10 items), MethodB (the foreach one that duplicates the list) will be slower and the differences will be higher, since the duplication of the list will be more costly. For example, doing a list of 1,000 items (with the condition being on 500 instead of 5) and 100,000 iterations, makes MethodB be 34 seconds, while both others run under 2 seconds on my machine. So yes, definitely don't use MethodB :-)

This doesn't mean that foreach is less efficient than for, it only means that for using foreach to remove items from a list, you need to duplicate said list, and that is costly.

This other method (using foreach) should be about as fast as the for or RemoveAll methods (it's a tiny bit slower in my profiling -because it allocates a new list, I figure-, but pretty much negligible):

public static void MethodD()
{
    var originalList = new List<int>(Enumerable.Range(1, 1000));
    var list = new List<int>(originalList.Count);
    foreach (var item in originalList)
    {
        if (item <= 500)
            list.Add(item);
    }
    list.Capacity = list.Count;
}

You just need to reverse the condition.

I'm not suggesting this method, just proving that foreach is not necessarily slower than for

Answer 5

Another way could be to foreach the list, set the item to null and then do a linq remove to (item => null), as already said, it's up to you to choose the way that suits you better