Coleções e estruturas de dados

Dados semelhantes podem normalmente ser tratados com mais eficiência quando armazenados e manipulados como uma coleção. Você pode usar a classe ou as classes nos System.Array System.Collections namespaces , , , e para adicionar, remover e modificar elementos individuais ou um intervalo de elementos em System.Collections.Generic System.Collections.Concurrent uma System.Collections.Immutable coleção.

Há dois tipos principais de coleções; coleções genéricas e coleções não genéricas. Coleções genéricas são fortemente tipadas em tempo de compilação. Por isso, coleções genéricas normalmente oferecem melhor desempenho. Coleções genéricas aceitam um parâmetro de tipo quando são criadas e não exigem que você converta de e para o tipo Object ao adicionar ou remover itens da coleção. Além disso, a maioria das coleções genéricas tem suporte Windows da Store. Coleções não genéricas armazenam itens como , exigem a seleção e a maioria não tem suporte para o desenvolvimento de aplicativos Object Windows Store. No entanto, você pode ver as coleções não genéricas no código mais antigo.

Começando com .NET Framework 4, as coleções no namespace fornecem operações thread-safe eficientes para acessar itens de coleção System.Collections.Concurrent de vários threads. As classes de coleção imutáveis no namespace ( pacote NuGet ) são inerentemente thread-safe porque as operações são executadas em uma cópia da coleção original e a coleção original não pode ser System.Collections.Immutable modificada.

Recursos comuns de coleção

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

Além disso, muitas classes de coleção contêm os seguintes recursos:

  • Propriedades de capacidade e contagem

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

    A maioria das coleções se expande automaticamente em capacidade quando a capacidade atual é atingida. A memória é realocada e os elementos são copiados da coleção antiga para a nova. Isso reduz o código necessário para usar a coleção; no entanto, o desempenho da coleção pode ser afetado de forma negativa. Por exemplo, para List<T> , se for menor que , adicionar um item será uma operação Count Capacity O(1). Se a capacidade precisar ser aumentada para acomodar o novo elemento, adicionar um item se tornará uma operação n O(), em que é n Count . A melhor maneira de evitar um desempenho ruim causado por várias realocações é definir a capacidade inicial para que seja o tamanho estimado da coleção.

    Uma BitArray é um caso especial; sua capacidade é a mesma que seu comprimento, que é o mesmo de 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 namespaces System.Collections têm um limite inferior de zero, indicando que são indexados em 0. Array tem um limite inferior de zero por padrão, mas um limite inferior diferente pode ser definido ao criar uma instância da classe Array usando Array.CreateInstance .

  • Sincronização para acesso de vários threads System.Collections (somente classes).

    Tipos de coleção não genérica no namespace System.Collections oferecem algum acesso thread-safe com sincronização; geralmente exposto por meio dos membros SyncRoot e IsSynchronized. Essas coleções são não thread-safe por padrão. Se você precisar de acesso com multithread escalável e eficiente para uma coleção, use uma das classes no namespace System.Collections.Concurrent ou considere usar uma coleção imutável. Para obter mais informações, veja Coleções thread-safe.

Escolher uma coleção

Em geral, você deve usar coleções genéricas. A tabela a seguir descreve alguns cenários comuns de coleção e as classes de coleção que você pode usar para esses cenários. Se você for inexperiente com coleções genéricas, esta tabela o ajudará a escolher a coleção genérica adequada para a tarefa.

Eu quero… Opções de coleção genérica Opções de coleção não genérica Opções de coleção thread-safe ou imutável
Armazenar itens como pares chave/valor para consulta rápida por chave Dictionary<TKey,TValue> Hashtable

(Um conjunto de pares chave/valor que são organizados com base no código hash da chave.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Itens de acesso por índice List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
Usar itens primeiro a entrar, primeiro a sair (PEPS) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Usar dados último a entrar, primeiro a sair (UEPS) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Acessar itens em sequência LinkedList<T> Nenhuma recomendação Nenhuma recomendação
Receba notificações quando itens forem removidos da coleção ou adicionados a ela. (implementa INotifyPropertyChanged e INotifyCollectionChanged) ObservableCollection<T> Nenhuma recomendação Nenhuma recomendação
Uma coleção classificada SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

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

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

ImmutableSortedSet<T>

Complexidade algorítmica de coleções

Ao escolher uma classe de coleção, vale a pena considerar possíveis trocas no desempenho. Use a tabela a seguir para referenciar como vários tipos de coleção mutáveis se comparam na complexidade algorítmica com suas contrapartes imutáveis correspondentes. Geralmente, os tipos de coleção imutáveis são menos bem-desempenho, mas fornecem imutabilidade , que geralmente é 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>.AddPesquisa 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> busca O (1) O (1) – ou estritamente O ( n ) ImmutableDictionary<T> busca O (log n )
SortedDictionary<T>.Add O (log n ) O ( n log n ) ImmutableSortedDictionary<T>.Add O (log n )

Um List<T> pode ser enumerado com eficiência usando um for loop ou um foreach loop. ImmutableList<T>No entanto, um trabalho insatisfatório dentro de um for loop ocorre devido ao tempo (de log n ) do seu indexador. A enumeração de um ImmutableList<T> usando um foreach loop é eficiente porque o ImmutableList<T> usa uma árvore binária para armazenar seus dados em vez de uma matriz simples, como o List<T> uso. Uma matriz pode ser rapidamente indexada em, enquanto uma árvore binária deve ser percorrido até que o nó com o índice desejado seja encontrado.

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

Título Descrição
Selecionando uma classe de coleção Descreve as diferentes coleções e ajuda a selecionar uma para o seu cenário.
Tipos de coleção comumente usados Descreve os tipos de coleção genérica e não genérica normalmente usadas, tais como System.Array, System.Collections.Generic.List<T>, e System.Collections.Generic.Dictionary<TKey,TValue>.
Quando usar coleções genéricas Descreve o uso de tipos de coleção genérica.
Comparações e classificações dentro de coleções Discute o uso de comparações de igualdade e comparações de classificação em coleções.
Tipos de coleção classificados Descreve as características e o desempenho de coleções classificadas
Tipos de Coleção de Tabela de Hash e Dicionário Descreve os recursos de tipos de dicionário baseado em hash genérico e não genérico.
coleções de Cofre de Thread Descreve os tipos de coleção, tais como System.Collections.Concurrent.BlockingCollection<T> e System.Collections.Concurrent.ConcurrentBag<T> que dão suporte a acesso simultâneo seguro e eficiente de vários threads.
System.Collections.Immutable Apresenta as coleções imutáveis e fornece links para os tipos de coleção.

Referência

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