Coleções e estruturas de dadosCollections and Data Structures

Dados semelhantes podem normalmente ser tratados com mais eficiência quando armazenados e manipulados como uma coleção.Similar data can often be handled more efficiently when stored and manipulated as a collection. Você pode usar a System.Array classe ou as classes nos System.Collections System.Collections.Generic System.Collections.Concurrent namespaces,, e System.Collections.Immutable para adicionar, remover e modificar elementos individuais ou um intervalo de elementos em uma coleção.You can use the System.Array class or the classes in the System.Collections, System.Collections.Generic, System.Collections.Concurrent, and System.Collections.Immutable namespaces to add, remove, and modify either individual elements or a range of elements in a collection.

Há dois tipos principais de coleções; coleções genéricas e coleções não genéricas.There are two main types of collections; generic collections and non-generic collections. Coleções genéricas são fortemente tipadas em tempo de compilação.Generic collections are type-safe at compile time. Por isso, coleções genéricas normalmente oferecem melhor desempenho.Because of this, generic collections typically offer better performance. 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.Generic collections accept a type parameter when they are constructed and do not require that you cast to and from the Object type when you add or remove items from the collection. Além disso, há suporte para a maioria das coleções genéricas em aplicativos da Windows Store.In addition, most generic collections are supported in Windows Store apps. 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.Non-generic collections store items as Object, require casting, and most are not supported for Windows Store app development. No entanto, você pode ver as coleções não genéricas no código mais antigo.However, you may see non-generic collections in older code.

A partir do .NET Framework 4, as coleções no System.Collections.Concurrent namespace fornecem operações eficientes de thread-safe para acessar itens de coleção de vários threads.Starting with .NET Framework 4, the collections in the System.Collections.Concurrent namespace provide efficient thread-safe operations for accessing collection items from multiple threads. As classes de coleção imutáveis no System.Collections.Immutable namespace (pacote NuGet) são inerentemente seguras ao thread 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.The immutable collection classes in the System.Collections.Immutable namespace (NuGet package) are inherently thread-safe because operations are performed on a copy of the original collection and the original collection cannot be modified.

Recursos comuns de coleçãoCommon collection features

Todas as coleções fornecem métodos para adicionar, remover ou localizar itens na coleção.All collections provide methods for adding, removing, or finding items in the collection. Além disso, todas as coleções que direta ou indiretamente implementam a interface ICollection ou a interface ICollection<T> compartilham estes recursos:In addition, all collections that directly or indirectly implement the ICollection interface or the ICollection<T> interface share these features:

Além disso, muitas classes de coleção contêm os seguintes recursos:In addition, many collection classes contain the following features:

  • Propriedades de capacidade e contagemCapacity and Count properties

    A capacidade de uma coleção é o número de elementos que ela pode conter.The capacity of a collection is the number of elements it can contain. A contagem de uma coleção é o número de elementos que ela realmente contém.The count of a collection is the number of elements it actually contains. Algumas coleções ocultam a capacidade ou a contagem ou ambas.Some collections hide the capacity or the count or both.

    A maioria das coleções se expande automaticamente em capacidade quando a capacidade atual é atingida.Most collections automatically expand in capacity when the current capacity is reached. A memória é realocada e os elementos são copiados da coleção antiga para a nova.The memory is reallocated, and the elements are copied from the old collection to the new one. 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.This reduces the code required to use the collection; however, the performance of the collection might be negatively affected. Por exemplo, para List<T> , se Count for menor que Capacity , a adição de um item será uma operação O (1).For example, for List<T>, if Count is less than Capacity, adding an item is an O(1) operation. Se a capacidade precisar ser aumentada para acomodar o novo elemento, adicionar um item se tornará uma n operação O (), em que n é Count .If the capacity needs to be increased to accommodate the new element, adding an item becomes an O(n) operation, where n is 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.The best way to avoid poor performance caused by multiple reallocations is to set the initial capacity to be the estimated size of the collection.

    Uma BitArray é um caso especial; sua capacidade é a mesma que seu comprimento, que é o mesmo de sua contagem.A BitArray is a special case; its capacity is the same as its length, which is the same as its count.

  • Um limite inferior consistenteA consistent lower bound

    O limite inferior de uma coleção é o índice do seu primeiro elemento.The lower bound of a collection is the index of its first element. Todas as coleções indexadas nos namespaces System.Collections têm um limite inferior de zero, indicando que são indexados em 0.All indexed collections in the System.Collections namespaces have a lower bound of zero, meaning they are 0-indexed. 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 de matriz usando Array.CreateInstance .Array has a lower bound of zero by default, but a different lower bound can be defined when creating an instance of the Array class using Array.CreateInstance.

  • Sincronização para acesso de vários threads ( System.Collections somente classes).Synchronization for access from multiple threads (System.Collections classes only).

    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.Non-generic collection types in the System.Collections namespace provide some thread safety with synchronization; typically exposed through the SyncRoot and IsSynchronized members. Essas coleções são não thread-safe por padrão.These collections are not thread-safe by default. 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.If you require scalable and efficient multi-threaded access to a collection, use one of the classes in the System.Collections.Concurrent namespace or consider using an immutable collection. Para obter mais informações, veja Coleções thread-safe.For more information, see Thread-Safe Collections.

Escolher uma coleçãoChoose a collection

Em geral, você deve usar coleções genéricas.In general, you should use generic collections. 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.The following table describes some common collection scenarios and the collection classes you can use for those scenarios. Se você for inexperiente com coleções genéricas, esta tabela o ajudará a escolher a coleção genérica adequada para a tarefa.If you are new to generic collections, this table will help you choose the generic collection that works the best for your task.

Eu quero…I want to… Opções de coleção genéricaGeneric collection options Opções de coleção não genéricaNon-generic collection options Opções de coleção thread-safe ou imutávelThread-safe or immutable collection options
Armazenar itens como pares chave/valor para consulta rápida por chaveStore items as key/value pairs for quick look-up by key Dictionary<TKey,TValue> Hashtable

(Um conjunto de pares chave/valor que são organizados com base no código hash da chave.)(A collection of key/value pairs that are organized based on the hash code of the key.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Itens de acesso por índiceAccess items by index List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
Usar itens primeiro a entrar, primeiro a sair (PEPS)Use items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Usar dados último a entrar, primeiro a sair (UEPS)Use data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Acessar itens em sequênciaAccess items sequentially LinkedList<T> Nenhuma recomendaçãoNo recommendation Nenhuma recomendaçãoNo recommendation
Receba notificações quando itens forem removidos da coleção ou adicionados a ela.Receive notifications when items are removed or added to the collection. (implementa INotifyPropertyChanged e INotifyCollectionChanged)(implements INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> Nenhuma recomendaçãoNo recommendation Nenhuma recomendaçãoNo recommendation
Uma coleção classificadaA sorted collection SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Um conjunto de funções matemáticasA set for mathematical functions HashSet<T>

SortedSet<T>
Nenhuma recomendaçãoNo recommendation ImmutableHashSet<T>

ImmutableSortedSet<T>

Complexidade do Algorithm de coleçõesAlgorithmic complexity of collections

Ao escolher uma classe de coleção, vale a pena considerar possíveis compensações no desempenho.When choosing a collection class, it is worth considering potential tradeoffs in performance. Use a tabela a seguir para referenciar como vários tipos de coleção mutáveis são comparados na complexidade do algoritmo para suas contrapartes imutáveis correspondentes.Use the following table to reference how various mutable collection types compare in algorithmic complexity to their corresponding immutable counterparts. Frequentemente, os tipos de coleção imutáveis são menos econômicos, mas fornecem imutabilidade, que geralmente é um benefício comparativa válido.Often immutable collection types are less performant but provide immutability - which is often a valid comparative benefit.

MutávelMutable AmortizadoAmortized Pior casoWorst Case ImutávelImmutable ComplexidadeComplexity
Stack<T>.Push O (1)O(1) O ( n )O(n) ImmutableStack<T>.Push O (1)O(1)
Queue<T>.Enqueue O (1)O(1) O ( n )O(n) ImmutableQueue<T>.Enqueue O (1)O(1)
List<T>.Add O (1)O(1) O ( n )O(n) ImmutableList<T>.Add O (log n )O(log n)
List<T>.Item[Int32] O (1)O(1) O (1)O(1) ImmutableList<T>.Item[Int32] O (log n )O(log n)
List<T>.Enumerator O ( n )O(n) O ( n )O(n) ImmutableList<T>.Enumerator O ( n )O(n)
HashSet<T>.Add, pesquisaHashSet<T>.Add, lookup O (1)O(1) O ( n )O(n) ImmutableHashSet<T>.Add O (log n )O(log n)
SortedSet<T>.Add O (log n )O(log n) O ( n )O(n) ImmutableSortedSet<T>.Add O (log n )O(log n)
Dictionary<T>.Add O (1)O(1) O ( n )O(n) ImmutableDictionary<T>.Add O (log n )O(log n)
Dictionary<T> buscaDictionary<T> lookup O (1)O(1) O (1) – ou estritamente O ( n )O(1) – or strictly O(n) ImmutableDictionary<T> buscaImmutableDictionary<T> lookup O (log n )O(log n)
SortedDictionary<T>.Add O (log n )O(log n) O ( n log n )O(n log n) ImmutableSortedDictionary<T>.Add O (log n )O(log n)

Um List<T> pode ser enumerado com eficiência usando um for loop ou um foreach loop.A List<T> can be efficiently enumerated using either a for loop or a 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.An ImmutableList<T>, however, does a poor job inside a for loop, due to the O(log n) time for its indexer. 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.Enumerating an ImmutableList<T> using a foreach loop is efficient because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. 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.An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.

Além disso, SortedSet<T> o tem a mesma complexidade que ImmutableSortedSet<T> .Additionally, SortedSet<T> has the same complexity as ImmutableSortedSet<T>. Isso porque ambos usam árvores binárias.That's because they both use binary trees. É claro que a diferença significativa é que ImmutableSortedSet<T> usa uma árvore binária imutável.The significant difference, of course, is that ImmutableSortedSet<T> uses an immutable binary tree. 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.Since ImmutableSortedSet<T> also offers a System.Collections.Immutable.ImmutableSortedSet<T>.Builder class that allows mutation, you can have both immutability and performance.

TítuloTitle DESCRIÇÃODescription
Selecionando uma classe de coleçãoSelecting a Collection Class Descreve as diferentes coleções e ajuda a selecionar uma para o seu cenário.Describes the different collections and helps you select one for your scenario.
Tipos de coleção comumente usadosCommonly Used Collection Types 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>.Describes commonly used generic and nongeneric collection types such as System.Array, System.Collections.Generic.List<T>, and System.Collections.Generic.Dictionary<TKey,TValue>.
Quando usar coleções genéricasWhen to Use Generic Collections Descreve o uso de tipos de coleção genérica.Discusses the use of generic collection types.
Comparações e classificações dentro de coleçõesComparisons and Sorts Within Collections Discute o uso de comparações de igualdade e comparações de classificação em coleções.Discusses the use of equality comparisons and sorting comparisons in collections.
Tipos de coleção classificadosSorted Collection Types Descreve as características e o desempenho de coleções classificadasDescribes sorted collections performance and characteristics
Tipos de Coleção de Tabela de Hash e DicionárioHashtable and Dictionary Collection Types Descreve os recursos de tipos de dicionário baseado em hash genérico e não genérico.Describes the features of generic and non-generic hash-based dictionary types.
Coleções com segurança de threadThread-Safe Collections 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.Describes collection types such as System.Collections.Concurrent.BlockingCollection<T> and System.Collections.Concurrent.ConcurrentBag<T> that support safe and efficient concurrent access from multiple threads.
System.Collections.ImmutableSystem.Collections.Immutable Apresenta as coleções imutáveis e fornece links para os tipos de coleção.Introduces the immutable collections and provides links to the collection types.

ReferênciaReference

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