Kolekce a datové strukturyCollections and Data Structures

Podobná data je často možné zpracovávat efektivněji, když jsou uložená a manipulována jako kolekce.Similar data can often be handled more efficiently when stored and manipulated as a collection. Můžete použít System.Array třídu nebo třídy v System.Collections System.Collections.Generic System.Collections.Concurrent System.Collections.Immutable oborech názvů,, a pro přidání, odebrání a úpravu buď jednotlivých prvků, nebo rozsah prvků v kolekci.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.

Existují dva hlavní typy kolekcí; Obecné kolekce a jiné než obecné kolekce.There are two main types of collections; generic collections and non-generic collections. Obecné kolekce jsou typově bezpečné v době kompilace.Generic collections are type-safe at compile time. Z tohoto důvodu obecné kolekce obvykle nabízejí lepší výkon.Because of this, generic collections typically offer better performance. Obecné kolekce přijímají parametr typu při jejich sestavení a nevyžadují, abyste přetypování do a z Object typu při přidávání nebo odebírání položek z kolekce.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. Kromě toho jsou v aplikacích pro Windows Store podporovány většinou obecné kolekce.In addition, most generic collections are supported in Windows Store apps. Neobecné kolekce ukládají položky jako Object , vyžadovat přetypování a většina nejsou podporované pro vývoj aplikací pro Windows Store.Non-generic collections store items as Object, require casting, and most are not supported for Windows Store app development. V starším kódu ale můžete vidět neobecné kolekce.However, you may see non-generic collections in older code.

Počínaje .NET Framework 4 kolekce v System.Collections.Concurrent oboru názvů poskytují efektivní operace bezpečné pro přístup z více vláken pro přístup k položkám kolekce z více vláken.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. Neměnné třídy kolekce v System.Collections.Immutable oboru názvů (balíček NuGet) jsou podstatou bezpečné pro přístup z více vláken, protože operace jsou prováděny na kopii původní kolekce a původní kolekci nelze změnit.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.

Společné funkce kolekcíCommon collection features

Všechny kolekce poskytují metody pro přidávání, odebírání a hledání položek v kolekci.All collections provide methods for adding, removing, or finding items in the collection. Kromě toho všechny kolekce, které přímo nebo nepřímo implementují ICollection rozhraní nebo ICollection<T> rozhraní sdílejí tyto funkce:In addition, all collections that directly or indirectly implement the ICollection interface or the ICollection<T> interface share these features:

Kromě toho mnoho tříd kolekcí obsahuje následující funkce:In addition, many collection classes contain the following features:

  • Vlastnosti kapacity a počtuCapacity and Count properties

    Kapacita kolekce je počet prvků, které může obsahovat.The capacity of a collection is the number of elements it can contain. Počet prvků v kolekci je počet prvků, které ve skutečnosti obsahují.The count of a collection is the number of elements it actually contains. Některé kolekce skrývají kapacitu nebo počet nebo obojí.Some collections hide the capacity or the count or both.

    Většina kolekcí se při dosažení aktuální kapacity automaticky zvětšuje v kapacitě.Most collections automatically expand in capacity when the current capacity is reached. Paměť je znovu přidělena a prvky jsou zkopírovány z staré kolekce do nové.The memory is reallocated, and the elements are copied from the old collection to the new one. Tím se snižuje kód potřebný k použití kolekce; výkon kolekce však může negativně ovlivnit.This reduces the code required to use the collection; however, the performance of the collection might be negatively affected. Například pro List<T> , pokud Count je menší než Capacity , přidání položky je operace o (1).For example, for List<T>, if Count is less than Capacity, adding an item is an O(1) operation. Pokud je potřeba zvýšit kapacitu tak, aby vyhovovala novému prvku, přidání položky se změní na operaci O ( n ), kde n je 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. Nejlepším způsobem, jak zabránit špatnému výkonu způsobenému více přerozdělením, je nastavit počáteční kapacitu na odhadovanou velikost kolekce.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.

    BitArrayJe zvláštní případ, jeho kapacita je stejná jako jeho délka, která je stejná jako počet.A BitArray is a special case; its capacity is the same as its length, which is the same as its count.

  • Konzistentní dolní mezA consistent lower bound

    Dolní mez kolekce je index jeho prvního prvku.The lower bound of a collection is the index of its first element. Všechny indexované kolekce v System.Collections oborech názvů mají dolní mez nula, což znamená, že jsou 0 – indexované.All indexed collections in the System.Collections namespaces have a lower bound of zero, meaning they are 0-indexed. Array má dolní mez nula ve výchozím nastavení, ale při vytváření instance třídy Array pomocí je možné definovat jinou dolní mez 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.

  • Synchronizace pro přístup z více vláken ( System.Collections pouze třídy).Synchronization for access from multiple threads (System.Collections classes only).

    Neobecné typy kolekce v System.Collections oboru názvů poskytují určitou bezpečnost vlákna se synchronizací, která je obvykle vystavena prostřednictvím SyncRoot IsSynchronized členů a.Non-generic collection types in the System.Collections namespace provide some thread safety with synchronization; typically exposed through the SyncRoot and IsSynchronized members. Ve výchozím nastavení nejsou tyto kolekce bezpečné pro přístup z více vláken.These collections are not thread-safe by default. Pokud vyžadujete škálovatelný a efektivní vícevláknový přístup ke kolekci, použijte jednu z tříd v System.Collections.Concurrent oboru názvů nebo zvažte použití neměnné kolekce.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. Další informace najdete v tématu kolekce bezpečnépro přístup z více vláken.For more information, see Thread-Safe Collections.

Zvolit kolekciChoose a collection

Obecně byste měli použít obecné kolekce.In general, you should use generic collections. Následující tabulka popisuje některé běžné scénáře shromažďování a třídy kolekcí, které můžete pro tyto scénáře použít.The following table describes some common collection scenarios and the collection classes you can use for those scenarios. Pokud s obecnými kolekcemi začínáte, tato tabulka vám pomůže vybrat obecnou kolekci, která bude pro váš úkol fungovat nejlépe.If you are new to generic collections, this table will help you choose the generic collection that works the best for your task.

Chci...I want to… Možnosti Obecné kolekceGeneric collection options Možnosti bez obecné kolekceNon-generic collection options Možnosti bezpečného a neměnného přístupu k vláknůmThread-safe or immutable collection options
Ukládat položky jako páry klíč/hodnota pro rychlé vyhledání podle klíčeStore items as key/value pairs for quick look-up by key Dictionary<TKey,TValue> Hashtable

(Kolekce párů klíč/hodnota, které jsou uspořádány na základě hash kódu klíče.)(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>
Přístup k položkám podle indexuAccess items by index List<T> Array

ArrayList
ImmutableList<T>

ImmutableArray
Použití položek first-in-first-out (FIFO)Use items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Použití dat Last-in-first-out (LIFO)Use data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Sekvenční přístup k položkámAccess items sequentially LinkedList<T> Bez doporučeníNo recommendation Bez doporučeníNo recommendation
Dostávat oznámení, když se položky odeberou nebo přidají do kolekceReceive notifications when items are removed or added to the collection. (implementuje INotifyPropertyChanged a INotifyCollectionChanged )(implements INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> Bez doporučeníNo recommendation Bez doporučeníNo recommendation
Seřazená kolekceA sorted collection SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Sada pro matematické funkceA set for mathematical functions HashSet<T>

SortedSet<T>
Bez doporučeníNo recommendation ImmutableHashSet<T>

ImmutableSortedSet<T>

Algoritmy složitosti kolekcíAlgorithmic complexity of collections

Při výběru třídy kolekceje vhodné zvážit potenciální kompromisy ve výkonu.When choosing a collection class, it is worth considering potential tradeoffs in performance. Použijte následující tabulku, chcete-li odkazovat na to, jak různé proměnlivé typy kolekcí porovnávají v algoritmech složitosti s odpovídajícími neproměnlivými protějšky.Use the following table to reference how various mutable collection types compare in algorithmic complexity to their corresponding immutable counterparts. Často neměnné typy kolekcí jsou méně výkonné, ale poskytují neměnnosti, což je často platná srovnávací výhoda.Often immutable collection types are less performant but provide immutability - which is often a valid comparative benefit.

MěnitelnéMutable AmortizovanéAmortized Nejhorší případWorst Case NeměnnéImmutable SložitostComplexity
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 (protokol n )O(log n)
List<T>.Item[Int32] O (1)O(1) O (1)O(1) ImmutableList<T>.Item[Int32] O (protokol 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, vyhledáváníHashSet<T>.Add, lookup O (1)O(1) O ( n )O(n) ImmutableHashSet<T>.Add O (protokol n )O(log n)
SortedSet<T>.Add O (protokol n )O(log n) O ( n )O(n) ImmutableSortedSet<T>.Add O (protokol n )O(log n)
Dictionary<T>.Add O (1)O(1) O ( n )O(n) ImmutableDictionary<T>.Add O (protokol n )O(log n)
Dictionary<T> prohledáváníDictionary<T> lookup O (1)O(1) O (1) – nebo striktně O ( n )O(1) – or strictly O(n) ImmutableDictionary<T> prohledáváníImmutableDictionary<T> lookup O (protokol n )O(log n)
SortedDictionary<T>.Add O (protokol n )O(log n) O ( n protokol n )O(n log n) ImmutableSortedDictionary<T>.Add O (protokol n )O(log n)

List<T>Můžete efektivně vytvořit výčet pomocí for smyčky nebo foreach smyčky.A List<T> can be efficiently enumerated using either a for loop or a foreach loop. ImmutableList<T>Ale v rámci smyčky se nejedná o špatnou úlohu for kvůli času o (protokolu n ) pro jeho indexer.An ImmutableList<T>, however, does a poor job inside a for loop, due to the O(log n) time for its indexer. Výčet ImmutableList<T> pomocí foreach smyčky je efektivní, protože ImmutableList<T> používá binární strom k ukládání dat místo jednoduchého pole, jako je například List<T> použití.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. Pole může být velmi rychle indexované do, zatímco binární strom musí být vás provedl dolů, dokud se nenajde uzel s požadovaným indexem.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.

Navíc SortedSet<T> má stejnou složitost jako ImmutableSortedSet<T> .Additionally, SortedSet<T> has the same complexity as ImmutableSortedSet<T>. To je proto, že používají binární stromy.That's because they both use binary trees. Významným rozdílem samozřejmě je, že ImmutableSortedSet<T> používá neproměnlivý binární strom.The significant difference, of course, is that ImmutableSortedSet<T> uses an immutable binary tree. Vzhledem ImmutableSortedSet<T> k tomu System.Collections.Immutable.ImmutableSortedSet<T>.Builder , že nabízí také třídu, která umožňuje mutace, můžete mít neměnnosti i výkon.Since ImmutableSortedSet<T> also offers a System.Collections.Immutable.ImmutableSortedSet<T>.Builder class that allows mutation, you can have both immutability and performance.

NadpisTitle PopisDescription
Výběr třídy kolekceSelecting a Collection Class V této části najdete popis různých kolekcí a pomůže vám to vybrat pro váš scénář.Describes the different collections and helps you select one for your scenario.
Běžně používané typy kolekcíCommonly Used Collection Types Popisuje běžně používané obecné a neobecné typy kolekce, například System.Array , System.Collections.Generic.List<T> a 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>.
Kdy použít obecné kolekceWhen to Use Generic Collections Popisuje použití obecných typů kolekcí.Discusses the use of generic collection types.
Porovnání a řazení v rámci kolekcíComparisons and Sorts Within Collections Popisuje použití porovnávání rovnosti a porovnávání řazení v kolekcích.Discusses the use of equality comparisons and sorting comparisons in collections.
Typy seřazených kolekcíSorted Collection Types Popisuje výkon a charakteristiky seřazených kolekcí.Describes sorted collections performance and characteristics
Typy kolekce Hashtable a DictionaryHashtable and Dictionary Collection Types Popisuje funkce obecných a neobecných typů slovníků založených na hodnotách hash.Describes the features of generic and non-generic hash-based dictionary types.
Kolekce bezpečné pro přístup z více vlákenThread-Safe Collections Popisuje typy kolekce, jako jsou System.Collections.Concurrent.BlockingCollection<T> a System.Collections.Concurrent.ConcurrentBag<T> , které podporují bezpečný a efektivní souběžný přístup z více vláken.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. unmutableSystem.Collections.Immutable Zavádí neměnné kolekce a poskytuje odkazy na typy kolekcí.Introduces the immutable collections and provides links to the collection types.

ReferenceReference

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