OrderedDictionary and Dictionary

Question

I was looking for a way to have my Dictionary enumerate its KeyValuePair in the same order that they were added. Now, Dictionary's documentation clearly states that:

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.

I found out that what I needed was an OrderedDictionary, but being the sceptic that I am, I decided to try it myself:

OrderedDictionary od = new OrderedDictionary();
Dictionary<String, String> d = new Dictionary<String, String>();

for (int i = 0; i < 10; i++)
{
    od.Add("key" + i, "value" + i);
    d.Add("key" + i, "value" + i);
}

System.Console.WriteLine("OrderedDictionary");
foreach (DictionaryEntry de in od) {
    System.Console.WriteLine(de.Key + ", " + de.Value);
}

System.Console.WriteLine("Dictionary");
foreach (var tmp in d) {
    System.Console.WriteLine(tmp.Key + ", " + tmp.Value);
}

Output:

OrderedDictionary
key0, value0
key1, value1
key2, value2
...

Dictionary
key0, value0
key1, value1
key2, value2
...

As you can see, both are ordered, and that raise two questions:

In which case does the Dictionary give a different order that the one in which the values are added? Does my first foreach loop assure me to retrieve my KeyValuePair in the same order, or do I have to use the index?

Try to use *random* keys while `Add`ing to collections and see the difference. — I4V, May 22 '13 at 14:20
Only for information: @I4V Tried it, and that doesn't change. — DeadlyJesus, May 22 '13 at 15:02
The important part of the Dictionary documentation is that "[t]he order [...] is undefined", meaning the implementation contains no logic to guarantee order. In other words, just because you observe a given order now doesn't mean you will always observe that same order, so don't rely on it. — Eric, Nov 13 '21 at 21:57

score 79 · Accepted Answer · edited May 11 '19 at 20:08

79

You are doing it wrong. You need not only to insert values sequentially into dictionary, but also remove some elements and see how the order has changed after this. The next code demonstrates this:

OrderedDictionary od = new OrderedDictionary();
Dictionary<String, String> d = new Dictionary<String, String>();
Random r = new Random();

for (int i = 0; i < 10; i++)
{
    od.Add("key" + i, "value" + i);
    d.Add("key" + i, "value" + i);
    if (i % 3 == 0)
    {
        od.Remove("key" + r.Next(d.Count));
        d.Remove("key" + r.Next(d.Count));
    }
}

System.Console.WriteLine("OrderedDictionary");
foreach (DictionaryEntry de in od) {
    System.Console.WriteLine(de.Key + ", " +de.Value);
}

System.Console.WriteLine("Dictionary");
foreach (var tmp in d) {
    System.Console.WriteLine(tmp.Key + ", " + tmp.Value);
}

prints something similar to (OrderedDictionary is always ordered):

OrderedDictionary
key3, value3
key5, value5
key6, value6
key7, value7
key8, value8
key9, value9
Dictionary
key7, value7
key4, value4
key3, value3
key5, value5
key6, value6
key8, value8
key9, value9

edited May 11 '19 at 20:08

Peter Mortensen

30,738
21
105
131

answered May 22 '13 at 14:23

Ilya Ivanov

23,148
4
64
90

What if I only Enumerate the dictionary ? From what I understand they work the same way in that case. – DeadlyJesus May 22 '13 at 14:26
@DeadlyJesus by enumerate you mean inserting values without removing? – Ilya Ivanov May 22 '13 at 14:27
Yes. What I did in my example is more or less what I'm doind in my app, I only add values in the dictionary and never remove/change them afterward. – DeadlyJesus May 22 '13 at 14:28
5

@DeadlyJesus look, after adding new items Dictionary resizes internal data structure by increasing capacity by two. This leads to inserting elements again into array `Dictionary.Entry[] entries;` with new keys. This may lead to changing the order of your items. I will try to show this by example (still haven't figured out how to show this), but if you rely on order I would use `OrderedDictionary` even if you are only inserting values into it. – Ilya Ivanov May 22 '13 at 14:39
23

@DeadlyJesus another important point is that OrderedDictionary **guarantees** that keys are sorted, and Dictionary does not. And as long as their "contract"/definition is fulfilled, nothing prevents C#'s internal implementation of Dictionary to change! So maybe somewhere in the future you change to Mono, or upgrade to C#6.5, or something like that; and suddenly you get unexpected bugs. – ANeves Oct 10 '13 at 11:19
8

@ANeves I am not sure I agree with OrderedDictionary sorts its keys if that's what you mean. OrderedDictionary is by no means a sorted dictionary; it simply maintains the order of items as they are added. – dragonfly02 Mar 29 '15 at 20:09
2

@ANeves that reads better now. I'm surprised that there is still no generic version of OrderedDictionary given it was introduced in .NET2.0... Maybe not enough people claim it's usefulness... – dragonfly02 Mar 31 '15 at 15:53

OrderedDictionary and Dictionary

1 Answers1

Linked

Related