Who's on Dictionary<>.First() ?

Question

What is the meaning of the .NET 3.5 extension method Enumerable.First() when you call it on an instance of the Dictionary collection?

Does the set of keys determine which item is first, or is it just not defined?

Answer 1

Well, I believe the set of keys will determine which item is first, but not in a well-defined (or easy to predict) way. In other words, don't assume that it will always work the same way - it's as unsafe as relying on a hash code implementation staying the same between runs.

EDIT: I believe that in fact, the ordering of insertion does matter, contrary to my previous ideas. However, this is implementation-specific (so could easily change in the next version). I believe that with the current implementation, the first entry added will be the first one returned if it hasn't been removed. If the first entry added is ever removed, the ordering is broken - it's not that the earliest entry is removed. Here's an example:

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        var dict = new Dictionary<int, int>();        
        dict.Add(0, 0);
        dict.Add(1, 1);
        dict.Add(2, 2);
        dict.Remove(0);
        dict.Add(10, 10);

        foreach (var entry in dict)
        {
            Console.WriteLine(entry.Key);
        }
        Console.WriteLine("First key: " + dict.First().Key);
    }
}

The results are 10, 1, 2, and "First key: 10" - showing that the latest added entry ends up being returned first.

However, I'd like to stress again that everything can change between versions of the framework.

Answer 2

If you need the first item in a dictionary, you're best using a SortedDictionary. I would think the First() method will just return the first item which happens to be at the top, but not necessarily the first one that was added.

Answer 3

I was looking at some code that used a foreach loop to get the "first" item in a dictionary object. The code assumes that this is the first one added to the dictionary.

Initially I thought the Dictionary.First() method would be more efficient. But then I realized that the whole notion of what item is first might not make much sense in this context.

The SortedDictionary, which Echilon suggested, probably has more overhead and way more functionality than I need. I am leaning toward just save the key of the first element added.

Answer 4

I did some more digging and found that MSDN warns that the order of values and keys in a Dictionary is unspecified. So I believe that means that First() may not always return the same value as you add more values.

Answer 5

The ordering of the Keys collection in a class implementing Dictionary<TKey, TValue> is not specified. So you don't know what value First() is going to return.

But there's a reason to use First() anyway - or, more specifically, to use FirstOrDefault(). If you have a method that takes an IEnumerable<T> argument, and you know T is a type whose default value is null, your method can use FirstOrDefault()` to test the object to see if it's empty.

Why would you do this instead of using Count()? To take advantage of deferred execution. If you call FirstOrDefault() on a generator, the generator yields one result and stops. If you call Count() on a generator, the generator has to enumerate to the end of the list.

So you can write a function like this:

bool ListIsEmpty(IEnumerable<string> list)
{
    return list.FirstOrDefault() == null;
}

and use it like this:

if (!ListIsEmpty(dict.Keys)) 
{
    Console.WriteLine("Dictionary is not empty");
}
if (!ListIsEmpty(dict.Keys.Where(x => x.Contains("foo"))
{
    Console.WriteLine("Dictionary has at least one key containing 'foo'.");
}

and know that the code is doing the bare minimum that it has to do in order to make those decisions.

Edit:

I should point out that another assumption the code above is making: that the IEnumerable<T> doesn't have a null as its first item!

This is always guaranteed for the Keys collection of a dictionary, or a DataRowCollection (my primary use case for LINQ), or for Where() when run on one of those collections.

But it's not guaranteed for a List<string> or a List<DataRow>. So there are definitely circumstances in which you'd want to think twice before using FirstOrDefault().