Crouching Enumerator, Hidden Boxing

A few months ago, I was playing around with a simple C# permutation generator to build a word list, with each character position having its own list of characters to iterate through:

List.Enumerator enumerator = characterList.GetEnumerator();

while (condition) {
	if (!enumerator.MoveNext()) {
		enumerator.Reset();
		enumerator.MoveNext();
	}

	Consume(enumerator.Current);
}

Oddly, I was getting a compilation error on line 5, as enumerator doesn’t have a Reset() method despite the IEnumerator interface defining one. MSDN quickly cleared things up, though, revealing that List<T>.Enumerator explicitly implements the method as void IEnumerator.Reset(), which is implicitly private. You can still call private interface methods if you first cast to that interface, so I changed line 5 to the following:

		((IEnumerator) enumerator).Reset();

I thought that was the end of it, but bizarely, the second call to MoveNext() on line 6 also returns false. I confirmed that the private Reset() method actually implements reset functionality, which it certainly does, yet it seemed to have no effect.

The answer lies in the fact that List<T>.Enumerator is a struct. This means that behind the scenes, the cast to IEnumerator is creating a boxed copy of enumerator, and that’s what’s being reset. The original is left untouched, so the call to MoveNext() will naturally return false. Rather than trying to keep the boxed copy that you get from the cast, the correct solution is to use IEnumerator<T> from the outset, rather than List<T>.Enumerator:

IEnumerator enumerator = characterList.GetEnumerator();

while (condition) {
	if (!enumerator.MoveNext()) {
		enumerator.Reset();
		enumerator.MoveNext();
	}

	Consume(enumerator.Current);
}

All this drama could have been avoided if I hadn’t checked the return type for List<T>.GetEnumerator() and used that. So much for more explicit typing being helpful.

Still, it’s rather odd that List<T>.Enumerator is both public and a struct. The former encourages its direct use, and the latter results in the problem I was experiencing. Sadly, this design is constant throughout the System.Collections.Generic namespace. By contrast, the equivalent non-generic collection is ArrayList, and there, the GetEnumerator() method returns an IEnumerator, which is implemented by a private class nested within the ArrayList type – a design that is constant throughout the rest of the System.Collections namespace, and is, in my opinion, better for everyone.

  • List implements its enumerator as a struct so that the caller has a way to avoid garbage collection induced by boxing of the IEnumerator. If you get the iterator explicitly as a List.Enumerator (and iterate it with MoveNext) then no extra allocation is done. If you get the iterator as an IEnumerator then the underlying struct gets wrapped in a dynamically allocated object that lets you access it via the interface.

    So it is slightly confusing, but there’s a method to the madness.

Leave a Reply

Your email address will not be published. Required fields are marked *