Does Enumerable.Where in LINQ-to-objects preserve order?

Question

var source = new List<string> { "A1", "A2", "B1", "B2" };
var filtered = source.Where(s => s.StartsWith("A"));

foreach (var s in filtered)
    Console.WriteLine(s);    // outputs first A1 and then A2

It seems like Enumerable.Where keeps the original order of elements when used on an ordered IEnumerable (such as a List<T> or T[]). Is this always the case? If yes, where is this documented?

Answer 1

Microsoft does actually document that LINQ to Objects preserves ordering. The document http://msdn.microsoft.com/en-us/library/dd460677%28v=vs.110%29.aspx says

In PLINQ, the goal is to maximize performance while maintaining correctness. A query should run as fast as possible but still produce the correct results. In some cases, correctness requires the order of the source sequence to be preserved; however, ordering can be computationally expensive. Therefore, by default, PLINQ does not preserve the order of the source sequence. In this regard, PLINQ resembles LINQ to SQL, but is unlike LINQ to Objects, which does preserve ordering.

As mentioned in this stackoverflow article microsoft documents for some LINQ methods that they do not preserve order. For example the documentation of distinct mentions that this method returns an unordered sequence.

Answer 2

The order is preserved using the Enumerable.Where method.

There was a similar question asked on SO, and the first answer breaks down which methods preserve the order:

Preserving order with LINQ

Answer 3

It's not documented. Documentation of the LINQ operators is seriously lacking in many aspects, including when and when isn't order kept, when and when isn't the operation buffered, or what are the complexity guarantees.

In this case, I don't mind depending on the implementation keeping the order, because that's what all practical implementations will do.

I recommend reading the Edulinq series by Jon Skeet where, before implementing the functionality, he explain what you should and what you should not expected of an operator.

Answer 4

Enumerable.Where will preserve the order of an IEnumerable<T>. This is not documented, so not a guarantee, however, the implementation just iterates through the IEnumerable<T> sequentially - in effect, preserving order - though that order is reliant on the underlying IEnumerable<T>'s order. (For example, Where on a HashSet<T> is not ordered, but it's because the HashSet<T>'s enumerable is unordered.)

It does, however, include special implementations to handle certain types (such as arrays and List<T>), so it's not impossible that a specific collection type, at some point in the future, might return results in a different order if this would be deemed a valuable improvement in terms of speed/perf./etc. The documentation never specifically gives an ordering guarantee.

Answer 5

The Where implementation is essentially as follows with some additional variable checking added in:

public static IEnumerable<T> Where(this IEnumerable<T> source, Funct<T, bool> predicate)
{
   foreach (T item in source)
       if (predicate(item))
           yield return item;
}

As a result, assuming yield is not being done asynchronously or in parallel, it will retain the order. If your source is .AsParallel, all bets are off in terms of the order.

Answer 6

The decompilation of the LINQ where is:

private static IEnumerable<TSource> WhereIterator<TSource>(IEnumerable<TSource> source, Func<TSource, int, bool> predicate)
{
    int num = -1;
    IEnumerator<TSource> getenumerator = source.GetEnumerator();
    while (getenumerator.MoveNext())
    {
        TSource current = getenumerator.Current;
        num++;
        if (predicate(current, num))
        {
            yield return current;
        }
    }
}

The decompilation of the System.Collections.Generic.List.MoveNext() has the code:

if (this.version == ts._version && this.index < ts._size)
{
    this.current = ts._items[this.index];
    this.index = this.index + 1;
    return true;
}

Using these two together you can see that the the order will be preserved. Of course Microsoft could change it in the future, but based on .NET 4.0, List.Where will be ordered.

Answer 7

It seems that it must preserve order, because it is able to function on infinite IEnumerables.

void Main() {
    foreach (var element in Count().Where (i => i%2 == 1)) {
        // do something with all odd numbers
    }
}

IEnumerable<int> Count() {
    int i = 0;
    while (true) yield return ++i;
}

I can't find this documented anywhere though.

Answer 8

Yes, it's going to be ordered according to the iterator. Since this isnt PLINQ, the enumerable is iterated over in order of element position of the enumerable - so if you implemented some kind of custom IEnumerator for your class, it would return in that ordering.

Answer 9

Enumerable.Where follows the ordering of elements returned by the enumerator generated by calling GetEnumerator on the underlying collection - looking at MSDN the enumerator on List<T> is documented to follow the indexing behaviour.

Answer 10

Without providing explicit OrderBy, the Where method cannot guarantee the order - otherwise, it would have been documented as doing such.