Enumeration and Iterators

Enumeration

An enumerator is a read-only, forward-only cursor over a sequence of values. An enumerator is an object that implements System.Collections.IEnumerator or System.Collections.Generic.IEnumerator<T>.

The foreach statement iterates over an enumerable object. An enumerable object is the logical representation of a sequence. It is not itself a cursor, but an object that produces cursors over itself. An enumerable either implements IEnumerable/IEnumerable<T> or has a method named GetEnumerator that returns an enumerator.

The enumeration pattern is as follows:

class Enumerator   // Typically implements IEnumerator<T>
{
  public IteratorVariableType Current { get {...} }
  public bool MoveNext() {...}
}
class Enumerable   // Typically implements IEnumerable<T>
{
  public Enumerator GetEnumerator() {...}
}

Here is the high-level way of iterating through the characters in the word beer using a foreach statement:

foreach (char c in "beer") Console.WriteLine (c);

Here is the low-level way of iterating through the characters in beer without using a foreach statement:

using (var enumerator = "beer".GetEnumerator())
  while (enumerator.MoveNext())
  {
    var element = enumerator.Current;
    Console.WriteLine (element);
  }

If the enumerator implements IDisposable, the foreach statement also acts as a using statement, implicitly disposing the enumerator object as in the earlier example.

Collection Initializers

You can instantiate and populate an enumerable object in a single step. For example:

using System.Collections.Generic;
...

List<int> list = new List<int> {1, 2, 3};

The compiler translates the last line into the following:

List<int> list = new List<int>();
list.Add (1); list.Add (2); list.Add (3);

This requires that the enumerable object implements the System.Collections.IEnumerable interface, and that it has an Add method that has the appropriate number of parameters for the call.

Iterators

Whereas a foreach statement is a consumer of an enumerator, an iterator is a producer of an enumerator. In this example, we use an iterator to return a sequence of Fibonacci numbers (where each number is the sum of the previous two):

using System;
using System.Collections.Generic;

class Test
{
  static void Main()
  {
    foreach (int fib in Fibs(6))
      Console.Write (fib + "  ");
  }

  static IEnumerable<int> Fibs(int fibCount)
  {
    for (int i = 0, prevFib = 1, curFib = 1;
         i < fibCount;
         i++)
    {
      yield return prevFib;
      int newFib = prevFib+curFib;
      prevFib = curFib;
      curFib = newFib;
    }
  }
}
OUTPUT: 1  1  2  3  5  8

Whereas a return statement expresses “Here’s the value you asked me to return from this method,” a yield return statement expresses “Here’s the next element you asked me to yield from this enumerator.” On each yield statement, control is returned to the caller, but the callee’s state is maintained so that the method can continue executing as soon as the caller enumerates the next element. The lifetime of this state is bound to the enumerator, such that the state can be released when the caller has finished enumerating.

Note

The compiler converts iterator methods into private classes that implement IEnumerable<T> and/or IEnumerator<T>. The logic within the iterator block is “inverted” and spliced into the MoveNext method and Current property on the compiler-written enumerator class. This means that when you call an iterator method, all you’re doing is instantiating the compiler-written class; none of your code actually runs! Your code runs only when you start enumerating over the resultant sequence, typically with a foreach statement.

Iterator Semantics

An iterator is a method, property, or indexer that contains one or more yield statements. An iterator must return one of the following four interfaces (otherwise, the compiler will generate an error):

System.Collections.IEnumerable
System.Collections.IEnumerator
System.Collections.Generic.IEnumerable<T>
System.Collections.Generic.IEnumerator<T>

Iterators that return an enumerator interface tend to be used less often. They’re useful when writing a custom collection class: typically, you name the iterator GetEnumerator and have your class implement IEnumerable<T>.

Iterators that return an enumerable interface are more common—and simpler to use because you don’t have to write a collection class. The compiler, behind the scenes, writes a private class implementing IEnumerable<T> (as well as IEnumerator<T>).

An iterator can include multiple yield statements:

static void Main()
{
  foreach (string s in Foo())
    Console.Write (s + " ");    // One Two Three
}

static IEnumerable<string> Foo()
{
  yield return "One";
  yield return "Two";
  yield return "Three";
}

The yield break statement indicates that the iterator block should exit early, without returning more elements. We can modify Foo as follows to demonstrate:

static IEnumerable<string> Foo (bool breakEarly)
{
  yield return "One";
  yield return "Two";
  if (breakEarly) yield break;
  yield return "Three";
}

Warning

A return statement is illegal in an iterator block—you must use yield break instead.

Composing Sequences

Iterators are highly composable. We can extend our Fibonacci example by adding the following method to the class:

static IEnumerable<int> EvenNumbersOnly (
  IEnumerable<int> sequence)
  {
    foreach (int x in sequence)
      if ((x % 2) == 0)
        yield return x;
  }
}

We can then output even Fibonacci numbers as follows:

foreach (int fib in EvenNumbersOnly (Fibs (6)))
  Console.Write (fib + " ");   // 2 8

Each element is not calculated until the last moment—when requested by a MoveNext() operation. Figure 1-5 shows the data requests and data output over time.

The composability of the iterator pattern is essential in building LINQ queries.

Composing sequences

Figure 1-5. Composing sequences