Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
    
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 Jun 13 '11 at 7:06

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

share|improve this answer
1  
Tom, sorry, I meant OrderedDictionary not SortedDictionary, edited my question –  Antonio Bakula Jun 13 '11 at 8:24

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.

share|improve this answer

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?

share|improve this answer
2  
When you want to be able to enumerate it in order. –  Peter Taylor Jun 13 '11 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. –  nbt Jun 13 '11 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<,> –  George Mauer Jun 13 '11 at 14:08

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.

share|improve this answer
    
Don't forget skip lists! –  LukeN Feb 11 '13 at 5:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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