Generic Key/Value pair collection in that preserves insertion order?

Question

I'm looking for something like a Dictionary<K,V> however with a guarantee that it preserves insertion order. Since Dictionary is a hashtable, I do not think it does.

Is there a generic collection for this, or do I need to use one of the old .NET 1.1 collections?

Answer 1

Well, you could use a List<KeyValuePair<K,V>>, which would preserve the order... however you would lose the lookup functionality of the dictionary. Why do you need the order to be preserved ?

Answer 2

System.Collections.Specialized.OrderedDictionary

Answer 3

There is an OrderedDictionary class that is a dictionary but can be indexed in insertion order, but it is not generified. There is not a generified one in the .Net framework at present.

I have read a comment somewhere from someone on the .Net team that said that they may implement a generified version in the future, but if so it would most likely be called IndexableDictionary instead of OrderedDictionary to make its behaviour more obvious.

EDIT: found the quote. It was on the MSDN page for OrderedDictionary, attributed to David M. Kean from Microsoft:

This type is actually misnamed; it is not an 'ordered' dictionary as such, but rather an 'indexed' dictionary. Although, today there is no equivalent generic version of this type, if we add one in the future it is likely that we will name such as type 'IndexedDictionary'.

Answer 4

There is a generic implementation on code project which comes with a reasonable amount of test cases.

The author chose a rather funny name (KeyedList) which makes it pretty hard to find.

Answer 5

I know you're writing C#, but Java has a class called LinkedHashMap that uses a private LinkedList to maintain the order of insertion of keys. If you can't find a suitable generic solution, perhaps that would be a start on implementing your own.