How to insert as first element in dictionary?

Question

I have a dictionary structure, with multiple key value pairs inside.

myDict.Add(key1, value1);
myDict.Add(key2, value2);
myDict.Add(key3, value3);

My dictionary is used as a data source for some control. In the control's dropdown I see the items are like this:

key1
key2
key3

The order looks identical to my dictionary. I know Dictionary is not like arrayList - you can get the index or so. I cannot use sortedDictionary. Now I need to add one more key value pair to this dictionary at some point of my program and I hope it has the same effect as I do this:

myDict.Add(newKey, newValue);
myDict.Add(key1, value1);
myDict.Add(key2, value2);
myDict.Add(key3, value3);

If I do this, I know newKey will display in my control as first element.

I have an idea to create a tempDict, put each pair in myDict to tempDict, then clear myDict, then add pairs back like this:

myDict.Add(newKey, newValue);
myDict.Add(key1, value1);
myDict.Add(key2, value2);
myDict.Add(key3, value3);

Is there better way than this?

Thanks!

Answer 1

Dictionary<K,V> does not have an ordering. Any perceived order maintenance is by chance (and an artifact of a particular implementation including, but not limited to, bucket selection order and count).

These are the approaches (just using the Base Class Libraries BCL) I know about:

1. Lookup<K,V>
   • .NET4, immutable, can map keys to multiple values (watch for duplicates during building)
2. OrderedDictionary
   • Old, non-generic, expected Dictionary performance bounds (other two approaches are O(n) for "get(key)/set(key)")
3. List<KeyValuePair<K,V>>
   • .NET2/3 okay, mutable, more legwork, can map keys to multiple values (watch for duplicates in inserts)

Happy coding.

---

Creating a hash data-structure that maintains insertion order is actually only a slight modification of a standard hash implementation (Ruby hashes now maintain insertion order); however, this was not done in .NET nor, more importantly, is it part of the Dictionary/IDictionary contract.

Answer 2

You cannot do that with the Dictionary class. It is working in your example because of a quirk in the way the data structure is implemented. The data structure actually stores the entries in temporal order in one array and then uses another array to index into the entry array. Enumerations are based on the entry array. That is why it appears to be ordered in your case. But, if you apply a series of removal and insertion operations you will notice this ordering gets perturbed.

Use KeyCollection instead. It provides O(1) retrieval by both key and index and preserves temporal ordering.

Answer 3

From the MSDN page on Dictionary(TKey, TValue):

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

I'm assuming you can't use SortedDictionary because the control depends on your data source being a Dictionary. If the control expects both the Dictionary type and sorted data, the control needs to be modified, because those two criteria contradict each other. You must use a different datatype if you need sorting/ordering functionality. Depending on undefined behavior is asking for trouble.

Answer 4

Don't use a dictionary - there is no guarantee the order of the keys won't change when you add further elements. Instead, define a class Pair for your Key-Value-Pairs (look here What is C# analog of C++ std::pair? for an example) and use a List<Pair> for your datasource. The List has an Insert operation you can use to insert new elements anywhere into your list.

Answer 5

Dictionary Should not be used to sort objects, it should rather be used to look up objects. i would suggest something else if you want to have it sort the objects too.

If you expand the Dictionary, there are no rule that would stop it from mixing up your List.