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!

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

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.

View more solutions

Comments

[spspli]

but my control need dictionary to feed data source and we don't want to change the control.

[Sam]

@spspli: what the good doctor is saying is you don't get to ignore the basics of Dictionary<K,T>. So either you change your data structure or you live with an unordered collection.

[Doc Brown]

When you want your control to display elements in a specific, list-like order, and the only allowed datasource is a dictionary - which does not provide a specific order - then your control is misdesigned and you cannot expect to find a solution for your problem. So either you change your control, use a different control or find out more about your control if there is an alternative way of getting the ordering information somewhere from outside into it.

[Admin]

+1 Wish I knew about KeyCollection before (but why is it off in the ComponentModel namespace and why does it rely on being extended? :-/)

[phoog]

Does your control need a Dictionary<,> or an IDictionary<,>? If the latter, then you can implement the IDictionary<,> interface around List<Pair> or any other insertion-ordered solution that you like.

[Ben]

+1 KeyedCollection is just what i was looking for!