Question Bug with removing a list entry while in an IEnumerator

Hello, I'm getting an

InvalidOperationException: Collection was modified; enumeration operation may not execute.

error when I try to remove an item from a list using

list.Remove(item);

inside a

while

loop inside an

IEnumerator

. Here is a cut down example of my code. Please ignore how many curly brackets there are, I haven't counted them and there may be extras.

Code (CSharp):

1. private IEnumerator Ticker()
2.         {
3.             while (true)
4.             {
5.                 foreach (var s in stats)
6.                 {
7.                     if (s.enabled)
8.                     {
9.                         foreach (var se in s.status)
10.                         {
11.                               s.status.Remove(se);
12.                         }
13.                         }
14.                     }
15.                 }
16.                 yield return new WaitForSecondsRealtime(7);
17.             }
18.         }

The specific problem is having

Remove(se);

in there, but I sorta need that. Any ideas how I can fix this? I suppose I could just cue it up to be removed in Update(), but that seems wasteful.

EDIT FOR ANYONE SEEKING THE ANSWER

You can add

.ToList()

to the list in the

foreach

however this is inefficient.

Code (CSharp):

1. foreach (var item in list.ToList())
2. {
3.      list.Remove(item);
4. }

It is better to use a reverse for loop. Reverse because the list drops items backwards to fill space.

Code (CSharp):

1. for (int i = s.status.Count - 1; i >= 0; i--)
2. {
3.     var se = s.status[i];
4.     // do stuff with se if needed
5.     s.status.RemoveAt(i);
6. }

 

Can’t modify the collection.


Make a new list record your entry data and then process the replacement of the original list with the new list after the for each has completed

 

Linked list can also be used. Be sure to pool the LinkedListNode when you remove a item otherwise you will strain the GC

 

Okay thanks guys

GC?

 

If you do not pool the LinkedListNode it will be garbage collected which can lead to spikes

 

You can do

foreach (var s in stats.ToArray())

Or do it in the foreach loop below that. Should solve the problem immediately, but im not sure if its good practice outside of prototyping.

 

It's a o(n) operation plus allocation. Depends on use case if bad

 

Thank you. What do you mean by LinkedListNode? Can you link to anything about using that in the way you describe?

 

The LinkedListNode<T> is the element type in a linked list. When you add a new item to a linked list it's a LinkedListNode being added. In same fashion a LinkedListNode is removed when removing from a linked list. Since LinkedListNode is a reference type it allocates on the heap.

 

Oh! Thank you!

 

To modify a list from a loop, you need to iterate the list with indexes instead of using an enumerator. The usual way is with a reverse for loop :

Code (CSharp):

1. for (int i = s.status.Count - 1; i >= 0; i--)
2. {
3.     var se = s.status[i];
4.     // do stuff with se if needed
5.     s.status.RemoveAt(i);
6. }

Also note that if you're removing all entries, you can (should) just call

s.status.Clear()

after the foreach loop instead of removing each element one by one.

 

Thanks. I've not really seen a reverse loop before. Any reason I'd use that?

 

Otherwise you would miss an item since you advance to the next index

 

It's mainly convenience. You can't directly do a forward for loop because you would skip entries. To do a forward iteration while deleting some entries, you need to use a while loop :

Code (CSharp):

1. int i = 0;
2. while (i < list.Count)
3. {
4.   if (someCondition)
5.     list.RemoveAt(i);
6.   else
7.     i++;
8. }

 

Ah, okay, thanks.

 

By the way, I remembered I had this issue before and I've rediscovered the fix in my old code files. Just add

.ToList()

to the list in the

foreach

Code (CSharp):

1. foreach (var item in list.ToList())
2. {
3.      list.Remove(item);
4. }

 

Just be aware of the O(n) and allocation implication

 

Thanks, could you explain what you mean a little?

 

Why not just use List.clear()? That's all that code above does, right? Even if that's too fancy,

list = new List<whatever>()

should do the same thing, but better.

 

While this technically work, it's an incredibly inefficient way of doing this, and a bad practice in general.

Not only you're instantiating an useless new list (which is slow and is increasing GC pressure), but using

Remove(item)

is causing a full iteration of reference comparisons on the list, which is also very slow. Plus, it's not safe to use if your list has duplicate entries.

Learn the good habit of using a reverse for loop and

RemoveAt(index)

. Better write efficient and safe code the first time, that will save you a lot of time and trouble in the long run.

And as @Owen-Reynolds mentionned, if you're removing all entries every time, just do a

List.Clear()

after the foreach loop instead of removing entries one by one. That is the cleanest and most performant way.

 

Just beaware that RemoveAt is a O(n) method



So depending on usecase a LinkedList can be better like I described earlier.

 

Yes, RemoveAt(index) is a O(n) method, but my point is that Remove(item) is even slower.

And while a LinkedList has amortized (not O(1) either) random Remove() performance, it is vastly slower for Add() and random access. Moreover, a List is still a lot faster if you're only adding/removing the last item.

In the overwhelming majority of use cases, a List is just as fast if not faster, less cumbersome to use, vastly less memory intensive. A LinkedList is a specialized collection that only make sense in a few specific situations, so never use it unless you have a deep understanding of its use case.

 

Because it's not actually removing every item in the real code, I'm just simplifying things because I know what's causing the error. Basically it's a list of timed status effects, and this is updating the effects on it.

Ah okay, thank you. I knew it was making a new list but I didn't realise it was that bad

 

Oh so that's why the backwards for loop, thank you

 

Eh no. But if you call it from a loop it's potentially O(n^2)

 

The normal way to remove _some_ items from a list is removeAll. Like

L.removeAll(c=>c.age<2)

(to remove all cats younger than 2 years). It's well-known and faster than anything else. It uses a single loop, from front-to-back. When it sees an item to delete, it merely adds to the count and moves on. Each good item, as you hit them, gets slid back by the count. It's a fun example to write or just play with, often covered in 1st semester programming.

Going backwards and calling removeAt is just one way to avoid "jumping" an item when two are in a row. Suppose we remove #6 and #7 is also bad. It turns out that removing #6 slides item #7 down into slot 6. But then foreach moves from 6 to 7. So we skipped item old-7-new-6. Going backwards just happens to not do that. But you can also fix that problem while going forwards -- when an item is removed, don't add 1 to the loop count. That's also fun practice.

These lists are probably all pretty small and this probably isn't done that often. I'm sure it's fast enough as is. But, if you have to keep tweaking this code, it might be easier to rewrite to be easier to read (in 2 months, you're going to look at the ToList() and think "why in the heck do I create a copy?")

 

Is that good or bad?

 

RemoveAt at is a O(n) operation so be aware. Each time you call it it needs to traverse all elements. But like pointed out above. It depends on use case. If you iterate over it more often than removing from it it will probably still be faster than a LinkedList

Just be aware. While Remove(LinkedListNode<T>) is a O(1) operation the overload bool Remove (T value) is a O(n) operation. So its only fast if you are using nodes

 

I'm sorry, but I'm not clear on what O(n) or O(n^2) operations are. I know it's a notation, but I can't find anything online related to what it actually is that gives me an introduction to it.

 

That’s the big-O notation, which expresses the growth behavior of an algorithm in terms of space complexity or time complexity. You usually see people use it when talking about the worst case bound on time complexity.

The basic gist of it is like this. Say you have an input with a known length n*. This can be the size of a collection or some other metric of the input complexity. If an algorithm has worst-case time complexity O(n^2), then the time it takes to run the algorithm scales quadratically. An input twice the size of the original input (2n vs n) takes 4 times the time it takes the original input (4n^2 vs n^2), and an input 4 times the size of the original input takes 16 times the time (16n^2 vs n^2). O(n) scales linearly (input size 2n takes only 2 times the original time, which is better performance than O(n^2)). O(1) is constant time, meaning you have some fixed bounds irrespective of n, and that’s generally ideal if you get a low order of magnitude for the constant amount of time (you probably don’t want an algorithm that always takes 10 minutes if you have another one that only takes 10 seconds on the inputs you’re expecting). In general, the slower the time complexity grows, the better. Any expression in terms of the input variables work for big-O notation. You often see things like O(log n) (binary search trees) or O(n log n) (sorting lists, and also happens to be a provable bound on the worst case time complexity for sorting).

*n is the typical variable name, but in other cases we can have multiple variables like m (number of edges) and n (number of vertices) when discussing algorithms for graphs.

 

The layman's version of that O(n) stuff has to do with how C# lists work -- they're arrays. When you create a List it makes a hidden size 4 array and a variable Count, set to 0. The rest is obvious -- list.Add puts it in the next free slot (of the secret array) and increases Count. Removing the last item does the opposite. If you go past 4 it does what you'd have to do -- creates a new size-8 array and copies over the old 4 items.

Once we know Lists are arrays, we know what Remove does on an item in the middle. It has to slide everything past the removed item down by 1 space, to fill the hole. That's a loop. Kind of a surprise, right? If you have a size 1000 list then list.removeAt(499) takes 500 steps as it slides down everything 500 to 999. If you go through that list (either forwards or backwards) removing some things, it's a nested loop! It goes through all 1000 items, and each thing removed takes about 500 steps. Removing 100 things takes about 100*500 = 50,000 steps!

O(n) is just the math way of saying how many nested loops something is. "list.remove is O(n)" means it's a loop. "Your whole thing is O(n^2)" just means it's a nested loop. O(n^3) means a triple-nested loop. It seems weird, but it's in most manuals that way since it also works for tricky stuff (for example, O(n) could mean a funny nested loop which works out to run like a single loop).

For fun you can see list's array grow with Capacity. This shows it starting at 4, then growing to 8, 16 then 32, as the size maxes out each time:

Code (CSharp):

1. List<int> N = new List<int>();
2. for(int i=0;i<21;i++) {
3.   N.Add(0);
4.   print("count/cap="+N.Count+"/"+N.Capacity);
5. }

 

Ah okay. Thank you.

That's interesting. I thought you couldn't alter array size.

 

You can't you have to allocate memory for a new array with the size you need.