when should I use a sorteddictionary instead of a dictionary [duplicate]

Question

As I wrote in some of my last posts I am still quite new to the c# world so it comes that I wrote small benchmark to compare Dictionary, Hashtable, SortedList and SortedDictionary against each other. The test runs with 8000 iterations and from 50 to 100000 elements. I tested adding of new elements, search for elements and looping through some elements all random. The results was as I expected them to be except the result of the SortedDictionary which was much confusing for me... It was just slow in all results. So did I missing sometging about the concept of a sorted dictionary. I already asked google but All that I found out was that others had come to the same test result. Slightly different based on their implementation of the test. Again my question: why is the SortedDicrionary so much slower than all the others?

Answer 1

A SortedDictionary is implemented as a binary search tree. Therefore, accessing an element is O(lg(n)). A Dictionary is a hash table, and has a complexity of O(1) for access.

A SortedDictionary is quite useful when you need the data to be sorted (a Dictionary has no defined order). Dictionary is appropriate for most cases.

Answer 2

The answer is simply that you would use the SortedDictionary if you need a dictionary that is sorted.

Remember that eventhough it ended up as slowest in your tests, it's still not slow. If you need exactly what the SortedDictionary does, it's the best solution. To do the same using a Dictionary or a SortedList would be very much slower.