c# order preserving data structures

Question

Oddly enough, MSDN has no information on the order preserving properties of data structures. So I've been making the assumption that:

• Hashtable and Hashset do not preserve the insertion order (aka the "hash" in there is a giveaway)
• Dictionary and List DO preserve the insertion order.

from this I extrapolate that if I have a Dictionary<double,double> foo that defines a curve, foo.Keys.ToList() and foo.Values.ToList() will give me an ordered list of the scope and domain of that curve without messing about with it?

Answer 1

As @Anton pointed out the Dictionary<TKey,TValue> is an unordered collection. The proper returning of your values is coincidence and will eventually fail. If you need to have an ordered hashtable you should use SortedDictionary<TKey,TValue>

Answer 2

You should NOT expect either the keys or values in a regular Dictionary<TKey,TValue> to be maintained in any order. In a SortedDictionary<TKey,TValue> the keys and values are maintained in order by the value of the key - this is not the same as insertion order.

The only built-in dictionary in the .NET framework that preserves insertion order is System.Collection.Specialized.OrderedDictionary. Unfortunately, this class is not generic - however, it's not terribly hard to write a generic wrapper around it. Keep in mind, when dealing with value types (like int or double) it will result in boxing of the keys/values (generic dictionaries don't impose boxing on value types).

Answer 3

By all means, rely on Dictionary<TKey, TValue> to preserve ordering!

While Dictionary<TKey, TValue> clearly states that enumeration ordering is undefined, we tested that it indeed does preserve insertion ordering (at least as long as you do not remove items from it). If someone can provide a test that disproves it, we would be very interested since our production code relies on it.

You might take the same approach and save yourself some effort and your customer some money.

Sure, Microsoft might change the Dictionary implementation in a future .NET version, but if that happens, your automated test will detect it, and you can replace Dictionary with another container at that time, right?