No generic implementation of OrderedDictionary?

Question

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?

Answer 1

A major conceptual problem with a generic version of OrderedDictionary is that users of a OrderedDictionary<TKey,TValue> would expect expect to be able to index it either numerically using an int, or by lookup using a TKey. When the only type of key was Object, as was the case with non-generic OrderedDictionary, 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 an OrderedDictionary<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 modify this, then an OrderedDictionary<TKey,TValue> could efficiently expose a ByIndex property that returned an Indexer struct which held a reference to the dictionary, and had an indexed property whose getter and setter would call GetByIndex and SetByIndex upon it. Thus, one could say something like MyDict.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 the ByIndex 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 (so MyDict.ByIndex[int] would be a member of MyDict, rather than requiring MyDict.ByIndex to be a member of MyDict 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.

Answer 2

For a lot of purposes I've found one can get by with a List<KeyValuePair<K, V>>. (Not if you need it to extend Dictionary, obviously, and not if you need better than O(n) key-value lookup.)

Answer 3

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.

Answer 4

Here's a bizarre find: the System.Web.Util namespace in System.Web.Extensions.dll contains a generic OrderedDictionary

// Type: System.Web.Util.OrderedDictionary`2
// Assembly: System.Web.Extensions, Version=4.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35
// Assembly location: C:\Windows\Microsoft.NET\Framework\v4.0.30319\System.Web.Extensions.dll

namespace System.Web.Util
{
    internal class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable

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...

Answer 5

For what it's worth, here is how I solved it (edited to improve my first attempt):

   public class PairList<TKey, TValue> : List<KeyValuePair<TKey, TValue>> {
        Dictionary<TKey, int> itsIndex = new Dictionary<TKey, int>();

        public void Add(TKey key, TValue value) {
            Add(new KeyValuePair<TKey, TValue>(key, value));
            itsIndex.Add(key, Count-1);
        }

        public TValue Get(TKey key) {
            var idx = itsIndex[key];
            return this[idx].Value;
        }
    }

It can be initialized like this:

var pairList = new PairList<string, string>
    {
        { "pitcher", "Ken" },
        { "catcher", "Brad"},
        { "left fielder", "Stan"},
    };

and accessed like this:

foreach (var pair in pairList)
{
    Console.WriteLine("position: {0}, player: {1}",
        pair.Key, pair.Value);            
}

// guaranteed to print in the order of initialization

Answer 6

There is SortedDictionary<TKey, TValue>. Although semantically close, I am not claiming it's the same as OrderedDictionary simply because they are not. Even from performance characteristics. However the very interesting and quite important difference between Dictionary<TKey, TValue> (and to that extent OrderedDictionary and implementations provided in answers) and SortedDictionary 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 about OutOfMemoryExceptions 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?