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

Pm

Interesting question, MoveNext() would kinda seem an oxymoron for a reverse enumerator though I guess for compatibility with foreach the GetReverseEnumerator() method would actually still have to return a IEnumerator and thus would require that method even if MovePrevious() would seem more appropriate to my mind – Correlate

There's the Reverse linq extension method which achieves something similar... – Bourges

On types that implement IList<T> we get an efficient Reverse from linq. Unfortunately not every type that can implement Reverse efficiently, can also implement IList<T>. For example a doubly linked list. So I agree, that those collections having a built in Reverse() method, would be nice. – Affiant

@RobV, MoveNext() would have a similar concept as C++'s increment operator++ as if you iterate from rbegin() to rend(). I wasn't thinking about compatibility with foreach .. that would be just too confusing. Maybe have another foreachreverse construct instead – Pm

@RQDQ, doesn't linq's Reverse actually buffer the results of the Enumerator and then enumerate backwards, thus using up more space and looping twice? – Pm

@CodeInChaos, actually no, Enumerable.Reverse() creates a copy of the whole sequence, even for IList<T>. See Jon Skeet's blog. – Shanna

@svick, the mentioned blog post has moved, it's now here. – Hach

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.

Attendance

Is it not called File.ReadLines ? – Footboard

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;
        }
    }

Tael

Thanks Hans, Great code! If you want you can update your code with the recent: IReadOnlyList. – Tiling

Answer 3

The clue is in the OP's final line: using this on Lists and LinkedLists.

So, for a List, this one would work nicely:

    public static IEnumerable<T> AsReverseEnumerator<T>(this IReadOnlyList<T> list)
    {
        for (int i = list.Count; --i >= 0;) yield return list[i];
    }

Using IReadOnlyList give a lot of flexibility in terms of what it will work on.

Something similar would be possible for LinkedLists.

Roede

Answer 4

The question concerns an enumerator, not an enumeration. If you must return an IEnumerator (e.g. when binding to a custom datasource object in wpf / uwp / winui), you can do it like this:

var reverseList = myList.AsEnumerable().Reverse().ToList();

return reverseList.GetEnumerator()

Ugly, convoluted and working, i.e. fully adhering to Framework Guidelines.

Administrate

Answer 5

Yes, you can do it easily.

Just use Stack<T>

Like

Stack<int> stack = new Stack<int>(collection);
IEnumerator<int> enumerator = stack.GetEnumerator();
while (enumerator.MoveNext())
{
    //Do stuff
}

Reider