C# Iterator Pattern demystified

Introduction

This is an alternative to the How to use the IEnumerable/IEnumerator interfaces[^]. The aim of this alternative tip is to give more relevant information to the beginner as well as why the heck one should bother about iterators at all.

Covered topics are:

• Iterator Pattern in C#
• What is an iterator?
• My first iterator
• What is IEnumerable/IEnumerable<T> for?
• What else can I do with iterators?
• That's all folks! (AKA Summary)
• Where to go from here...?

Lets start with that: why to bother what the iterator pattern is? You use the iterator pattern most likely in your every day work maybe without being aware of:

List<string> all = new List<string>() { "you", "me", "everyone" };
...
foreach(string who in all)
{
   Console.WriteLine("who: {0}!", who);
}

The iterator tells the foreach loop in what sequence you get the elements.

Iterator Pattern in C#

Note: Some classes may also provide the non-generic IEnumerator GetEnumerator() { ... } method. This is from the older days where there were no generics yet, e.g. all non-generic collections like Array, etc. provide only that "old-fashioned" iterator function.

Behind the scenes, the foreach loop

foreach(string who in all) { ... }

translates into:

using (var it = all.GetEnumerator())
while (it.MoveNext())
{
    string who = it.Current;
    ...
}

var it = all.GetEnumerator();
while (it.MoveNext())
{
    string who = (string)it.Current;
    ...
}

Bonus: the two explicit iterator calls can be combined into one:

var it = all.GetEnumerator();
using(it as IDisposable)
while (it.MoveNext())
{
    string who = (string)it.Current;
    ...
}

Ah yes, you now appreciate the foreach loop! It takes away the burden of writing this bunch of explicit iterator code. Please note: you can write in any one of the above forms, but for sure, you will use the foreach loop whenever possible, right?

So, the core of the C# implementation of the Iterator Pattern is the GetEnumerator() method. What are now these IEnumerator/IEnumerator<T> interfaces?

What is an iterator

An iterator provides a means to iterate (i.e. loop) over some items. The sequence of elements is given by the implementations of the IEnumerator/IEnumerator<T> interfaces:

namespace System.Collections
{
    public interface IEnumerator
    {
        object Current { get; }
        bool MoveNext();
        void Reset();
    }
}
namespace System.Collections.Generic
{
    public interface IEnumerator<out T> : IDisposable, IEnumerator
    {
        T Current { get; }
    }
}

The pattern is basically given by MoveNext() and Current. The semantics is that one has to first call MoveNext() to get to the first element. If MoveNext() returns false, then there is no more element. Current returns the current element. You are not supposed to call Current if the preceeding MoveNext() returned false.

The MoveNext() gives the next element in the sequence of elements - what ever that sequence is, e.g. from first to last, or sorted by some criteria, or random, etc.

You know now how to apply the iterator pattern (e.g. in a foreach loop) and that this is possible for all classes that provide the above mentioned GetEnumerator() method (the iterator).

How to write your own Iterator? Read on.

My first Iterator

How to write your own iterator? Nothing easier than that, you would maybe say: implement the IEnumerator<T> interface and return an instance of that class in the GetEnumerator() method.

This would be the "hard way". The easy way is to employ yield return - the C# way to write an iterator.

public class MyData
{
    private string _id;
    private List<string> _data;
    public MyData(string id, params string[] data)
    {
        _id = id;
        _data = new List<string>(data);
    }
    public IEnumerator<string> GetEnumerator()
    {
        yield return _id;
        foreach(string d in _data) yield return d;
    }
}

The key concept of yield return within the GetEnumerator() method is to define the sequence that MoveNext() traverses. Each yield return call represents one step in the sequence with the corresponding Current value.

An equivalent explicit implementation of the Iterator could look like this:

public class MyData
{
    private string _id;
    private List<string> _data;
    public MyData(string id, params string[] data)
    {
        _id = id;
        _data = new List<string>(data);
    }
    public class MyEnumerator: IEnumerator<string>
    {
        private MyData _inst;
        private int _pos;
        internal MyEnumerator(MyData inst) { Reset(); _inst = inst; }
        public string Current
        {
            get
            {
                if (_pos == -1) return _inst._id;
                if (0 <= _pos && _pos < _inst._data.Count()) return _inst._data[_pos];
                return default(string);
            }
        }
        public void Dispose() { }
        object IEnumerator.Current { get { return Current; } }
        public bool MoveNext() { return ++_pos < _inst._data.Count(); }
        public void Reset() { _pos = -2; }
    }

    public IEnumerator<string> GetEnumerator() { return new MyEnumerator(this); }
}

Why would you want to do that explicitly? There is no good reason unless your version of C# does not provide yield as a keyword (that's only true if you work in C# stone age ;-)). The benefit of yield becomes even more obvious, if the sequence is more complex than the ones shown here. I leave that exercise to you to play with iterator sequences...

You know now that you implement your own iterator by taking benefit of the power of yield.

You will see that you hardly ever write your own iterator, though. The reason is the IEnumerable/IEnumerable<T> interfaces and the advent of LINQ.

What is IEnumerable/IEnumerable<T> for?

These interfaces are quite simple:

namespace System.Collections
{
    public interface IEnumerable
    {
        IEnumerator GetEnumerator();
    }
}

namespace System.Collections.Generic
{
    public interface IEnumerable<out T> : IEnumerable
    {
        IEnumerator<T> GetEnumerator();
    }
}

So, easy answer: they provide an iterator (one "old-fashioned", one with generics).

A class that implements one of these interfaces provides an iterator implementation. Furthermore, such an instance can be used wherever one of these interface is needed. Note: it is not required to implement this interface to have an iterator: one can provide its GetEnumerator() method without implementing this interface. But in such a case, one can not pass the class to a method where IEnumerable<T> is to be passed.

E.g. there is a List<T> constructor that takes an IEnumerable<T> to initialize its content from that iterator.

namespace System.Collections.Generic
{
    public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
    {
        ...
        public List(IEnumerable<T> collection);
        ...
    }
}

If you look now at the LINQ extension methods: many of these base on IEnumerable<T>, thus, extending any iterator class by some new function that often return yet another iterator. E.g.

namespace System.Linq
{
    public static class Enumerable
    {
        ...
        public static IEnumerable<TResult> Select<TSource, TResult>(
                                           this IEnumerable<TSource> source,
                                           Func<TSource, TResult> selector);
        ...
        public static IEnumerable<TSource> Where<TSource>(
                                           this IEnumerable<TSource> source,
                                           Func<TSource, bool> predicate);
        ...
    }
}

This is used as:

    List<string> list = ...;
    var query = list.Where(s=>s.Length > 2).Select(s=>s);
    foreach(string s in query)
    {
       ...
    }

And again, the C# language provides an alterantive way to express this (one could say simpler):

    List<string> list = ...;
    var query = from s in list where s.Length > 2 select s;
    foreach(string s in query)
    {
       ...
    }

This is LINQ - Language Integrated Queries: Extension methods that can be expressed in the form from ... in ... where ... select (to show some of the LINQ keywords). Please note that you can always write a LINQ expression as a chain of extension methods as shown above.

So, now you know the benefits of the IEnumerable<T> interfaces and where and how they are used.

What else can I do with iterators?

You can define your own specific iterator on any class. The following

foreach(var item in data) { ... }

uses the GetEnumerator() of the data class.

What can you say about this?

foreach(var item in data.Random(1000)) { ... }

Yes, the expression data.Random(1000) must provide an iterator, i.e. a GetEnumerator() method. This implies that the Method Random(int n) of the data class must return IEnumerable<T> (or its non-generic sibling).

public class MyData
{
   ...
   public IEnumerable<string> Random(int n)
   {
      ...
   }
   ...
}

What is the body of that method? You can use here again the yield keyword to implement the MoveNext()/Current pair of the iterator.

   public IEnumerable<string> Random(int n)
   {
       Random random = new Random(_data.Count);
       while(n-- > 0) yield return _data[random.Next()];
   }

That's all Folks!

• The Iterator Pattern in C# is given by the GetEnumerator() method that returns IEnumerator or its generic sibling (you choose).
• IEnumerable (or its generic sibling) implementation provides an iterator (thus, the GetEnumerator() method).
• Methods and properties that return IEnumerator/IEnumerable or their generic siblings are conveniently implemented by yield return calls.
• Iterators is one basic ingredient to LINQ (the others are delegates in the form of lambda expressions and IQueriable<T>/IQueriable - but this is another story to tell what these are for).
• You most likely don't implement your own iterators since LINQ provides powerful iterator based extension methods (selection, sorting, aggregation, counting, calculating, etc.), but it does not hurt if you have a basic understanding of the iterator concept as it is implemented in C#.

Where to go from here...?

Want to read more about C# Iterators?

I'm a book enthusiast (I buy a book if it has the few crucial pages that are worth it ;-) ).

• Therefore, I can first of all recommend one brilliant book: Kompaktkurs C# 4.0[^]. It is available in German only. Written by Hanspeter Mössenböck[^]. He has a very concise style to describe the core of every C# language feature. What I described about iterator is inspired by his writing. I got most of the kowledge about C# iterators from that book. BTW: He also describes nicely other topics like co- and contra-variance, etc. Simply great!

Online links:

• There are of course articles from Microsoft about iterators and yield, but they are technical and lack the bigger picture view:
  Iterators (C# Programming Guide)[^]
  Using Iterators (C# Programming Guide)[^]
  yield (C# Reference)[^]
• Iterator block implementation details: auto-generated state machines[^] from C# in Depth, Second Edition[^] provides far more details on what is generated out of yield (thank you Matt[^] for this hint[^]!)
• There are plenty of online documents on iterators and yield, but I did not find one that describes the machinery behind the scene as accurate as done in the book mentioned above.
• If you have access to .Net Reflector[^] or IL-Spy[^] you might reverse engineer the structure created by a foreach loop.
• You may see an iterator in action outside the foreach loop: in Invent your own Dynamic LINQ parser[^] you see an iterator used as token sequence. The tokens (strings in this case) are produced by a Regex and provided in an iterator such that one can get one token after the other until there is no token anymore.

More about LINQ?

LINQ is a very broad topic which I did not cover in this tip. The interesting part as concerned here are the provided extension methods. A few links do discover the technical details:

• The LINQ Enumerable Class, Part 1[^] from the MSDN Magazine[^] (thank you Matt[^] for this hint[^]!)
• IEnumerator(Of T) Interface[^] (the iterator)
• IEnumerable(Of T) Interface[^] (also list all extension methods, mainly from the Enumerable class)
• Enumerable Class[^] (contains IEnumerable<T> extension methods)
• Queryable Class[^] (contains IQueryable<T> extension methods)
• delegate (C# Reference)[^] (again Microsoft-like: missing the big picture - very technical)
• Lambda Expressions (C# Programming Guide)[^]

Enjoy discovering the world of iterators and appreciate their power!

Cheers

Andi

History