SortedList<>, SortedDictionary<> and Dictionary<>

Question

I find that SortedList<TKey, TValue> SortedDictionary<TKey, TValue> and Dictionary<TKey, TValue> implement the same interfaces.

1. When should we opt for SortedList and SortedDictionary over Dictionary?
2. What is the difference between SortedList and SortedDictionary in terms of application?

Answer 1

1. When iterating over the elements in either of the two, the elements will be sorted. Not so with Dictionary<T,V>.

2. MSDN addresses the difference between SortedList<T,V> and SortedDictionary<T,V>:

The SortedDictionary(TKey, TValue) 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(TKey, TValue) 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:

SortedList(TKey, TValue) uses less memory than SortedDictionary(TKey, TValue).

SortedDictionary(TKey, TValue) has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList(TKey, TValue).

If the list is populated all at once from sorted data, SortedList(TKey, TValue) is faster than SortedDictionary(TKey, TValue).