Different collection types may have different accessing schemes. Not all types of collections can be accessed efficiently with an index like an array's — the linked list, for example. Differences between collection types make it impossible to write a method such as the following without special provisions:

// Pass in any kind of collection:
void MyClearMethod(Collection aColl, int index)
{
  aColl[index] = 0; // Indexing doesn't work for all types of collections.
  // ...continues...
}

Each collection type can (and does) define its own access methods. For example, a linked list may offer a GetNext() method to fetch the next element in the chain of objects or a stack collection may offer a Push() and Pop() to add and remove objects.

A more general approach is to provide for each collection class a separate iterator class, which is wise in the ways of navigating that particular collection. Each collection X defines its own class IteratorX. Unlike X, IteratorX offers a common IEnumerator interface, the gold standard of iterating. This technique uses a second object, the iterator, as a kind of pointer, or cursor, into the collection.

The iterator (enumerator) approach offers these advantages:

To make the foreach loop possible, the IEnumerator interface must support all different types of collections, from arrays to linked lists. Consequently, its methods must be as general as possible. For example, you can't use the iterator to access locations within the collection class randomly because most collections don't provide random access. (You'd need to invent a different enumeration interface with that ability, but it wouldn't work with foreach.)

IEnumerator provides these three methods:

The following method demonstrates this principle. The programmer of the MyCollection class (not shown) creates a corresponding iterator class — say, IteratorMyCollection (using the IteratorX naming convention that I describe earlier in this chapter). The application programmer has stored numerous ContainedDataObjects in MyCollection. The following code segment uses the three standard IEnumerator methods to read these objects back out:

// The MyCollection class holds ContainedDataObject type objects as data.
void MyMethod(MyCollection myColl)
{
  // The programmer who created the MyCollection class also
  // creates an iterator class IteratorMyCollection;
  // the application program creates an iterator object
  // in order to navigate through the myColl object.
  IEnumerator iterator = new IteratorMyCollection(myColl);
  // Move the enumerator to the "next location" within the collection.
  while(iterator.MoveNext())
  {
    // Fetch a reference to the data object at the current location
    // in the collection.
    ContainedDataObject contained;  // Data
    contained = (ContainedDataObject)iterator.Current;
    // ...use the contained data object...
  }
}

The method MyMethod() accepts as its argument the collection of ContainedDataObjects. It begins by creating an iterator of class IteratorMyCollection. The method starts a loop by calling MoveNext(). On this first call, MoveNext() moves the iterator to the first element in the collection. On each subsequent call, MoveNext() moves the pointer "over one position." MoveNext() returns false when the collection is exhausted and the iterator cannot be moved any farther.

The Current property returns a reference to the data object at the current location of the iterator. The program converts the object returned into a ContainedDataObject before assigning it to contained. Calls to Current are invalid if the MoveNext() method didn't return true on the previous call or if MoveNext() hasn't yet been called.

The IEnumerator methods are standard enough that C# uses them automatically to implement the foreach statement.

The foreach statement can access any class that implements IEnumerable or IEnumerable<T>. I discuss foreach in terms of IEnumerable<T> in this section, as shown in this general method that is capable of processing any such class, from arrays to linked lists to stacks and queues:

void MyMethod(IEnumerable<T> containerOfThings)
{
  foreach(string s in containerOfThings)
  {
    Console.WriteLine("The next thing is {0}", s);
  }
}

A class implements IEnumerable<T> by defining the method GetEnumerator(), which returns an instance of IEnumerator<T>. Under the hood, foreach invokes the GetEnumerator() method to retrieve an iterator. It uses this iterator to make its way through the collection. Each element it retrieves has been cast appropriately before continuing into the block of code contained within the braces. Note that IEnumerable<T> and IEnumerator<T> are different, but related, interfaces. C# provides non-generic versions of both as well, but you should prefer the generic versions for their increased type safety.

IEnumerable<T> looks like this:

interface IEnumerable<T>
{
  IEnumerator<T> GetEnumerator();
}

while IEnumerator<T> looks like this:

interface IEnumerator<T>
{
  bool MoveNext();
  T Current { get; }
}

The nongeneric IEnumerator interface adds a Reset() method that moves the iterator back to the beginning of the collection, and its Current property returns type Object. Note that IEnumerator<T> inherits from IEnumerator — and recall that interface inheritance (covered in Book II, Chapter 8) is different from normal object inheritance.

C# arrays (embodied in the Array class they're based on) and all the .NET collection classes already implement both interfaces. So it's only when you're writing your own custom collection class that you need to take care of implementing these interfaces. For built-in collections, you can just use them. See the System.Collections.Generic namespace topic in Help.

Thus you can write the foreach loop this way:

foreach(int nValue in myCollection)
{
  // ...
}

The indexer looks much like an ordinary get/set property, except for the appearance of the keyword this and the index operator [] instead of the property name, as shown in this bit of code:

class MyArray
{
  public string this[int index]   // Notice the "this" keyword.
  {
    get
    {
      return array[index];
    }
    set
    {
      array[index] = value;
    }
  }
}

Under the hood, the expression s = myArray[i]; invokes the get accessor method, passing it the value of i as the index. In addition, the expression myArray[i] = "some string"; invokes the set accessor method, passing it the same index i and "some string" as value.

The index type isn't limited to int. You may choose to index a collection of houses by their owners' names, by house address, or by any number of other indices. In addition, the indexer property can be overloaded with multiple index types, so you can index on a variety of elements in the same collection.

The following Indexer program generates the virtual array class KeyedArray. This virtual array looks and acts like an array except that it uses a string value as the index:

// Indexer -- This program demonstrates the use of the index operator
//    to provide access to an array using a string as an index.
//    This version is nongeneric, but see the IndexerGeneric example.
using System;

namespace Indexer
{
  public class KeyedArray
  {
    // The following string provides the "key" into the array --
    // the key is the string used to identify an element.
    private string[] _keys;

    // The object is the actual data associated with that key.
    private object[] _arrayElements;

    // KeyedArray -- Create a fixed-size KeyedArray.
    public KeyedArray(int size)
    {
      _keys = new string[size];
      _arrayElements = new object[size];
    }

    // Find -- Find the index of the element corresponding to the
    //    string targetKey (return a negative if it can't be found).
    private int Find(string targetKey)
    {
      for(int i = 0; i < _keys.Length; i++)
      {
        if (String.Compare(_keys[i], targetKey) == 0)
        {
          return i;
        }
      }
      return −1;
    }

    // FindEmpty -- Find room in the array for a new entry.
    private int FindEmpty()
    {
      for (int i = 0; i < _keys.Length; i++)
      {
        if (_keys[i] == null)
        {
          return i;
        }
      }

throw new Exception("Array is full");
    }

    // Look up contents by string key -- this is the indexer.
    public object this[string key]
    {
      set
      {
        // See if the string is already there.
        int index = Find(key);
        if (index < 0)
        {
          // It isn't -- find a new spot.
          index = FindEmpty();
          _keys[index] = key;
        }

        // Save the object in the corresponding spot.
        _arrayElements[index] = value;
      }

      get
      {
        int index = Find(key);
        if (index < 0)
        {
          return null;
        }
        return _arrayElements[index];
      }
    }
  }

  public class Program
  {
    public static void Main(string[] args)
    {
      // Create an array with enough room.
      KeyedArray ma = new KeyedArray(100);

      // Save the ages of the Simpson kids.
      ma["Bart"] = 8;
      ma["Lisa"] = 10;
      ma["Maggie"] = 2;

      // Look up the age of Lisa.
      Console.WriteLine("Let's find Lisa's age");
      int age = (int)ma["Lisa"];
      Console.WriteLine("Lisa is {0}", age);

      // Wait for user to acknowledge the results.
      Console.WriteLine("Press Enter to terminate...");
      Console.Read();
    }
  }
}

The class KeyedArray holds two ordinary arrays. The _arrayElements array of objects contains the actual KeyedArray data. The strings that inhabit the _keys array act as identifiers for the object array. The ith element of _keys corresponds to the ith entry of _arrayElements. The application program can then index KeyedArray via string identifiers that have meaning to the application.

The set[string] indexer starts by checking to see whether the specified index already exists by calling the method Find(). If Find() returns an index, set[] stores the new data object into the corresponding index in _arrayElements. If Find() can't find the key, set[] calls FindEmpty() to return an empty slot in which to store the object provided.

The get[] side of the index follows similar logic. It first searches for the specified key using the Find() method. If Find() returns a nonnegative index, get[] returns the corresponding member of _arrayElements where the data is stored. If Find() returns −1, get[] returns null, indicating that it can't find the provided key anywhere in the list.

The Find() method loops through the members of _keys to look for the element with the same value as the string targetKey passed in. Find() returns the index of the found element (or −1 if none was found). FindEmpty() returns the index of the first element that has no key element.

The Main() method demonstrates the Indexer class in a trivial way:

public class Program
{
  public static void Main(string[] args)
  {
    // Create an array with enough room.
    KeyedArray ma = new KeyedArray(100);

    // Save the ages of the Simpson kids.
    ma["Bart"] = 8;
    ma["Lisa"] = 10;
    ma["Maggie"] = 2;

    // Look up the age of Lisa.
    Console.WriteLine("Let's find Lisa's age");
    int age = (int)ma["Lisa"];
    Console.WriteLine("Lisa is {0}", age);

    // Wait for user to acknowledge the results.
    Console.WriteLine("Press Enter to terminate...");
    Console.Read();
  }
}

The program creates a KeyedArray object ma of length 100 (that is, with 100 free elements). It continues by storing the ages of the children in The Simpsons TV show, indexed by each child's name. Finally, the program retrieves Lisa's age using the expression ma["Lisa"] and displays the result. The expression ma["Lisa"] is read as "ma sub-Lisa."

Notice that the program has to cast the value returned from ma[] because KeyedArray is written to hold any type of object. The cast wouldn't be necessary if the indexer were written to handle only int values — or if the KeyedArray were generic. (For more information about generics, see Chapter 8 in this minibook.)

The output of the program is simple yet elegant:

Let's find Lisa's age
Lisa is 10
Press Enter to terminate...

The following fragment from the IteratorBlocks example provides an iterator that steps through the months of the year:

//MonthDays -- Define an iterator that returns the months
//   and their lengths in days -- sort of a "collection" class.
class MonthDays
{
  // Here's the "collection."
  string[] months =
          { "January 31", "February 28", "March 31",
            "April 30", "May 31", "June 30", "July 31",
            "August 31", "September 30", "October 31",
            "November 30", "December 31" };

  //GetEnumerator -- Here's the iterator. See how it's invoked
  //   in Main() with foreach.
  public System.Collections.IEnumerator GetEnumerator()
  {
    foreach (string month in months)
    {
      // Return one month per iteration.
      yield return month;
    }
  }
}

Here's part of a Main() method that iterates this collection using a foreach loop:

// Instantiate a MonthDays "collection" class.
MonthDays md = new MonthDays();
// Iterate it.
foreach (string month in md)
{
  Console.WriteLine(month);
}

This extremely simple collection class is based on an array, as KeyedArray is. The class contains an array whose items are strings. When a client iterates this collection, the collection's iterator block delivers strings one by one. Each string contains the name of a month (in sequence), with the number of days in the month tacked on to the string. It isn't useful, but, boy, is it simple — and different!

The class defines its own iterator block, in this case as a method named GetEnumerator(), which returns an object of type System.Collections.IEnumerator. Now, it's true that you had to write such a method before, but you also had to write your own enumerator class to support your custom collection class. Here, you just write a fairly simple method to return an enumerator based on the new yield return keywords. C# does the rest for you: It creates the underlying enumerator class and takes care of calling MoveNext() to iterate the array. You get away with much less work and much simpler code.

In the following sections, I show you several varieties of iterator blocks:

Note that class MonthDays' GetEnumerator() method contains a foreach loop to yield the strings in its inner array. Iterator blocks often use a loop of some kind to do this, as you can see in several later examples. In effect, you have in your own calling code an inner foreach loop serving up item after item that can be iterated in another foreach loop outside GetEnumerator().

Take a moment to compare the little collection in this example with an elaborate LinkedList collection. Whereas LinkedList has a complex structure of nodes connected by pointers, this little months collection is based on a simple array — with canned content, at that. I'm expanding the collection notion a bit, and I expand it even more before this chapter concludes.

(Your collection class may not contain canned content — most collections are designed to hold things you put into them via Add() methods and the like. The KeyedArray class in the earlier section "Accessing Collections the Array Way: Indexers," for example, uses the [] indexer to add items. Your collection could also provide an Add() method as well as add an iterator block so that it can work with foreach.)

The point of a collection, in the most general sense, is to store multiple objects and to allow you to iterate those objects, retrieving them one at a time sequentially — and sometimes randomly, or apparently randomly, as well, as in the Indexer example. (Of course, an array can do that, even without the extra apparatus of a class such as MonthDays, but iterators go well beyond the MonthDays example, as I'll show you.)

More generally, regardless of what an iterable collection does under the hood, it produces a "stream" of values, which you get at with foreach. (I cover file streams in Book III — I'm liberating the stream concept to make a point about iterators.)

To drive home the point, here's another simple collection class from IteratorBlocks, one that stretches the idea of a collection about as far as possible (you may think):

//StringChunks -- Define an iterator that returns chunks of text,
//   one per iteration -- another oddball "collection" class.
class StringChunks
{
  //GetEnumerator -- This is an iterator; see how it's invoked
  //   (twice) in Main.
  public System.Collections.IEnumerator GetEnumerator()
  {
    // Return a different chunk of text on each iteration.
    yield return "Using iterator ";
    yield return "blocks ";
    yield return "isn't all ";
    yield return "that hard";
    yield return ".";
  }
}

Oddly, the StringChunks collection stores nothing in the usual sense. It doesn't even contain an array. So where's the collection? It's in that sequence of yield return calls, which use a special syntax to return one item at a time until all have been returned. The collection "contains" five objects, each a simple string much like the ones stored in an array in the previous MonthDays example. And, from outside the class, in Main(), you can iterate those objects with a simple foreach loop because the yield return statements deliver one string at a time, in sequence. Here's part of a simple Main() method that iterates a StringChunks collection:

// Instantiate a StringChunks "collection" class.
StringChunks sc = new StringChunks();
// Iterate it: prints pieces of text.
foreach (string chunk in sc)
{
  Console.WriteLine(chunk);
}

As of C# 2.0, the language introduced two new bits of iterator syntax. The yield return statement resembles the old combination of MoveNext() and Current for retrieving the next item in a collection. The yield break statement resembles the C# break statement, which lets you break out of a loop or switch statement.

foreach (string chunk in sc)
{
  Console.WriteLine(chunk);
}

//YieldBreakEx -- Another example of the yield break keyword
class YieldBreakEx
{
  int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
  //GetEnumerator -- Returns a sequence of prime numbers
  //   Demonstrates yield return and yield break
  public System.Collections.IEnumerator GetEnumerator()
  {
    foreach (int prime in primes)
    {
      if (prime > 13) yield break;
      yield return prime;
    }
  }
}

In earlier examples in this chapter, iterator blocks have looked like this:

public System.Collections.IEnumerator GetEnumerator()
{
  yield return something;
}

But iterator blocks can also take a couple of other forms: as named iterators and as class properties.

//EvenNumbers -- Define a named iterator that returns even numbers
//   from the "top" value you pass in DOWN to the "stop" value.
//   Another oddball "collection" class
class EvenNumbers

{
  //DescendingEvens -- This is a "named iterator."
  //   Also demonstrates the yield break keyword
  //   See how it's invoked in Main() with foreach.
  
public System.Collections.IEnumerable DescendingEvens(int top,
                                                      int stop)
  {
    // Start top at nearest lower even number.
    if (top % 2 != 0) // If remainder after top / 2 isn't 0.
      top -= 1;
    // Iterate from top down to nearest even above stop.
    for (int i = top; i >= stop; i -= 2)
    {
      if (i < stop)
        yield break;
      // Return the next even number on each iteration.
      yield return i;
    }
  }
}

public System.Collections.IEnumerable PositiveIntegers()
{
  for (int i = 0; ; i++)
  {
    yield return i;
  }
}

// Instantiate an EvenNumbers "collection" class.
EvenNumbers en = new EvenNumbers();
// Iterate it: prints even numbers from 10 down to 4.
Console.WriteLine("
stream of descending evens :
");
foreach (int even in en.DescendingEvens(11, 3))
{
  Console.WriteLine(even);
}

EvenNumbers en = new EvenNumbers();
foreach(int even in en.DescendingEvens(nTop, nStop)) ...

foreach(int even in EvenNumbers.DescendingEvens(nTop, nStop)) ...

//PropertyIterator -- Demonstrate implementing a class
//   property's get accessor as an iterator block.
class PropertyIterator
{
  double[] doubles = { 1.0, 2.0, 3.5, 4.67 };
  // DoubleProp -- A "get" property with an iterator block
  public System.Collections.IEnumerable DoubleProp
  {
    get
    {
      foreach (double db in doubles)
      {
        yield return db;
      }
    }
  }
}

// Instantiate a PropertyIterator "collection" class.
PropertyIterator prop = new PropertyIterator();
// Iterate it: produces one double at a time.
Console.WriteLine("
stream of double values:
");
foreach (double db in prop.DoubleProp)
{
  Console.WriteLine(db);
}

Hmm, I have to be careful about my phrasing.

In the small special-purpose iterator classes in the IteratorBlocks example, earlier in this chapter, I put the collection itself inside the iterator class, as in MonthDays. In some cases, that's just right — for instance, when the collection is something like SentenceChunks, which returns canned bits of text, or something like DescendingEvens, in which the return is calculated on the spot. But suppose that you want to supply an iterator based on an iterator block for a real collection class, such as LinkedList.

That's what I did in the LinkedListWithIteratorBlock example on this book's Web site. That example rewrites the roll-your-own LinkedList with a GetEnumerator() method implemented as an iterator block. It completely replaces the old LinkedListIterator class. The following listing gives just the new version of GetEnumerator() (you can see the whole example on this book's Web site):

// LinkedListWithIteratorBlock -- Implements iterator for the linked list as
//    an iterator block.
class LinkedList   // No longer need ": IEnumerator" here.
{
  ... rest of the class.
  ...
  // Here's the iterator, implemented as an iterator block.
  public IEnumerator GetEnumerator()
  {
    // Make sure the current node is legal.
    // If it's null, it hasn't yet been set to point into the list,
    // so point it at the head.
    if (currentNode == null)
    {
      currentNode = head;
    }
    // Here's the iteration for the enumerator that
    // GetEnumerator() returns.
    while (currentNode != null)
    {
      yield return currentNode.Object;
      currentNode = currentNode.forward;
    }
  }
}

I show the following basic form of an iterator block in several sections earlier in this chapter, including the section "Iterating days of the month: A first example":

public System.Collections.IEnumerator GetEnumerator() {}

This line looks exactly like the IEnumerator object returned by GetEnumerator() in the original LinkedList class. But implementing the GetEnumerator() method now works quite differently, as explained in this list:

foreach(string s in llc)  // foreach does the cast for you here.
{
  Console.WriteLine(s);
}

// In file Program.cs:

// IteratorBlockIterator -- Implements a separate iterator object as a
//    companion to a collection class, a la LinkedList, but
//    implements the actual iterator with an iterator block
using System;
using System.Collections;
namespace IteratorBlockIterator
{
  class Program
  {

// Create a collection and use two iterator objects to iterate
    // it independently (each using an iterator block).
    static void Main(string[] args)
    {
      string[] strs = new string[] { "Joe", "Bob", "Tony", "Fred" };
      MyCollection mc = new MyCollection(strs);
      // Create the first iterator and start the iteration.
      MyCollectionIterator mci1 = mc.GetEnumerator();
      foreach (string s1 in mci1)  // Uses the first iterator object
      {
        // Do some useful work with each string.
        Console.WriteLine(s1);
        // Find Tony's boss.
        if (s1 == "Tony")
        {
          // In the middle of that iteration, start a new one, using
          // a second iterator, repeated for each outer loop pass.
          MyCollectionIterator mci2 = mc.GetEnumerator();
          foreach (string s2 in mci2)  // Uses the second iterator object
          {
            // Do some useful work with each string.
            if (s2 == "Bob")
            {
              Console.WriteLine("	{0} is {1}'s boss", s2, s1);
            }
          }
        }
      }
      // Wait for user to acknowledge the results.
      Console.WriteLine("Press Enter to terminate...");
      Console.Read();
    }
    // A simple collection of strings
    public class MyCollection
    {
      // Implement collection with an old-fashioned ArrayList.
      // Internal, so separate iterator object can access the strings.
      internal ArrayList _list = new ArrayList();
      public MyCollection(string[] strs)
      {
        foreach (string s in strs)
        {
          _list.Add(s);
        }
      }
      // GetEnumerator -- As in LinkedList, returns one of your
      //    iterator objects.
      public MyCollectionIterator GetEnumerator()
      {
        return new MyCollectionIterator(this);
      }
    }
    // MyCollectionIterator -- The iterator class for MyCollection
    //    (MyCollection is in a separate file.)
    public class MyCollectionIterator
    {
      // Store a reference to the collection.
      private MyCollection _mc;
      public MyCollectionIterator(MyCollection mc)
      {
        this._mc = mc;
      }

// GetEnumerator -- This is the iterator block, which carries
      //    out the actual iteration for the iterator object.
      public System.Collections.IEnumerator GetEnumerator()
      {
        // Iterate the associated collection's underlying list,
        // which is accessible because it's declared internal.
        foreach (string s in _mc._list)
        {
          yield return s;   // The iterator block's heart
        }
      }
    }
  }
}

// GetEnumerator -- As in LinkedList, returns one of your
//    iterator objects.
public MyCollectionIterator GetEnumerator()
{
  return new MyCollectionIterator(this);
}

// GetEnumerator -- This is the iterator block, which carries
//    out the actual iteration for the iterator object.
public System.Collections.IEnumerator GetEnumerator()
{
  // Iterate the associated collection's underlying list,
  // which is accessible because it's declared internal.
  foreach (string s in mc.list)
  {
    yield return s;   // The iterator block's heart
  }
}

Joe
Bob
Tony
        Bob is Tony's boss
Fred

MyCollectionIterator mci1 = mc.GetEnumerator();
foreach (string s1 in mci1)  // Uses the first iterator block
{
  // Do some useful work with each string.
  Console.WriteLine(s1);
  // Find Tony's boss.
  if(s1 == "Tony")
  {
    // In the middle of that iteration, start a new one, using
    // a second iterator; this is repeated for each outer loop pass.
    MyCollectionIterator mci2 = mc.GetEnumerator();
    foreach (string s2 in mci2)  // Uses the second iterator block
    {
      // Do some useful work with each string.
      if(s2 == "Bob")
      {
        Console.WriteLine("	{0} is {1}'s boss", s2, s1);
      }
    }
  }
}