When SortedDictionary is enumerated does it return KeyValuePairs in expected order?

Question

When I have SortedDictionary<TK, TV> in .NET and I want to enumerate it as ICollection<KeyValuePair<TK, TV>> does it enumerate in expected order?

That is KeyValuePair<TK, TV> with lowest key is returned as first, folloved by KeyValuePair<TK, TV> with second lowest key etc.?

Note: Only answer backed up by reference will be accepted.

Answer 1

From the Reference for GetEnumerator:

"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."

Specifically: "While enumerating, the sort order is maintained."

Answer 2

Yes definitely, although you are going to find it very hard to find documentation that clarifies this precisely.

Although the documentation for each of the four GetEnumerator overloads on this type make vague statements about returning "an enumerator that iterates through a collection", it is obvious enough that they should produce equivalent (sorted by key) sequences; remember that a sorted-dictionary is meant to "represent a collection of key/value pairs that are sorted on the key." It would be highly unintuitive and confusing for users if a collection behaved completely differently (i.e. with a different enumeration order) between a foreach loop and a LINQ to Objects query, for example.

The best I can do is provide you with the implementations of the two GetEnumerator methods you appear to be interested in (as of .NET 4.0). They are identical - they return an instance of the nested Enumerator type, with the same arguments for its constructor. The only difference is the boxing of the struct-type in the second overload:

// Used when you do foreach(var kvp in dict) { ... }

public Enumerator<TKey, TValue> GetEnumerator()
{
    return new Enumerator<TKey, TValue>
                ((SortedDictionary<TKey, TValue>) this, 1);
}

// Used when you do:
// foreach(var kvp in (ICollection<KeyValuePair<TKey, TValue>>)dict) { ... }
// or use LINQ to Objects on the collection.

IEnumerator<KeyValuePair<TKey, TValue>> 
IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
{
    return new Enumerator<TKey, TValue>
                ((SortedDictionary<TKey, TValue>) this, 1);
}

In fact, the only GetEnumerator overload that has a slightly different implementation is the IDictionary.GetEnumerator method. This changes an argument to the constructor-call such that the resulting enumerator produces DictionaryEntry instances rather than KeyValuePair<,> instances. Of course, the enumeration order will still be the same as with the other overloads.