What dotnet collection class's items can be enumerated in "addition order" and retrieved via a key?

Question

I'm lead to believe that I cannot count on the order of items added to a dictionary for enumeration purposes.

Is there a class (generic if possible) to which items may be added with a key and which can be enumerated in addition order or which can be retrieved by key?

Clarification: I do not want to enumerate in Key Order. I want to enumerate in addition order. Which is to say that I want to be able to retrieve the items via enumeration on a FIFO ( first in first out) basis.

Answer 1

You can achieve the effect you want just by using a List that stores the keys in order of addition. Then you can enumerate that list in order, and retrieve the values from the Dictionary.

However, if you want to do all this with a single existing collection type, I'm not aware of a type that does this without you needing to provide a comparer or without the key being part of the item. For the former, you could try SortedDictionary and for the latter, you could derive a new collection from KeyedCollection (not entirely sure that this would maintain the order without a comparer so you'd need to experiment to confirm that).

Answer 2

First, on your primary assumption, you are correct. A normal dictionary makes no guarantees about the order of enumeration.

Second, you'll need to be careful about going the SortedDictionary with custom IComparer route. The comparer is used for key equality as well as sorting the collection. That is, using an IComparer based on the addition order, you may have difficulty retrieving an element from a SortedDictionary by key value, it might end up lost in the tree (which is the backing of a sorted dictionary).

If you're willing to go the C5 Generic Class Library route, you can get some good mileage out of a HashedLinkedList<KeyValuePair<T>> or HashedLinkedList<T> if T is self-keyed. You can create an IEqualityComparer that will operate on the key to generate the hash code. Then retrieving the actual value, you can use Find(ref T x) with a prototype x (perhaps where only the key is set) which will find the stored T and return that by reference in O(1) time vs. O(log n) with a SortedDictionary. As well, being backed by a LinkedList, it is guaranteed to enumerate in addition order (and you can specify which direction you'd prefer through C5's IDirectedEnumerable).

Hope that helps.