Compartilhar via

Coleções e estruturas de dados

Dados semelhantes geralmente podem ser tratados com mais eficiência quando armazenados e manipulados como uma coleção. Você pode usar a System.Array classe ou as classes em System.Collections, System.Collections.Generice System.Collections.ConcurrentSystem.Collections.Immutable namespaces para adicionar, remover e modificar elementos individuais ou um intervalo de elementos em uma 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 construídas. Eles não exigem que você converta de e para o tipo Object ao adicionar ou remover itens da coleção. Além disso, há suporte para a maioria das coleções genéricas em aplicativos da Windows Store. As coleções não genéricas armazenam itens como Object, exigem a conversão e a maioria não tem suporte para o desenvolvimento de aplicativos da Windows Store. No entanto, você pode ver coleções não genéricas no código mais antigo.

No .NET Framework 4 e versões posteriores, as coleções no namespace System.Collections.Concurrent fornecem operações thread-safe eficientes para acessar itens da coleção por meio de vários threads. As classes de coleção imutáveis no System.Collections.Immutable 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 modificada.

Funcionalidades comuns da 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 implementam direta ou indiretamente a ICollection interface ou a ICollection<T> interface compartilham esses 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 é alcançada. A memória é realocada e os elementos são copiados da coleção antiga para a nova. Esse design reduz o código necessário para usar a coleção. No entanto, o desempenho da coleção pode ser afetado negativamente. Por exemplo, para List<T>, se Count for menor que Capacity, adicionar um item é uma operação O(1). Se a capacidade precisar ser aumentada para acomodar o novo elemento, adicionar um item se tornará uma operação O(n), onde n está Count. A melhor maneira de evitar o baixo desempenho causado por várias realocações é definir a capacidade inicial como 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 de seu primeiro elemento. Todas as coleções indexadas nos namespaces System.Collections têm um limite inferior de zero, o que significa que são indexadas a partir de 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).

    Os tipos de coleções não genéricas no namespace System.Collections oferecem algum acesso thread-safe com sincronização, geralmente exposto por meio dos membros SyncRoot e IsSynchronized. Essas coleções não são thread-safe por padrão. Se você precisar de acesso escalonável e eficiente de vários threads a uma coleção, use uma das classes no System.Collections.Concurrent namespace ou considere usar uma coleção imutável. Para obter mais informações, consulte Thread-Safe Collections.

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 novo em coleções genéricas, a tabela a seguir ajudará você a escolher a coleção genérica que funciona melhor para sua tarefa:

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

(Uma coleção 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>
Acessar itens 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 sequencialmente LinkedList<T> Nenhuma recomendação Nenhuma recomendação
Receba notificações quando os itens forem removidos ou adicionados à coleção. (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 para 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 compensações 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 seus equivalentes imutáveis correspondentes. Geralmente, os tipos de coleção imutáveis são menos performantes, mas fornecem imutabilidade - o 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> pesquisa O(1) O(1) – ou estritamente O(n) ImmutableDictionary<T> pesquisa 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. No entanto, uma ImmutableList<T> não é eficiente em um loop for, devido ao tempo de O(log n) do indexador. Enumerar um ImmutableList<T> usando um loop foreach é eficiente porque ImmutableList<T> usa uma árvore binária para armazenar seus dados em vez de uma matriz como List<T> usa. Uma matriz pode ser indexada rapidamente, enquanto uma árvore binária precisa ser percorrida até que o nó com o índice desejado seja encontrado.

Além disso, SortedSet<T> tem a mesma complexidade que ImmutableSortedSet<T> porque ambas usam árvores binárias. A diferença significativa é que ImmutableSortedSet<T> usa uma árvore binária imutável. Como ImmutableSortedSet<T> 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 você a selecionar uma para seu cenário.
Tipos de coleção comumente usados Descreve tipos de coleção genéricos e não genéricos comumente usados, 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 ordenados Descreve o desempenho e as características das coleções classificadas.
Tipos de coleção de tabela de hash e dicionário Descreve as características dos tipos de dicionário baseados em hash, genéricos e não genéricos.
ColeçõesThread-Safe Descreve tipos de coleção 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