There doesn't appear to be a generic implementation of OrderedDictionary
(which is in the System.Collections.Specialized
namespace) in .NET 3.5. Is there one that I'm missing?
I've found implementations out there to provide the functionality, but wondered if/why there isn't a generic implementation out-of-the-box and if anyone knows whether it's something in .NET 4.0?
A major conceptual problem with a generic version of
OrderedDictionary
is that users of aOrderedDictionary<TKey,TValue>
would expect expect to be able to index it either numerically using anint
, or by lookup using aTKey
. When the only type of key wasObject
, as was the case with non-genericOrderedDictionary
, the type of argument passed to the indexer would be sufficient to distinguish whether what type of indexing operation should be performed. As it is, though, it's unclear how the indexer of anOrderedDictionary<int, TValue>
should behave.If classes like
Drawing.Point
had recommended and followed a rule that piecewise-mutable structures should expose their mutable elements as fields rather than properties, and refrain from using property setters that modifythis
, then anOrderedDictionary<TKey,TValue>
could efficiently expose aByIndex
property that returned anIndexer
struct which held a reference to the dictionary, and had an indexed property whose getter and setter would callGetByIndex
andSetByIndex
upon it. Thus, one could say something likeMyDict.ByIndex[5] += 3;
to add 3 to the 6th element of the dictionary. Unfortunately, for the compiler to accept such a thing, it would be necessary to make theByIndex
property return a new class instance rather than a struct every time it's invoked, eliminating the advantages one would get by avoiding boxing. In vb.net, one could get around that issue by using a named indexed property (soMyDict.ByIndex[int]
would be a member ofMyDict
, rather than requiringMyDict.ByIndex
to be a member ofMyDict
which includes an indexer), but C# doesn't allow such things.It might still have been worthwhile to offer an
OrderedDictionary<TKey,TValue> where TKey:class
, but much of the reason for providing generics in the first place was to allow their use with value types.For a lot of purposes I've found one can get by with a
List<KeyValuePair<K, V>>
. (Not if you need it to extendDictionary
, obviously, and not if you need better than O(n) key-value lookup.)For the record, there is a generic KeyedCollection that allows objects to be indexed by an int and a key. The key must be embeded in the value.
Here's a bizarre find: the System.Web.Util namespace in System.Web.Extensions.dll contains a generic OrderedDictionary
Not sure why MS placed it there instead of the System.Collections.Generic package, but I assume you can simply copy paste the code and use it (it's internal, so can't use it directly). Looks like the implementation uses a standard dictionary and separate Key/Value lists. Pretty straightforward...
For what it's worth, here is how I solved it (edited to improve my first attempt):
It can be initialized like this:
and accessed like this:
There is
SortedDictionary<TKey, TValue>
. Although semantically close, I am not claiming it's the same asOrderedDictionary
simply because they are not. Even from performance characteristics. However the very interesting and quite important difference betweenDictionary<TKey, TValue>
(and to that extentOrderedDictionary
and implementations provided in answers) andSortedDictionary
is that the latter is using binary tree underneath. This is critical distinction because it makes the class immune to memory constraints applied to generic class. See this thread aboutOutOfMemoryExceptions
thrown when generic class is used for handling large set of key-value pairs.How to figure out the max value for capacity parameter passed to Dictionary constructor to avoid OutOfMemoryException?