Thread: SortedDictionary v.s. Dictionary

Hello everyone,


Here is my understanding of pros and cons SortedDictionary v.s. Dictionary, am I correct? Or anything important missing? What is your practices of when to use SortedDictionary and when to use Dictionary?

1. Dictionary is faster for insertion and removal, but slower for query value by key compared with SortedDictionary;
2. Dictionary is using a linear array to store key/value pair, but SortedDictionary is using binary search tree to store key/value pair, so for query, SortedDictionary is faster.


thanks in advance,
George

Thanks nvoigt!


I agree. Looks like lookup operation in Dictionary is faster than SortedDictionary? And for insert/delete, Dictionary is also faster than SortedDictionary?

Mentioned here,

http://msdn.microsoft.com/en-us/libr...08(VS.80).aspx

"Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table." Looks like the query time for Dictionary is O(1), but the query time for SortedDictionary is O(logn) -- "The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal."

http://msdn.microsoft.com/en-us/libr...4c(VS.80).aspx

Originally Posted by nvoigt

You are wrong. But I won't go ahead and spoon feed the helpfile to you, when the answer is on the very first page. Try to do some work on your own.

regards,
George