How does IEnumerable<T>.Reverse work?

Question

I am checking out the code in the reflector, but I haven't yet found out how it can enumerate through a collection backwards?

Since there is no count information, and enumeration always starts from the "start" of the collection, right?

Is it a drawback in the .NET framework? Is the cost higher than regular enumeration?

Answer 1

In short, it buffers everything and then walks through it backwards. Not efficient, but then, neither is OrderBy from that perspective.

In LINQ-to-Objects, there are buffering operations (Reverse, OrderBy, GroupBy, etc) and non-buffering operations (Where, Take, Skip, etc).

---

As an example of a non-buffering Reverse implementation using IList<T>, consider:

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

Note that this is still a little susceptible to bugs if you mutate the list while iterating it... so don't do that ;-p

Answer 2

It works by copying the underlying IEnumerable<T> to an array, then enumerating over that array backward. If the underlying IEnumerable<T> implements ICollection<T> (like T[], List<T>, etc.), then the copy step is skipped and the enumerator just iterates over the underlying collection directly.

For more information, check out System.Linq.Buffer<TElement> in Reflector.

Edit: The underlying collection is always copied, even if it's an ICollection<TElement>. This prevents changes in the underlying collection from being propagated by the Buffer<TElement>.

Answer 3

it loads all items to memory and then steps through them (backwards). this is far less efficient.