Partilhar via

Recolhas e Estruturas de Dados

  • Artigo

Dados semelhantes podem muitas vezes ser tratados de forma mais eficiente quando armazenados e manipulados como uma recolha. Pode utilizar a System.Array classe ou as classes nos System.Collectionsespaços System.Collections.Genericde nomes System.Collections.ConcurrentSystem.Collections.Immutable para adicionar, remover e modificar elementos individuais ou uma gama de elementos numa coleção.

Existem dois tipos principais de coleções; coleções genéricas e coleções não genéricas. As coleções genéricas são tipo de segurança na hora da compilação. Por isso, as coleções genéricas normalmente oferecem um melhor desempenho. As coleções genéricas aceitam um parâmetro de tipo quando são construídas e não requerem que você lance de e para o Object tipo quando adiciona ou remove itens da coleção. Além disso, a maioria das coleções genéricas são suportadas em aplicações Windows Store. As coleções não genéricas armazenam itens como Object, requerem casting, e a maioria não é suportada para o desenvolvimento de aplicações Windows Store. No entanto, pode ver coleções não genéricas em código mais antigo.

Começando com .NET Framework 4, as coleções no espaço de System.Collections.Concurrent nome fornecem operações eficientes de segurança para fios para aceder a itens de recolha a partir de vários fios. As classes de recolha imutáveis no espaço de System.Collections.Immutable nomes (pacote NuGet) são inerentemente seguras porque as operações são realizadas numa cópia da coleção original e a coleção original não pode ser modificada.

Características comuns da coleção

Todas as coleções fornecem métodos para adicionar, remover ou encontrar itens na coleção. Além disso, todas as coleções que implementam direta ou indiretamente a ICollection interface ou a ICollection<T> interface partilham estas funcionalidades:

Além disso, muitas classes de recolha contêm as seguintes características:

  • Capacidade e Propriedades de Contagem

    A capacidade de uma coleção é o número de elementos que pode conter. A contagem de uma coleção é o número de elementos que realmente contém. Algumas coleções escondem a capacidade ou a contagem ou ambos.

    A maioria das coleções expande-se automaticamente na capacidade quando a capacidade atual é alcançada. A memória é realojada, e os elementos são copiados da coleção antiga para a nova. Isto reduz o código necessário para a utilização da coleção; no entanto, o desempenho da coleção pode ser negativamente afetado. Por exemplo, para List<T>, se Count for menos do que Capacity, adicionar um item é uma operação O(1). Se a capacidade tiver de ser aumentada para acomodar o novo elemento, adicionar um item torna-se uma operação On,,onde n está Count. A melhor maneira de evitar um mau desempenho causado por múltiplas reafectações é definir a capacidade inicial para ser o tamanho estimado da coleção.

    A BitArray é um caso especial; a sua capacidade é a mesma do seu comprimento, que é o mesmo que a sua contagem.

  • Um limite inferior consistente

    O limite inferior de uma coleção é o índice do seu primeiro elemento. Todas as coleções indexadas nos System.Collections espaços de nome têm um limite inferior de zero, o que significa que são indexadas a 0. Array tem um limite inferior de zero por defeito, mas um limite inferior diferente pode ser definido ao criar um exemplo da classe Array usando Array.CreateInstance.

  • Sincronização para acesso a partir de vários fios (System.Collections apenas classes).

    Os tipos de recolha não genéricos no espaço de System.Collections nome proporcionam alguma segurança do fio com sincronização; normalmente expostos através dos SyncRoot e IsSynchronized membros. Estas coleções não são seguras por defeito. Se necessitar de acesso multi-roscado escalável e eficiente a uma coleção, use uma das classes no espaço de System.Collections.Concurrent nomes ou considere usar uma coleção imutável. Para mais informações, consulte a Thread-Cofre Collections.

Escolha uma coleção

Em geral, deve usar coleções genéricas. A tabela seguinte descreve alguns cenários de recolha comuns e as classes de recolha que pode usar para esses cenários. Se você é novo em coleções genéricas, esta tabela irá ajudá-lo a escolher a coleção genérica que funciona melhor para a sua tarefa.

Eu quero... Opções genéricas de recolha Opções de recolha não genéricas Opções de recolha seguras ou imutáveis
Armazenar itens como pares chave/valor para uma procura rápida por chave Dictionary<TKey,TValue> Hashtable

(Uma coleção de pares chave/valor que são organizados com base no código de haxixe da chave.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Aceder a itens por índice List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Utilize os itens primeiro no primeiro lugar (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Utilizar dados Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Aceder a itens sequencialmente LinkedList<T> Sem recomendação Sem recomendação
Receba notificações quando os itens forem removidos ou adicionados à coleção. (instrumentos INotifyPropertyChanged e INotifyCollectionChanged) ObservableCollection<T> Sem recomendação Sem recomendação
Uma coleção ordenada SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Um conjunto para funções matemáticas HashSet<T>

SortedSet<T>		 Sem recomendação ImmutableHashSet<T>

ImmutableSortedSet<T>

Complexidade algorítmica das coleções

Ao escolher uma classe de coleção, vale a pena considerar potenciais tradeoffs no desempenho. Utilize a tabela seguinte para fazer referência à forma como vários tipos de recolha mutáveis se comparam em complexidade algorítmica às suas correspondentes congéneres imutáveis. Muitas vezes, os tipos de recolha imutáveis são menos performantes, mas proporcionam imutabilidade - o que muitas vezes é um benefício comparativo válido.

Mutável Amortizado Pior caso Imutável Complexidade
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, procura O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> lookup O(1) O(1) – ou estritamente O(n) ImmutableDictionary<T> lookup O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

A List<T> pode ser enumerada de forma eficiente usando um for loop ou um foreach loop. Um ImmutableList<T>, no entanto, faz um mau trabalho dentro de um for loop, devido ao tempo O (log n) para o seu indexante. Enumerar um ImmutableList<T>foreach loop é eficiente porque ImmutableList<T> usa uma árvore binária para armazenar os seus dados em vez de uma matriz simples como List<T> utilizações. Uma matriz pode ser muito rapidamente indexada, enquanto uma árvore binária deve ser descendo até que o nó com o índice desejado seja encontrado.

Além disso, SortedSet<T> tem a mesma complexidade que ImmutableSortedSet<T>. Isso é porque ambos usam árvores binárias. A diferença significativa, é claro, é que ImmutableSortedSet<T> usa uma árvore binária imutável. Uma vez ImmutableSortedSet<T> que também oferece uma System.Collections.Immutable.ImmutableSortedSet<T>.Builder classe que permite mutação, você pode ter imutabilidade e desempenho.

Título Descrição
Selecionando uma classe de coleção Descreve as diferentes coleções e ajuda-o a selecionar uma para o seu cenário.
Tipos de recolha comumente usados Descreve tipos de recolha genéricos e não-genes comumente usados, tais como System.Array, System.Collections.Generic.List<T>e System.Collections.Generic.Dictionary<TKey,TValue>.
Quando usar coleções genéricas Discute-se a utilização de tipos de recolha genérica.
Comparações e Sorts Dentro de Coleções Discute-se a utilização de comparações de igualdade e comparações de triagem em coleções.
Tipos de recolha ordenado Descreve desempenho e características de coleções ordenadas
Tipos de coleção de hashtable e dicionário Descreve as características de tipos de dicionários genéricos e não genéricos baseados em haxixe.
Coleções thread-Cofre Descreve tipos de recolha como System.Collections.Concurrent.BlockingCollection<T> e System.Collections.Concurrent.ConcurrentBag<T> que suportam acesso simultâneo seguro e eficiente a partir de vários fios.
System.Collections.Imuttable Introduz as coleções imutáveis e fornece ligações aos tipos de recolha.

Referência

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable