Qual é a diferença entre SortedList e SortedDictionary?

Existe alguma diferença prática real entre um SortedList e um SortedDictionary ? Há alguma circunstância em que você usaria especificamente um e não o outro?

Sim – suas características de desempenho diferem significativamente. Provavelmente seria melhor chamá-los de SortedList e SortedTree pois isso reflete a implementação mais de perto.

Veja os documentos do MSDN para cada um deles ( SortedList , SortedDictionary ) para detalhes do desempenho de diferentes operações em diferentes situações. Aqui está um bom resumo (dos documentos SortedDictionary ):

A class genérica SortedDictionary é uma tree de pesquisa binária com recuperação de O (log n), onde n é o número de elementos no dictionary. Neste, é semelhante à class genérica SortedList . As duas classs têm modelos de objects semelhantes e ambas possuem recuperação O (log n). Onde as duas classs diferem é no uso de memory e velocidade de inserção e remoção:

  • SortedList usa menos memory que SortedDictionary .

  • SortedDictionary 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 .

  • Se a lista for preenchida de uma só vez a partir de dados classificados, SortedList será mais rápido que SortedDictionary .

( SortedList na verdade mantém uma matriz ordenada, em vez de usar uma tree. Ela ainda usa a pesquisa binária para encontrar elementos.)

Aqui está uma visão tabular, se isso ajudar …

De uma perspectiva de desempenho :

 +------------------+---------+----------+--------+----------+----------+---------+ | Collection | Indexed | Keyed | Value | Addition | Removal | Memory | | | lookup | lookup | lookup | | | | +------------------+---------+----------+--------+----------+----------+---------+ | SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser | | SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater | +------------------+---------+----------+--------+----------+----------+---------+ * Insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list (assuming no resize is required). 

De uma perspectiva de implementação :

 +------------+---------------+----------+------------+------------+------------------+ | Underlying | Lookup | Ordering | Contiguous | Data | Exposes Key & | | structure | strategy | | storage | access | Value collection | +------------+---------------+----------+------------+------------+------------------+ | 2 arrays | Binary search | Sorted | Yes | Key, Index | Yes | | BST | Binary search | Sorted | No | Key | Yes | +------------+---------------+----------+------------+------------+------------------+ 

Para parafrasear aproximadamente , se você precisar de desempenho bruto, o SortedDictionary poderia ser uma escolha melhor. Se você precisar de menos sobrecarga de memory e recuperação indexada, a SortedList se SortedList melhor. Veja esta pergunta para mais sobre quando usar qual.

Você pode ler mais aqui , aqui , aqui , aqui e aqui .

Eu abri o Reflector para dar uma olhada nisso, pois parece haver um pouco de confusão sobre o SortedList . Na verdade, não é uma tree de pesquisa binária, é uma matriz ordenada (por chave) de pares de valores-chave . Há também uma variável de TKey[] keys que é classificada em sincronia com os pares de valor-chave e usada para pesquisa binária.

Aqui está alguma fonte (visando .NET 4.5) para fazer backup de minhas reivindicações.

Membros privados

 // Fields private const int _defaultCapacity = 4; private int _size; [NonSerialized] private object _syncRoot; private IComparer comparer; private static TKey[] emptyKeys; private static TValue[] emptyValues; private KeyList keyList; private TKey[] keys; private const int MaxArrayLength = 0x7fefffff; private ValueList valueList; private TValue[] values; private int version; 

SortedList.ctor (IDictionary, IComparer)

 public SortedList(IDictionary dictionary, IComparer comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer) { if (dictionary == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); } dictionary.Keys.CopyTo(this.keys, 0); dictionary.Values.CopyTo(this.values, 0); Array.Sort(this.keys, this.values, comparer); this._size = dictionary.Count; } 

SortedList.Add (TKey, TValue): void

 public void Add(TKey key, TValue value) { if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } int num = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer); if (num >= 0) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } this.Insert(~num, key, value); } 

SortedList.RemoveAt (int): void

 public void RemoveAt(int index) { if ((index < 0) || (index >= this._size)) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); } this._size--; if (index < this._size) { Array.Copy(this.keys, index + 1, this.keys, index, this._size - index); Array.Copy(this.values, index + 1, this.values, index, this._size - index); } this.keys[this._size] = default(TKey); this.values[this._size] = default(TValue); this.version++; } 

Confira a página do MSDN para SortedList :

Na seção Comentários:

A class genérica SortedList< (Of <(TKey, TValue>)>) é uma tree de pesquisa binária com recuperação de O(log n) , onde n é o número de elementos no dictionary. Neste, é semelhante à class genérica SortedDictionary< (Of <(TKey, TValue>)>) . As duas classs têm modelos de objects semelhantes e ambas possuem recuperação O(log n) . Onde as duas classs diferem é no uso de memory e velocidade de inserção e remoção:

  • SortedList< (Of <(TKey, TValue>)>) usa menos memory que SortedDictionary< (Of <(TKey, TValue>)>) .
  • SortedDictionary< (Of <(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< (Of <(TKey, TValue>)>) .

  • Se a lista for preenchida de uma só vez a partir de dados classificados, SortedList< (Of <(TKey, TValue>)>) será mais rápido que SortedDictionary< (Of <(TKey, TValue>)>) .

Esta é uma representação visual de como os desempenhos se comparam entre si.

Já é dito o suficiente sobre o assunto, mas para simplificar, aqui está minha opinião.

O dictionary ordenado deve ser usado quando

  • Mais inserções e operações de exclusão são necessárias.
  • Dados não ordenados.
  • O access chave é suficiente e o access ao índice não é necessário.
  • A memory não é um gargalo.

Por outro lado, a Lista Ordenada deve ser usada quando

  • Mais pesquisas e menos inserções e operações de exclusão são necessárias.
  • Os dados já estão classificados (se não todos, a maioria).
  • O access ao índice é obrigatório.
  • A memory é uma sobrecarga.

Espero que isto ajude!!

O access ao índice (mencionado aqui) é a diferença prática. Se você precisar acessar o sucessor ou predecessor, precisará de SortedList. SortedDictionary não pode fazer isso, então você é bastante limitado em como você pode usar a ordenação (first / foreach).