LINQ – the order of elements when using Where()

Last week I was asked if the order of elements found using a where clause was guaranteed to be the same as the order of the original collection. That question is hard to answer.

In the normal case (where nobody has overwritten any framework methods or any such thing) the answer in practise is yes, the order will be the same, because Where(), simply enumerates over the collection one element at a time, and if the elements parses the condition it is returned. This small test program demonstrates it – I have used a SortedDictionary, because it makes it easy to see the order.

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
 class Program
 {
  static void Main(string[] args)
  {
   var sd = new SortedDictionary<string, string="">() { { "b", "test1" }, { "a", "test2" }, { "c", "test3" } };
   Console.WriteLine("The dictionay");
   foreach (var kv in sd)
   {
    Console.WriteLine(kv.Key + " - " + kv.Value);
   }
   Console.WriteLine("the dictionary where Key != b");
   foreach (var kv in sd.Where(x => x.Key != "b"))
   {
    Console.WriteLine(kv.Key + " - " + kv.Value);
   }
   Console.ReadKey();
  }
 }
}

And the output is as expected:

The dictionay
a – test2
b – test1
c – test3
the dictionary where Key != b
a – test2
c – test3

Does that mean that we can conclude that the order of elements returned from Where() will be the same as in the original collection? In the current version of the framework it will. In the general case the Where method is implemented like this:

public static IEnumerable Where(this IEnumerable source, Func<tsource, bool=""> predicate) {
 return new WhereEnumerableIterator(source, predicate);
}

In the real code there are special implementations for List<T>, arrays Iterator<T>. But here we look at the general case. In the WhereEnumerableIterator the main part of the MoveNext method is implemented like this:

while (enumerator.MoveNext()) {
 TSource item = enumerator.Current;
 if (predicate(item)) {
  current = item;
  return true;
 }
}

(enumerator is initialized with source.GetEnumerator())

So we see the order of the original collection must be preserved.

It should be noted, however, that nowhere in the documentation for Where() is it guaranteed to preserve the order. It is only stated that Where() will return an IEnumerable<T> containing the elements that satisfies the condition.

This means it probably isn’t safe to rely on the ordering in the future.

Further somebody might come by and try to make your foreach loop faster by adding an AsParallel() – and that will certainly ruin the order, so if order is important it might be better to add an OrderBy() – that will make it clear that order is important. (or insert a comment to the same effect).

A funny side note: In the documentation for Parallel LINQ it is stated that: 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. See http://msdn.microsoft.com/en-us/library/dd460677.aspx – so it is sort of documented that order is preserved – just not in the LINQ Where() documentation. The question is if this is good enough to guarantee that order is really preserved in the future also. (maybe I just haven’t found the place in the documentation for LINQ where it says order is preserved…)

Advertisements

About Lund

Owner of iCodeIT, a software consulting company. I am primarily working the .NET development and architecture.
This entry was posted in C#, Linq and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s