Why is there no ReverseEnumerator in C#?

Question

Does anyone know if there was a specific reason or design decision to not include a reverse enumerator in C#? It would be so nice if there was an equivalent to the C++ reverse_iterator just like Enumerator is the equivalent of the C++ iterator. Collections that can be reverse-iterated would just implement something like IReverseEnumerable and one could do something like:

List<int>.ReverseEnumerator ritr = collection.GetReverseEnumerator();
while(rtir.MoveNext())
{
 // do stuff
}

This way, you would be able to iterate Lists and LinkedLists in the same way rather than using indexer for one and previous links for the other thus achieving better abstraction

Answer 1

It would be entirely possible to implement this. Personally, I almost never reverse-iterate. If I need to do this, I call .Reverse() first. Probably this is what the .NET BCL designers thought as well.

All features are unimplemented by default. They need to be designed, implemented, tested, documented and supported. - Raymond Chen

And this is why you don't implement features that provide little utility. You start with the most important features (like iterating front-to-back). And you stop somewhere where either your budget is depleted or where you think is does not make sense to continue.

There are many things that are not in the .NET base class library. Until .NET 4 there even wasn't a File.EnumerateLines. And I would venture to say that such a functionality is more important than reverse iteration for most people.

It might be the case that you are working in a business domain where reverse iteration is common. My experience is the opposite. As a framework designer you can only guess who will use your framework and what features these people will demand. It is hard to draw the line.

Answer 2

It isn't available because IEnumerator is a forward only iterator. It only has a MoveNext() method. That makes the interface very universal and the core of Linq. There are lots of real world collections that cannot be iterated backwards because that requires storage. Most streams are like that for example.

Linq provides a solution with the Reverse() extension method. It works by storing the elements first, then iterating them backwards. That however can be very wasteful, it requires O(n) storage. It is missing a possible optimization for collections that are already indexable. Which you can fix:

static class Extensions {
    public static IEnumerable<T> ReverseEx<T>(this IEnumerable<T> coll) {
        var quick = coll as IList<T>;
        if (quick == null) {
            foreach (T item in coll.Reverse()) yield return item;
        }
        else {
            for (int ix = quick.Count - 1; ix >= 0; --ix) {
                yield return quick[ix];
            }
        }
    }
}

Sample usage:

        var list = new List<int> { 0, 1, 2, 3 };
        foreach (var item in list.ReverseEx()) {
            Console.WriteLine(item);
        }

You'll want to make a specialization for LinkedList since it doesn't implement IList<T> but still allows quick backwards iteration through the Last and LinkedListNode.Previous properties. Although it is much better to not use that class, it has lousy CPU cache locality. Always favor List<T> when you don't need cheap inserts. It could look like this:

    public static IEnumerable<T> ReverseEx<T>(this LinkedList<T> list) {
        var node = list.Last;
        while (node != null) {
            yield return node.Value;
            node = node.Previous;
        }
    }