Is it safe to add items to the List while iterating through it

Question

I understand that one cannot use an enumerator and make amendments to List<T> at the same time. Adding or removing an item will invalidate the enumerator(http://msdn.microsoft.com/en-us/library/system.collections.ienumerator(v=vs.110).aspx), since the internal array will be reallocated(http://msdn.microsoft.com/en-us/library/3wcytfd1(v=vs.110).aspx).

1. Is it always true, even if Count is less than Capacity?(As far as I understand in this case the array won't be reallocated, so the enumerator has to be valid);
2. Why Current returns the element that it is set to, even if the enumerator is already invalidated?(I mean, if the array was reallocated...);
3. Does reallocation preservers the original order of the items? I mean if some item has index of n, will it have the same index after adding and item?(MSDN says that Add adds an object to the end of the list) If so, it is safe to run through a list in a regular for loop and to add the items assuming that the loop will iterate through each item only once, am I correct?

Answer 1

Is it always true, even if Count is less than Capacity

This may or may not be true. However, you should act as if it is always true, because the documentation does not make any exceptions for this behavior.

At least one implementation of List<T> (from the Mono project) always invalidates all iterators by incrementing a hidden member called _version which is stored inside the list, in every operation that changes the list. When you obtain an iterator (which is called Enumerator in .NET) the current value of _version is stored inside the enumerator object. Every time you call MoveNext, the stored _version is compared to the current _version, and an exception is thrown when the two do not match.

Why Current returns the element that it is set to, even if the enumerator is already invalidated?

Because the value of Current is stored in the iterator. While there is a good reason to stop you from iterating further when the collection has been modified, it is fine to let you access the value at the position to which you advanced the iterator when it has been valid.

Does reallocation preservers the original order of the items?

Yes. That is why traversing a list with a for loop and an index remains safe even when you add or remove elements from your list.

Answer 2

1. The internal array is not reallocated every time items are added/removed from the list, and that's not the reason why the enumerator is invalidated. Here's a better reason: Collection was modified; enumeration operation may not execute - why?.

   To put it simply, the internal array is reallocated when its capacity is exhausted, and the array's size will be doubled. Some collections also allow you to prune the internal array, e.g., List<T>.TrimExcess

2. Why not? The object still exists.

3. Yes

Take a look at the source code, particularly at EnsureCapacity and List<T>.Enumerator if you want to know more.

Answer 3

Adding or removing an item will invalidate the enumerator, since the internal array will be reallocated

This is partially correct. Adding, removing or inserting items will invalidate the enumerator not because internal array will be reallocated but because List<T> maintains a version field internally to track the changes that has happened. Enumerator will use the version field to find any new updates has happened since enumerator was created.

To answer your questions:

1. Enumerator is not valid^[1] if you modify the list irrespective of the "Count < Capacity", because it doesn't matter. What matters is the version field.
2. Because enumerator takes a copy of current element from the List.
3. Yes re allocation preserves the order.

---

1: It is not always true, there is a bug in the implementation.