Eu acho isso SortedList<TKey, TValue> SortedDictionary<TKey, TValue>e Dictionary<TKey, TValue>implemento as mesmas interfaces.

1. Quando devemos optar por SortedListe SortedDictionaryterminar Dictionary?
2. Qual é a diferença entre SortedListe SortedDictionaryem termos de aplicação?

1. Ao iterar sobre os elementos em qualquer um dos dois, os elementos serão classificados. Não é assim com Dictionary<T,V>.

2. MSDN trata da diferença entre SortedList<T,V>e SortedDictionary<T,V>:

A classe genérica SortedDictionary (TKey, TValue) é uma árvore de pesquisa binária com recuperação O (log n), onde n é o número de elementos no dicionário. Nesse aspecto, é semelhante à classe genérica SortedList (TKey, TValue). As duas classes têm modelos de objetos semelhantes e ambas têm recuperação O (log n). As duas classes diferem no uso de memória e na velocidade de inserção e remoção:

SortedList (TKey, TValue) usa menos memória do que SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) tem operações de inserção e remoção mais rápidas para dados não classificados: O (log n) em oposição a O (n) para SortedList (TKey, TValue).

Se a lista for preenchida de uma vez a partir de dados classificados, SortedList (TKey, TValue) será mais rápido do que SortedDictionary (TKey, TValue).

Eu mencionaria diferença entre dicionários.

A imagem acima mostra que Dictionary<K,V>é igual ou mais rápido em todos os casos do que Sortedanalógico, mas se a ordem dos elementos for necessária, por exemplo, para imprimi-los, Sortedum é escolhido.

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

Para resumir os resultados de um Teste de desempenho - SortedList x SortedDictionary x Dicionário x Hashtable , os resultados do melhor ao pior para diferentes cenários:

Uso de memória:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Inserções:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operações de pesquisa:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

operações de loop foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

1. Quando você deseja que a coleção seja classificada por chave ao iterar sobre ela. Se você não precisa que seus dados sejam classificados, é melhor você apenas ter um Dicionário, ele terá um desempenho melhor.

2. SortedList e SortedDictionary fazem praticamente a mesma coisa, mas são implementados de forma diferente, portanto, têm diferentes pontos fortes e fracos explicados aqui .

Posso ver que as respostas propostas se concentram no desempenho. O artigo fornecido a seguir não fornece nada de novo em relação ao desempenho, mas explica os mecanismos subjacentes. Observe também que ele não se concentra nos três CollectionTipos mencionados na pergunta, mas aborda todos os Tipos do System.Collections.Genericnamespace.

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

Extrai:

Dicionário <>

O Dicionário é provavelmente a classe de contêiner associativa mais usada. O Dicionário é a classe mais rápida para pesquisas / inserções / exclusões associativas porque usa uma tabela de hash por baixo dos panos . Como as chaves são hash, o tipo de chave deve implementar corretamente GetHashCode () e Equals () ou você deve fornecer um IEqualityComparer externo ao dicionário na construção. O tempo de inserção / exclusão / pesquisa de itens no dicionário é o tempo constante amortizado - O (1) - o que significa que não importa o tamanho do dicionário, o tempo que leva para encontrar algo permanece relativamente constante. Isso é altamente desejável para pesquisas de alta velocidade. A única desvantagem é que o dicionário, por natureza de usar uma tabela hash, não está ordenado, entãovocê não pode percorrer facilmente os itens em um Dicionário em ordem .

SortedDictionary <>

O SortedDictionary é semelhante ao Dicionário no uso, mas muito diferente na implementação. O SortedDictionary usa uma árvore binária nos bastidores para manter os itens em ordem pela chave . Como consequência da classificação, o tipo usado para a chave deve implementar IComparable corretamente para que as chaves possam ser classificadas corretamente. O dicionário classificado troca um pouco do tempo de pesquisa pela capacidade de manter os itens em ordem, portanto, os tempos de inserção / exclusão / pesquisa em um dicionário classificado são logarítmicos - O (log n). De modo geral, com o tempo logarítmico, você pode dobrar o tamanho da coleção e basta fazer uma comparação extra para encontrar o item. Use o SortedDictionary quando quiser pesquisas rápidas, mas também quiser manter a coleção em ordem pela chave.

SortedList <>

O SortedList é a outra classe de contêiner associativa classificada nos contêineres genéricos. Mais uma vez, SortedList, como SortedDictionary, usa uma chave para classificar pares de valores-chave . Ao contrário de SortedDictionary, no entanto, os itens em uma SortedList são armazenados como uma matriz classificada de itens. Isso significa que as inserções e exclusões são lineares - O (n) - porque excluir ou adicionar um item pode envolver o deslocamento de todos os itens para cima ou para baixo na lista. O tempo de pesquisa, entretanto, é O (log n) porque SortedList pode usar uma pesquisa binária para encontrar qualquer item na lista por sua chave. Então, por que você quer fazer isso? Bem, a resposta é que se você for carregar a SortedList antecipadamente, as inserções serão mais lentas, mas como a indexação de array é mais rápida do que seguir links de objetos, as pesquisas são ligeiramente mais rápidas do que SortedDictionary. Mais uma vez, eu usaria isso em situações em que você deseja pesquisas rápidas e deseja manter a coleção em ordem por chave, e onde inserções e exclusões são raras.

Resumo provisório dos procedimentos subjacentes

O feedback é muito bem-vindo, pois tenho certeza de que não acertei tudo.

• Todas as matrizes são de tamanho n.
• Matriz não classificada = .Add / .Remove é O (1), mas .Item (i) é O (n).
• Matriz classificada = .Add / .Remove é O (n), mas .Item (i) é O (log n).

Dicionário

Memória

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Adicionar

1. Adicionar HashArray(n) = Key.GetHash# O (1)
2. Adicionar KeyArray(n) = PointerToKey# O (1)
3. Adicionar ItemArray(n) = PointerToItem# O (1)

Remover

1. For i = 0 to n, encontre ionde HashArray(i) = Key.GetHash # O (log n) (matriz classificada)
2. Remova HashArray(i)# O (n) (matriz classificada)
3. Remova KeyArray(i)# O (1)
4. Remova ItemArray(i)# O (1)

Obter Item

1. For i = 0 to n, encontre ionde HashArray(i) = Key.GetHash# O (log n) (matriz classificada)
2. Retorna ItemArray(i)

Loop Through

1. For i = 0 to n, Retorna ItemArray(i)

SortedDictionary

Memória

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

Adicionar

1. Adicionar KeyArray(n) = PointerToKey# O (1)
2. Adicionar ItemArray(n) = PointerToItem# O (1)
3. For i = 0 to n, encontre ionde KeyArray(i-1) < Key < KeyArray(i)(usando ICompare) # O (n)
4. Adicione OrderArray(i) = n# O (n) (matriz classificada)

Remover

1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (n)
2. Remova KeyArray(SortArray(i))# O (n)
3. Remova ItemArray(SortArray(i))# O (n)
4. Remova OrderArray(i)# O (n) (matriz classificada)

Obter Item

1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (n)
2. Retorna ItemArray(i)

Loop Through

1. For i = 0 to n, Retorna ItemArray(OrderArray(i))

SortedList

Memória

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

Adicionar

1. For i = 0 to n, encontre ionde KeyArray(i-1) < Key < KeyArray(i)(usando ICompare) # O (log n)
2. Adicionar KeyArray(i) = PointerToKey# O (n)
3. Adicionar ItemArray(i) = PointerToItem# O (n)

Remover

1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Remova KeyArray(i)# O (n)
3. Remova ItemArray(i)# O (n)

Obter Item

1. For i = 0 to n, encontre ionde KeyArray(i).GetHash = Key.GetHash# O (log n)
2. Retorna ItemArray(i)

Loop Through

1. For i = 0 to n, Retorna ItemArray(i)

Tentando atribuir um pontuação de desempenho a cada caso apresentado por @Lev, usei os seguintes valores:

• O (1) = 3
• O (log n) = 2
• O (n) = 1
• O (1) ou O (n) = 2
• O (log n) ou O (n) = 1,5

Os resultados são (mais altos = melhores):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

É claro que cada caso de uso dará mais peso a certas operações.