Are elements in a .NET's Dictionary sequential?

Question

Say, if I create a dictionary like this:

Dictionary<string, MyClass> dic = new Dictionary<string, MyClass>();

dic.add("z1", val1);
dic.add("abc9", val2);
dic.add("abc8", val3);
dic.add("ABC1", val4);

So when I do:

foreach (KeyValuePair<string, MyClass> kvp in dic)
{
}

Am I guaranteed to have these values retrieved as such: "z1", "abc9", "abc8", "ABC1"?

And what if I first do this, will it be: "z1", "abc8", "ABC1"?

dic.Remove("abc9");

`Am I guaranteed to have these values retrieved as such: "z1", "abc9", "abc8", "ABC1"?` **NO** — I4V, Sep 26 '13 at 21:05
Nope, though potentially confusing since dictionaries IRL are alphabetically of course :) — Kieren Johnstone, Sep 26 '13 at 21:13
Trying it doesn't provide an answer to wether or not the feature is formally supported (and thus will remain supported in the future). Considering todays implementation can only falsify, not verify. — Tormod, Sep 26 '13 at 21:30

score 6 · Answer 1 · answered Sep 26 '13 at 21:06

No. From MSDN (emphasis mine)

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey, TValue> structure representing a value and its key. The order in which the items are returned is undefined.

You may want to look at the OrderedDictionary class if you want more control over the iteration order.

score 5 · Accepted Answer · edited May 23 '17 at 10:25

5

The short answer is No. Order is not guaranteed in a Dictionary<TKey, TValue>, nor should you count on order being maintained.

You might want to check into OrderedDictionary instead.

Example:

OrderedDictionary d = new OrderedDictionary();

d.Add("01", "First");
d.Add("02", "Second");
d.Add("03", "Third");
d.Add("04", "Fourth");
d.Add("05", "Fifth");

for(int i = 0; i < d.Count; i++) // Print values in order
{
   Console.WriteLine(d[i]);
}

Note there's no generic OrderedDictionary<TKey,TValue> version for some odd reason. However, this question has some hints on how to implement one.

edited May 23 '17 at 10:25

Community

1
1

answered Sep 26 '13 at 21:05

Mike Christensen

88,082
50
208
326

Thanks. It's good that I asked first. `OrderedDictionary` seems like what I need. So what you're saying, is that if I replace `Dictionary` with `OrderedDictionary` in my code above, my assumption would hold true, yes? – ahmd0 Sep 26 '13 at 21:08
@ahmd0 - Correct, however there doesn't *appear* to be a generic version of `OrderedDictionary` for some reason, so you'd have to cast each value when you access them. – Mike Christensen Sep 26 '13 at 21:13
No, it is not the same. Just verified it. The `foreach` loop like I showed above compiles but then crashes with `OrderedDictionary` instead of `Dictionary`. It must be changed to `foreach (DictionaryEntry de in dic){}`. Also those casts, like you pointed out, are quite annoying... – ahmd0 Sep 26 '13 at 21:37
@ahmd0 - Yea, maybe best to write your own implementation. Or, Jon Skeet's suggestion of having a `Dictionary<>` plus a `List<>` to track order. – Mike Christensen Sep 26 '13 at 21:42

score 1 · Answer 3 · answered Sep 26 '13 at 21:05

1

Am I guaranteed to have these values retrieved as such: "z1", "abc9", "abc8", "ABC1"?

Absolutely not. Always treat Dictionary<,> as an unordered collection of key/value pairs. Even though as an implementation detail you'll generally see them in insertion order if you only ever add values, you should not rely on this.

From the documentation:

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey, TValue> structure representing a value and its key. The order in which the items are returned is undefined.

(Emphasis mine.)

If you need a particular order, you should use a different collection - potentially in conjunction with a dictionary, if you also need to be able to fetch by key. (It's not entirely uncommon to maintain an IList<TKey> as well as a Dictionary<TKey, TValue> for example.)

answered Sep 26 '13 at 21:05

Jon Skeet

1,421,763
867
9,128
9,194

Jon; if you never remove or manipulate the Dictionary, only add items, the underlying implementation seems to suggest they would be in order since it is an an array of entries. Would that be correct? I've gone over this question previously and haven't been able to break this premise! – Allan Elder Sep 26 '13 at 21:20
2

@AllanElder: Yes, that's what the *current* implementation does. But you should never rely on that. – Jon Skeet Sep 26 '13 at 21:21
1

@AllanElder - Many of bugs have been the result of *assuming* a behavior will never change. If sort order is not guaranteed, sort order is not guaranteed. For all we know, .NET 6.0 or .NET 12.0 might completely rewrite `Dictionary<>` causing incompatibilities with poorly written code years down the road. By that time, the original authors are probably long gone, leaving some poor guy to clean up the mess (yes, I've been that poor guy). – Mike Christensen Sep 26 '13 at 21:26
@MikeChristensen: While some people may think .NET already has too many collections, I would have like to have seen .NET include more "add-only" collections, since such collections can often--for minimal added cost--offer guarantees that would be expensive in collections that allowed more varied mutations. For example, maintaining insertion order in a dictionary where nothing is ever deleted is cheap; maintaining it in the presence of deletions is not. Thread-safety is also much cheaper in add-only collections than in collections which allow other mutations. – supercat Dec 11 '13 at 18:04

score 0 · Answer 4 · answered Sep 26 '13 at 21:05

0

No, there is no guarantee of elements order. Also, it can be different depending on actual implementation of IDictionary<...> interface.

answered Sep 26 '13 at 21:05

Display Name

8,022
3
31
66

Are elements in a .NET's Dictionary sequential?

4 Answers4