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

You could create your own generic class (and have it derive from Dictionary<,> or SortedDictionary<,>) and implement your own version of GetEnumerator() in which you can sort the dictionary by key and return the values sorted (or if you use SortedDictionary then it's already sorted).

You could also use a SortedList<,>, which is better and lighter in some occasions, check MSDN to see which best matches your needs.

Answer 3

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.

Answer 4

Topic is a bit old now but I was looking for a collection with the same behaviour (preserve the order in which items were added) AND be able to index the collection on a key. The answer is the abstract class KeyedCollection<>! (in System.Collections.ObjectModel namespace) I ran a simple test with a dictionary and this keyedcollection by adding a bunch of times, remove one from the middle and add the item again. The KeyedCollection adds the new item to the end, the Dictionary placed it in its original position (I guess some sort of hashing going on there)