C#: Is a SortedDictionary sorted when you enumerate over it?

Question

A SorteDictionary is according to MSDN sorted on the key. Does that mean that you can be sure that it will be sorted when you enumerate it in a foreach? Or does it just mean that the SortedDictionary works that way internally to have better performance in various cases?

Answer 1

From MSDN:

The dictionary is maintained in a sorted order using an internal tree. Every new element is positioned at the correct sort position, and the tree is adjusted to maintain the sort order whenever an element is removed. While enumerating, the sort order is maintained.

Answer 2

When you enumerate the collection it is sorted by keys (even if you enumerate say the Values collection). Internally the collection is implemented as a binary search tree (according to the documentation). Both insertion and lookup of values are O(log n) (meaning they are pretty efficient).

Answer 3

If you enumerate the items in a SortedDictionary, the items will be returned in the sort order of the item keys. And if you enumerate by the keys in the SortedDictionary, the keys will also be returned in sorted order. And perhaps somewhat surprisingly, if you enumerate the SortedDictionary by its values, the values are returned in the sort order of the keys, not the sort order of the values as you might expect.

Demonstration:

Note that in this demo the items added to the SortedDictionary are not added in sorted order.

Also, if you plan to enumerate your dictionary by its values and there is a possibility of duplicate values, consider having your reverse lookup function return an IEnumerable<T>. (Of course, for large dictionaries, looking up a key by its value may result in poor performance.)

using System;
using System.Collections.Generic;
using System.Linq;

class SortedDictionaryEnumerationDemo
{
    static void Main()
    {
        var dict = new SortedDictionary<int, string>();
        dict.Add(4, "Four");
        dict.Add(5, "Five");
        dict.Add(1, "One");
        dict.Add(3, "Three");
        dict.Add(2, "Two");

        Console.WriteLine("== Enumerating Items ==");
        foreach (var item in dict)
        {
            Console.WriteLine("{0} => {1}", item.Key, item.Value);
        }

        Console.WriteLine("\n== Enumerating Keys ==");
        foreach (int key in dict.Keys)
        {
            Console.WriteLine("{0} => {1}", key, dict[key]);
        }

        Console.WriteLine("\n== Enumerating Values ==");
        foreach (string value in dict.Values)
        {
            Console.WriteLine("{0} => {1}", value, GetKeyFromValue(dict, value));
        }
    }

    static int GetKeyFromValue(SortedDictionary<int, string> dict, string value)
    {
        // Use LINQ to do a reverse dictionary lookup.
        try
        {
            return
                (from item in dict
                 where item.Value.Equals(value)
                 select item.Key).First();
        }
        catch (InvalidOperationException e)
        {
            return -1;
        }
    }
}

Expected Output:

== Enumerating Items ==
1 => One
2 => Two
3 => Three
4 => Four
5 => Five

== Enumerating Keys ==
1 => One
2 => Two
3 => Three
4 => Four
5 => Five

== Enumerating Values ==
One => 1
Two => 2
Three => 3
Four => 4
Five => 5