c#: How to Iterate over Dictionaries: Carefully

Don’t be fooled by false ordering!


First I’d like to clarify that the example below is not contrived, it is inspired by code found in actual shipping code.

In the simple example below we add items to a dictionary and then iterate over it.

Dictionary<string, int> d = new Dictionary<string, int>();
d[ "a" ] = 0;
d[ "b" ] = 0;
d[ "c" ] = 0;
string s = "";
foreach (int k in d.Keys )
s += k.ToString();

If you run the example above there is a considerable chance that the “foreach” will visit the keys in order of insertion. Like so:

"abc"

This is not by design, but a side effect of how all major libraries (.net and mono) currently implements “Dictionary”.

The current implementation stores all items in an array and the iteration through the dictionary is done through this array.

The easiest way to “break” this false “order of insertion”-rule is to remove an item (not the last) and inserting a new one such as below

d.Remove( "b");
d[ "d"] = 0;

Now the second item (“b” in the array will have been replaced with the new key, and iterating over the keys would get us this:

"adc"

Again I’d like to re-iterate this is not by design. All of the behavior I point to above is purely an implementation detail, a future c# implementation might actually maintain the order even after the example above.

Do Not Rely on Ordering of Dictionaries

If you need reasons here are some:

  1. The behavior is not communicated. (the engineer expected to maintain this code will see “Dictionary” and trust there is no ordered)
  2. A simple change (remove an item before last insert) will break ordering
  3. If the code is ever moved to another language (c++, objective-C, Java, Javascript) it will immediate break.
  4. A future implementation of c# could break this behavior

Conclusion

Do not rely on order if iteration of dictionaries. Did I say that already?

Show your support

Clapping shows how much you appreciated Tales from the Crypt’s story.