Are there any C# collections where modification does not invalidate iterators?

Question

Are there any data structures in the C# Collections library where modification of the structure does not invalidate iterators?

Consider the following:

List<int> myList = new List<int>();
myList.Add( 1 );
myList.Add( 2 );
List<int>.Enumerator myIter = myList.GetEnumerator();
myIter.MoveNext();  // myIter.Current == 1
myList.Add( 3 );
myIter.MoveNext();  // throws InvalidOperationException

Answer 1

Use a for loop instead of a foreach, and then you can modify it. I wouldn't advise it though....

Answer 2

No, they do not exist. ALl C# standard collections invalidate the numerator when the structure changes.

Answer 3

The only way to do this is to make a copy of the list before you iterate it:

var myIter = new List<int>(myList).GetEnumerator();

Answer 4

According to this MSDN article on IEnumerator the invalidation behaviour you have found is required by all implementations of IEnumerable.

An enumerator remains valid as long as the collection remains unchanged. If changes are made to the collection, such as adding, modifying, or deleting elements, the enumerator is irrecoverably invalidated and the next call to MoveNext or Reset throws an InvalidOperationException. If the collection is modified between MoveNext and Current, Current returns the element that it is set to, even if the enumerator is already invalidated.

Answer 5

Yes, take a look at the System.Collections.Concurrent namespace in .NET 4.0.

Note that for some of the collections in this namespace (e.g., ConcurrentQueue<T>), this works by only exposing an enumerator on a "snapshot" of the collection in question.

From the MSDN documentation on ConcurrentQueue<T>:

The enumeration represents a moment-in-time snapshot of the contents of the queue. It does not reflect any updates to the collection after GetEnumerator was called. The enumerator is safe to use concurrently with reads from and writes to the queue.

This is not the case for all of the collections, though. ConcurrentDictionary<TKey, TValue>, for instance, gives you an enumerator that maintains updates to the underlying collection between calls to MoveNext.

From the MSDN documentation on ConcurrentDictionary<TKey, TValue>:

The enumerator returned from the dictionary is safe to use concurrently with reads and writes to the dictionary, however it does not represent a moment-in-time snapshot of the dictionary. The contents exposed through the enumerator may contain modifications made to the dictionary after GetEnumerator was called.

If you don't have 4.0, then I think the others are right and there is no such collection provided by .NET. You can always build your own, however, by doing the same thing ConcurrentQueue<T> does (iterate over a snapshot).

Answer 6

Supporting this behavior requires some pretty complex internal handling, so most of the collections don't support this (I'm not sure about the Concurrent namespace).

However, you can very well simulate this behavior using immutable collections. They don't allow you to modify the collection by design, but you can work with them in a slightly different way and this kind of processing allows you to use enumerator concurrently without complex handling (implemented in Concurrent collections).

You can implement a collection like that easily, or you can use FSharpList<T> from FSharp.Core.dll (not a standard part of .NET 4.0 though):

open Microsoft.FSharp.Collections;

// Create immutable list from other collection
var list = ListModule.OfSeq(anyCollection);
// now we can use `GetEnumerable`
var en = list.GetEnumerable();

// To modify the collection, you create a new collection that adds 
// element to the front (without actually copying everything)
var added = new FSharpList<int>(42, list);

The benefit of immutable collections is that you can work with them (by creating copies) without affecting the original one, and so the behavior you wanted is "for free". For more information, there is a great series by Eric Lippert.