36

Why did Microsoft not provide generic implementation of OrderedDictionary?

There are a few custom implementations I've seen, including: http://www.codeproject.com/KB/recipes/GenericOrderedDictionary.aspx

But why did Microsoft not include it in the base .net library? Surely they had a reason for not building a generic.... but what is it?

Prior to posting this message, I did see: https://stackoverflow.com/questions/2629027/no-generic-implementation-of-ordereddictionary

But that just confirms that it does not exist. Not why it does not exist.

Thanks

8
  • 4
    There's always SortedDictionary<TKey, TValue> : msdn.microsoft.com/en-us/library/f7fta44c.aspx Nov 2, 2010 at 14:51
  • 2
    Unless I misunderstand the SortedDict docs, that is not what I want. I don't want any sorting done. I just want an array that I can also access by key. Anyway, I am really wondering why MS skipped this. (Subtle issues, etc.)
    – nonot1
    Nov 2, 2010 at 15:16
  • What's a typical use case for an ordered dictionary? I'm struggling to think of one off the top of my head. Nov 3, 2010 at 2:06
  • 2
    @Carson anytime you have what is an array of data items that you also need quick random access to. To simply store in a Dict loses the ordering information, and using an array requires your to maintain your own index.
    – nonot1
    Nov 3, 2010 at 11:30
  • 2
    Ask Eric Lippert to read and answer your question. He's usually very agreeable to helping out with this type of question. I think you can contact him via his blog: blogs.msdn.com/b/ericlippert
    – devuxer
    Jul 11, 2011 at 23:54

3 Answers 3

21

The OrderedDictionary overloads the indexing operation so that indexing with an integer N will get the item in position N, while indexing with an Object will retrieve the item coresponding to that object. If one were to create an OrderedDictionary<int, string> called myDict, and added items (1,"George") and (0,"Fred") in that order, should myDict[0] return "George" or "Fred"?

Such an issue could have been resolved by imposing a class constraint on the key type. On the other hand, much of the usefulness of generic collections stems from their ability to efficiently work with value types. Imposing a class constraint on the key type would seem a little ugly.

If the class didn't have to be CLS compliant but merely had to work with vb.net, a sensible design might have been to used named indexed properties. Thus, in the example above, myDict.ByKey[0] would have yielded "Fred", and myDict.BySequence[0] would have yielded "George". Unfortunately, languages like C# do not support named indexed properties. While one could have kludged something to allow use of the above syntax even without such properties, the unfortunate decision to wrap the fields of structures like Point and Rectangle means that for myDict.ByKey[0] = "Wally" to work, myDict.ByKey would have to return a new class object. A struct would be more efficient, but compilers would reject what looked like a write to a read-only structure (notwithstanding that the property wouldn't modify the struct returned by ByKey, but instead modify the collection to which it holds a reference).

Personally, I think a dictionary-ish object that was specified as keeping track of the insertion order would be a nice thing to have; I'd also like to have a dictionary-ish object which could easily return the key associated with a particular key (so that, e.g. if one has a case-insensitive dictionary and has added a record with a key of "GEORGE", one could ask the dictionary what key is associated with "George" without having to search through all the KeyValuePair objects returned in an enumeration.

2
  • Easily resolved by either a) choosing a behavior and clearly documenting (and never changing) it, b) adding a separate method that retrieves by index, or even c) making "int" an illegal key type. As long as the order does not change when retrieving by int, we don't care HOW it works. #sigh What I'm saying is ... it's not actually a hard problem.
    – tekHedd
    Dec 29, 2021 at 19:15
  • @tekHedd: The only way to make int an illegal key type would be to add a class constraint, which is a possibility I'd mentioned. Otherwise, the problem is that while VB.NET allows classes to have multiple indexed properties, C# doesn't.
    – supercat
    Dec 29, 2021 at 22:25
19

In C# 4.0 In A Nutshell I read this:

  1. An OrderedDictionary is a combination of a HashTable and ArrayList
  2. There is no generic ArrayList
  3. "The nongeneric ArrayList class is used mainly for backward compatibility with Framework 1.x..."
  4. "An ArrayList is functionally similiar to List<object>"
  5. "Reflection is easier with a nongeneric ArrayList than a List<object>"

Conclusion?

No generic OrderedDictionary because it's underlying construct is a (unofficially) depreciated class that has no generic version itself.

2
  • 10
    This doesn't really answer the question. A generic OrderedDictionary could obviously be build on a generic Dictionary and a generic List.
    – JacquesB
    Feb 3, 2017 at 19:21
  • One precept of class use is if the UI doesn't change who cares about implementation? Well, the language design / compiler team, let's say, might prefer the generic inheriting its non-generic counterpart. My spidey sense boggles. For starters: Is differing (immediate) ancestors a land mine somewhere in the evolutionary path for OrderedDictionary covariance and contra variance?
    – radarbob
    Apr 15, 2019 at 7:50
6

Because maintaining order prevents the O(1) lookup that IDictionary implies unless you wrap two collections (one for order, one for lookup), which makes add/remove less performant and increases memory usage. Or you could have slower lookup in exchance for less memory usage.

My guess is that there was no 'clearly better' choice here, so it didn't go into the standard library. Especially around 2.0, C# was still learning from Java's mistakes. I wouldn't be surprised if Java's 'everything and the kitchen sink' approach to collections in their standard library was viewed as something to avoid as well.

1
  • 5
    Having slower look-up in exchange for less memory just effectively makes the OrderedDictionary a List. I'd imagine that anyone with a legitimate use case for an OrderedDictionary is using it specifically because they need a collection class that has O(1) lookup but also remembers insertion order, in which case using additional memory is unavoidable and thus acceptable.
    – Abion47
    Dec 15, 2018 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.