Iterator pattern and foreach statement#

If a sequence type is defined following the standard iterator pattern of object-oriented programming, the objects in the sequence can be pulled by C# foreach statement. Iterator pattern consists of a sequence (also called container of items, or aggregate of elements) and an iterator:

internal abstract class Sequence

1
{

1
public abstract Iterator GetEnumerator(); // Must be public.

1
}

1
internal abstract class Iterator

1
{

1
public abstract bool MoveNext(); // Must be public.

1
public abstract object Current { get; } // Must be public.

}

And their generic version is:

internal abstract class GenericSequence<T>

1
{

1
public abstract GenericIterator<T>GetEnumerator(); // Must be public.

1
}

1
internal abstract class GenericIterator<T>

1
{

1
public abstract bool MoveNext(); // Must be public.

1
public abstract T Current { get; } // Must be public.

}

The above types and members demonstrate the minimum requirements of iterator pattern for foreach statement. The sequence must have a GetEnumerator factory method to output an iterator (It can be virtually read as GetIterator). And iterator must have a MoveNext method to output a bool value to indicate whether there is a value that can be pulled. If the output is true, iterator’s Current property getter can be called to pull that value. Now the values in above non-generic and generic sequences can be access with C# foreach statement:

internal static void ForEach<T>(Sequence sequence, Action<T> process)

1
{

1
foreach (T value in sequence)

1
{

1
process(value);

1
}

1
}

1
internal static void ForEach<T>(GenericSequence<T> sequence, Action<T> process)

1
{

1
foreach (T value in sequence)

1
{

1
process(value);

1
}

}

The foreach statement is declarative syntactic sugar. It is compiled to the following imperative control flow to get iterator from sequence, and poll iterator until there is no value available:

internal static void CompiledForEach<T>(Sequence sequence, Action<T> process)

1
{

1
Iterator iterator = sequence.GetEnumerator();

1
try

1
{

1
while (iterator.MoveNext())

1
{

1
T value = (T)iterator.Current;

1
process(value);

1
}

1
}

1
finally

1
{

1
(iterator as IDisposable)?.Dispose();

1
}

1
}

1
internal static void CompiledForEach<T>(GenericSequence<T> sequence, Action<T> process)

1
{

1
GenericIterator<T>iterator = sequence.GetEnumerator();

1
try

1
{

1
while (iterator.MoveNext())

1
{

1
T value = iterator.Current;

1
process(value);

1
}

1
}

1
finally

1
{

1
(iterator as IDisposable)?.Dispose();

1
}

}

Apparently, the generic version of definition is preferred, because the non-generic iterator’s Current property outputs object type, which has to be explicitly cast to the expected type specified in the foreach statement and could be a chance of failure. To demonstrate the iterator pattern implementation, a sequence of values can be defined as a singly linked list, where each value is stored in a linked list node:

internal class LinkedListNode<T>

1
{

1
internal LinkedListNode(T value, LinkedListNode<T> next = null) =>

1
(this.Value, this.Next) = (value, next);

1
public T Value { get; }

1
public LinkedListNode<T> Next { get; }

}

Then iterator can be implemented to traverse along the linked list nodes. When there is a next node, MoveNext outputs true, and Current can output the next value. Notice the iterator is stateful:

internal class LinkedListIterator<T> : GenericIterator<T>

1
{

1
private LinkedListNode<T> node; // State.

1
internal LinkedListIterator(LinkedListNode<T>head) =>

1
this.node = new LinkedListNode<T>(default, head);

1
public override bool MoveNext()

1
{

1
if (this.node.Next != null)

1
{

1
this.node = this.node.Next; // State change.

1
return true;

1
}

1
return false;

1
}

1
public override T Current => this.node.Value;

}

Finally, the sequence can be simply implemented as an iterator factory:

internal class LinkedListSequence<T> : GenericSequence<T>

1
{

1
private readonly LinkedListNode<T> head;

1
internal LinkedListSequence(LinkedListNode<T> head) => this.head = head;

1
public override GenericIterator<T> GetEnumerator() => new LinkedListIterator<T>(this.head);

}

Now the values in the linked list sequence can be sequentially pulled with the foreach syntactic sugar, which is declarative and there is no need to specify the control flow or handle the state:

internal static void ForEach()

1
{

1
LinkedListNode<int> node3 = new LinkedListNode<int>(3, null);

1
LinkedListNode<int> node2 = new LinkedListNode<int>(2, node3);

1
LinkedListNode<int> node1 = new LinkedListNode<int>(1, node2);

1
LinkedListSequence<int> sequence = new LinkedListSequence<int>(node1);

1
foreach (int value in sequence)

1
{

1
value.WriteLine(); // 1 2 3

1
}

}

A general implementation of iterator pattern is discussed later in the LINQ to Objects query implementation chapter.

IEnumerable and IEnumerator interfaces#

Initially, .NET Framework 1.0 provides IEnumerable and IEnumerator interfaces as the contract of iterator pattern:

namespace System.Collections

1
{

1
public interface IEnumerable // Sequence.

1
{

1
IEnumerator GetEnumerator();

1
}

1
public interface IEnumerator // Iterator.

1
{

1
object Current { get; }

1
bool MoveNext();

1
void Reset(); // For COM interoperability.

1
}

}

They can be virtually read as iteratable sequence and iterator. .NET Framework’s sequence and collection types implement IEnumerable so that they can be used with foreach statement, like array, ArrayList, Queue, Stack, SortedList, etc. Then .NET Framework 2.0 was released with generics support. So IEnumerable and IEnumerator interfaces are provided as the generic version of iterator pattern contract.

namespace System.Collections.Generic

1
{

1
public interface IEnumerable<T> : IEnumerable // Sequence.

1
{

1
IEnumerator<T> GetEnumerator();

1
}

1
public interface IEnumerator<T> : IDisposable, IEnumerator // Iterator.

1
{

1
T Current { get; }

1
}

}

Since .NET Framework 2.0, sequence and collection types are usually provided as generic types, with IEnumerable implemented, like array, List, Queue, Stack, SortedList, etc.

Later, .NET Framework 4.0 introduces covariance and contravariance for generic interface. As discussed in the covariance and contravariance chapter, T is covariant for both IEnumerable and IEnumerable. So, their definitions are updated with the out modifier for type parameter:

namespace System.Collections.Generic

1
{

1
public interface IEnumerable<out T> : IEnumerable // Sequence.

1
{

1
IEnumerator<T> GetEnumerator();

1
}

1
public interface IEnumerator<out T> : IDisposable, IEnumerator // Iterator.

1
{

1
T Current { get; }

1
}

}

This is how they are defined in .NET Standard.

foreach statement vs. for statement#

Array is a special type. A concrete array T[] inherits System.Array type, which does not implement IEnumerable but IEnumerable:

namespace System

1
{

1
public abstract class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable

1
{

1
}

}

Instead, T[] directly implements IEnumerable, ICollection, and IList, as long as T[] is single dimensional and zero–lower bound. So, array T[] can be used with foreach loop:

internal static void ForEach<T>(T[] array, Action<T> process)

1
{

1
foreach (T value in array)

1
{

1
process(value);

1
}

}

foreach statement with array is compiled into a for loop, accessing each value with index, which has better performance than the above control flow of getting iterator and polling its MoveNext method and Current property:

internal static void CompiledForEach<T>(T[] array, Action<T> process)

1
{

1
for (int index = 0; index < array.Length; index++)

1
{

1
T value = array[index];

1
process(value);

1
}

}

And so is string. Since string is a sequence of characters, it implements IEnumerable. Foreach statement with string is also compiled to index access for better performance:

internal static void ForEach(string @string, Action<char> process)

1
{

1
foreach (char value in @string)

1
{

1
process(value);

1
}

1
}

1
internal static void CompiledForEach(string @string, Action<char> action)

1
{

1
for (int index = 0; index < @string.Length; index++)

1
{

1
char value = @string[index];

1
action(value);

1
}

}

LINQ to Objects queryable types#

As discussed, most LINQ to Objects queries are extension methods for IEnumerable. Since most of.NET sequence and collection types implements IEnumerable, LINQ to Object queries are available for these types, and foreach statement is also available for these type to pull results. The following list is the commonly used interfaces and types that implement IEnumerable:

· System.Collections.Generic.IEnumerable

o Microsoft.Collections.Immutable.IImmutableQueue

§ Microsoft.Collections.Immutable.ImmutableQueue

o Microsoft.Collections.Immutable.IImmutableStack

§ Microsoft.Collections.Immutable.ImmutableStack

o Microsoft.Collections.Immutable.IOrderedCollection

§ Microsoft.Collections.Immutable.ImmutableList

o System.Collections.Concurrent.IProducerConsumerCollection

§ System.Collections.Concurrent.ConcurrentBag

§ System.Collections.Concurrent.ConcurrentQueue

§ System.Collections.Concurrent.ConcurrentStack

o System.Collections.Concurrent.BlockingCollection

o System.Collections.Generic.ICollection

§ System.Collections.Generic.IDictionary<TKey, TValue>

§ System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue>

§ System.Collections.Generic.Dictionary<TKey, TValue>

§ System.Collections.ObjectModel.ReadOnlyDictionary<TKey, TValue>

§ System.Dynamic.ExpandoObject

§ System.Collections.Generic.IList

§ System.ArraySegment

§ System.Collections.Generic.List

§ System.Collections.ObjectModel.Collection

§ System.Collections.ObjectModel.ObservableCollection

§ System.Collections.ObjectModel.KeyedCollection<TKey, TItem>

§ System.Collections.ObjectModel.ReadOnlyCollection

§ System.Collections.Generic.ISet

§ System.Collections.Generic.HashSet

§ System.Collections.Generic.SortedSet

o System.Collections.Generic.IReadOnlyCollection

§ System.Collections.Generic.IReadOnlyDictionary<TKey, TValue>

§ System.Collections.Generic.Dictionary<TKey, TValue>

§ System.Collections.ObjectModel.ReadOnlyDictionary<TKey, TValue>

§ Microsoft.Collections.Immutable.IImmutableDictionary<TKey, TValue>

§ Microsoft.Collections.Immutable.ImmutableDictionary<TKey, TValue>

§ Microsoft.Collections.Immutable.ImmutableSortedDictionary<TKey, TValue>

§ System.Collections.Generic.Dictionary<TKey, TValue>

§ System.Collections.ObjectModel.ReadOnlyDictionary<TKey, TValue>

§ System.Collections.Generic.IReadOnlyList

§ Microsoft.Collections.Immutable.IImmutableList

§ Microsoft.Collections.Immutable.ImmutableList

§ System.Collections.Generic.List

§ System.Collections.ObjectModel.Collection

§ System.Collections.ObjectModel.ReadOnlyCollection

§ Microsoft.Collections.Immutable.IImmutableSet

§ Microsoft.Collections.Immutable.IImmutableHashSet

§ Microsoft.Collections.Immutable.ImmutableHashSet

§ Microsoft.Collections.Immutable.IImmutableSortedSet

§ Microsoft.Collections.Immutable.ImmutableSortedSet

o System.Collections.Generic.LinkedList

o System.Collections.Generic.Queue

o System.Collections.Generic.SortedList<TKey, TValue>

o System.Collections.Generic.Stack

o System.Linq.IGrouping<TKey, TElement>

o System.Linq.ILookup<TKey, TElement>

§ System.Linq.Lookup<TKey, TElement>

o System.Linq.IOrderedEnumerable

o System.Linq.ParallelQuery*

§ System.Linq.OrderedParallelQuery

o System.Linq.IQueryable*

§ System.Linq.IOrderedQueryable

§ System.Linq.EnumerableQuery

§ System.Data.Linq.ITable

§ System.Data.Linq.Table

§ Microsoft.EntityFrameworkCore.DbSet

o System.String (implements IEnumerable)

o T[] (array of T)

In the above list, LINQ to Objects queries cannot be directly used for ParallelQuery, IQueryable, and their subtypes. As fore mentioned, ParallelQuery is defined for parallel LINQ, and IQueryable is defined for remote LINQ, LINQ query methods are also defined for them, like Where extension method for ParallelQuery, and Where extension method for IQueryable, etc. When calling Where for IQueryable, apparently the call is compiled to the Where extension method for IQueryable, not the Enumerable.Where extension method for IEnumerable. To use LINQ to Objects’ Enumerable.Where method for ParallelQuery and IQueryable, AsEnumerable query method can be used, which is discussed later in this chapter. ParallelQuery is covered in the Parallel LINQ chapters, and IQueryable is covered in the LINQ to Entities chapters.

For history reason, there are some types may only implement IEnumerable, but not implement IEnumerable. A Cast query method is provided to cast non-generic sequence to generic sequence for further LINQ to Objects query, which is discussed later.