I find that `SortedList<TKey, TValue>`

`SortedDictionary<TKey, TValue>`

and `Dictionary<TKey, TValue>`

implement the same interfaces.

- When should we opt for
`SortedList`

and`SortedDictionary`

over`Dictionary`

? - What is the difference between
`SortedList`

and`SortedDictionary`

in terms of application?

When iterating over the elements in either of the two, the elements will be sorted. Not so with

`Dictionary<T,V>`

.MSDN addresses the difference between

`SortedList<T,V>`

and`SortedDictionary<T,V>`

:I'd mention difference between dictionaries.

Above picture shows that

`Dictionary<K,V>`

is equal or faster in every case than`Sorted`

analog, but if order of elements is required, e.g. to print them,`Sorted`

one is chosen.Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

To summarize the results of a Performance Test - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable, the results from best to worst for different scenarios:

Memory Usage:Insertions:Search Operations:foreach loop operationsWhen you want the collection to be sorted by key when you iterate over it. If you don't need your data to be sorted, you're better off with just a Dictionary, it'll have better performance.

SortedList and SortedDictionary pretty much do the same thing, but are implemented differently, thus have different strengths and weaknesses explained here.

I can see the proposed answers focus on performance. The article provided below does not provide anything new regarding performance, but it explains the underlying mechanisms. Also note it does not focus on the three

`Collection`

Types mentionned in the question, but adresses all the Types of the`System.Collections.Generic`

namespace.http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

## Extracts:

## Dictionnary<>

## SortedDictionary<>

## SortedList<>

## Tentative Summary of underlying Procedures

Feedback is very welcome as I am sure I did not get everything right.`n`

.DictionnaryMemory`KeyArray(n) -> non-sorted array<pointer>`

`ItemArray(n) -> non-sorted array<pointer>`

`HashArray(n) -> sorted array<hashvalue>`

Add`HashArray(n) = Key.GetHash`

# O(1)`KeyArray(n) = PointerToKey`

# O(1)`ItemArray(n) = PointerToItem`

# O(1)Remove`For i = 0 to n`

, find`i`

where`HashArray(i) = Key.GetHash`

# O(log n) (sorted array)`HashArray(i)`

# O(n) (sorted array)`KeyArray(i)`

# O(1)`ItemArray(i)`

# O(1)Get Item`For i = 0 to n`

, find`i`

where`HashArray(i) = Key.GetHash`

# O(log n) (sorted array)`ItemArray(i)`

Loop Through`For i = 0 to n`

, return`ItemArray(i)`

SortedDictionaryMemory`KeyArray(n) = non-sorted array<pointer>`

`ItemArray(n) = non-sorted array<pointer>`

`OrderArray(n) = sorted array<pointer>`

Add`KeyArray(n) = PointerToKey`

# O(1)`ItemArray(n) = PointerToItem`

# O(1)`For i = 0 to n`

, find`i`

where`KeyArray(i-1) < Key < KeyArray(i)`

(using`ICompare`

) # O(n)`OrderArray(i) = n`

# O(n) (sorted array)Remove`For i = 0 to n`

, find`i`

where`KeyArray(i).GetHash = Key.GetHash`

# O(n)`KeyArray(SortArray(i))`

# O(1)`ItemArray(SortArray(i))`

# O(1)`OrderArray(i)`

# O(n) (sorted array)Get Item`For i = 0 to n`

, find`i`

where`KeyArray(i).GetHash = Key.GetHash`

# O(n)`ItemArray(i)`

Loop Through`For i = 0 to n`

, return`ItemArray(OrderArray(i))`

SortedListMemory`KeyArray(n) = sorted array<pointer>`

`ItemArray(n) = sorted array<pointer>`

Add`For i = 0 to n`

, find`i`

where`KeyArray(i-1) < Key < KeyArray(i)`

(using`ICompare`

) # O(log n)`KeyArray(i) = PointerToKey`

# O(n)`ItemArray(i) = PointerToItem`

# O(n)Remove`For i = 0 to n`

, find`i`

where`KeyArray(i).GetHash = Key.GetHash`

# O(log n)`KeyArray(i)`

# O(n)`ItemArray(i)`

# O(n)Get Item`For i = 0 to n`

, find`i`

where`KeyArray(i).GetHash = Key.GetHash`

# O(log n)`ItemArray(i)`

Loop Through`For i = 0 to n`

, return`ItemArray(i)`

Trying to assign a

performance scoreto each case presented by @Lev, I used the following values:The results are (higher = better):

Of course, every use-case will give more weight to certain operations.