1

I was absolutly sure that I need one (and some SO users too), but it turns out that my case was easily refactored with simple List<object>, and more I think about it I am no so sure anymore that one is needed and generics classes for collection managment are sufficient, I am just curious :)

btw. there is a similar question, but that question assumes that such class is needed, and only one comment suggest that maybe is not needed.

[EDIT] oh f*, I was ment to write OrderedDictionary not SortedDictionary, sorry folks, edited my post

1
  • Specialized datastructures are very important when the number of elements approach a non-trivial amount. For example, measure the performance of a trie vs a List<T> when implementing a version of autocompletion and putting a few million elements in it...
    – Max
    Commented Jun 13, 2011 at 7:06

4 Answers 4

4

There is a SortedList class that is actually a dictionary and may be what you were looking for - it isn't missing, but the naming is definitely a design flaw.

1
  • 1
    Tom, sorry, I meant OrderedDictionary not SortedDictionary, edited my question Commented Jun 13, 2011 at 8:24
1

It's hard to say whether it is a design flaw, as design usually corresponds to customer requirements, use cases, etc. Withough knowing the contraints that Microsoft identified (or missed), no conclusive result can be arrived at. Im my personal opinion, I've never needed such a data type, and don't see any fault in it being left out. That isn't to say that programmers who work with the framework don't need one, but just that one wasn't included. If you really feel that one should be included in the next release, head on over to Microsoft Connect and say so.

Having said that it is pretty trivial to roll your own if you need one. The naive (i.e. first thing that comes to mind =]) implementation (which may not suit your needs) would be to have two private members, a Dictionary and a List. For insertion, add the element to the list, and then add the index of the added element to the dictionary with the corresponding key that you need. Lookup can be achieved by using a value of Type KeyType (to get the corresponding index of the element), or by obtaining the element of the list by using a direct offset. Obviously don't forget to implement the applicable interfaces so that your class is compatible with other .NET functionality.

1
  • I wish Microsoft had documented that as long as a Dictionary has never in its lifetime had any items removed, items will enumerate in the order they were added. Maintaining an insertion-order guarantee when slots are recycled is expensive, but if no item is ever deleted no slot will ever need to be recycled.
    – supercat
    Commented Jan 24, 2015 at 21:54
0

Hmm, I program C# every day and I can't say that I've ever needed one. If I did I suppose it would be a simple matter to create - just implement IDictionary<,>. Though a dictionary is meant to be a hash, I don't know what it would mean to "sort" a hash

What are the scenarios when you would find yourself needing a sorted dictionary?

3
  • 2
    When you want to be able to enumerate it in order. Commented Jun 13, 2011 at 6:13
  • I don't know about yours, but my Oxford English Dictionary is sorted in word order. Some languages, like C++ provide both sorted (tree-based) and unsorted (hashed) map/dictionary implementations. Commented Jun 13, 2011 at 8:09
  • 1
    @Neil That will be worthwhile when the computer needs to open up the Mirriam Websters on the shelf but not particularly useful when you consider the advent of Random Access Memory. Are you talking about b-tree style performance optimization? I'm going to go ahead and make the claim that anything requiring actual optimization should not be stored in a Dictionary<,> Commented Jun 13, 2011 at 14:08
0

It seems that C# does provide both (though one is bizzarely named) so I'd just like to comment on why having both types is generally (not just in C#, about which I know little) a good idea.

There are basically two ways of implementing a map/dictionary. You can use a balanced binary tree or you can use a hash table. The first is unordered in that you can iterate over the members in key-order, and the second isn't. The ability to iterate in order is important in (for example) many text processing applications.

Tree-based maps have another advantage - they only need the types in them to supply comparison operators, where things in hash-based maps must supply a hash function. Most programmers have few problems implementing comparison, but a good hash function can be very hard to implement.

Unfortunately, tree-based maps are generally somewhat less efficient than hashed ones. My own investigations in C++ indicate that hashes are about twice as fast (which isn't such a big difference). But this is only in the general case - for example, maps where the keys are very long strings will probably be more efficiently implemented using btrees, as the comparison function does not have to consider the whole string, but the hash function does.

So there you have it, both types have their place in any good programmer's toolkit.

1

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.