Kolekce a datové struktury

Podobná data je často možné zpracovávat efektivněji, když jsou uložená a manipulována jako kolekce. 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.

Existují dva hlavní typy kolekcí; Obecné kolekce a jiné než obecné kolekce. Obecné kolekce jsou typově bezpečné v době kompilace. Z tohoto důvodu obecné kolekce obvykle nabízejí lepší výkon. 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. kromě toho je v aplikacích Windows storu podporována většina obecných kolekcí. neobecné kolekce ukládají položky jako Object , vyžadovat přetypování a většina nejsou podporované pro vývoj aplikací Windows storu. V starším kódu ale můžete vidět neobecné kolekce.

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. neměnné třídy kolekce v System.Collections.Immutable oboru názvů (NuGet balíček) jsou podstatně bezpečné pro přístup z více vláken, protože operace se provádějí na kopii původní kolekce a původní kolekce nelze upravovat.

Společné funkce kolekcí

Všechny kolekce poskytují metody pro přidávání, odebírání a hledání položek v kolekci. Kromě toho všechny kolekce, které přímo nebo nepřímo implementují ICollection rozhraní nebo ICollection<T> rozhraní sdílejí tyto funkce:

Kromě toho mnoho tříd kolekcí obsahuje následující funkce:

  • Vlastnosti kapacity a počtu

    Kapacita kolekce je počet prvků, které může obsahovat. Počet prvků v kolekci je počet prvků, které ve skutečnosti obsahují. Některé kolekce skrývají kapacitu nebo počet nebo obojí.

    Většina kolekcí se při dosažení aktuální kapacity automaticky zvětšuje v kapacitě. Paměť je znovu přidělena a prvky jsou zkopírovány z staré kolekce do nové. Tím se snižuje kód potřebný k použití kolekce; výkon kolekce však může negativně ovlivnit. Například pro List<T> , pokud Count je menší než Capacity , přidání položky je operace o (1). 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 . 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.

    BitArrayJe zvláštní případ, jeho kapacita je stejná jako jeho délka, která je stejná jako počet.

  • Konzistentní dolní mez

    Dolní mez kolekce je index jeho prvního prvku. Všechny indexované kolekce v System.Collections oborech názvů mají dolní mez nula, což znamená, že jsou 0 – indexované. 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 .

  • Synchronizace pro přístup z více vláken ( System.Collections pouze třídy).

    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. Ve výchozím nastavení nejsou tyto kolekce bezpečné pro přístup z více vláken. 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. další informace najdete v tématu kolekce Sejf vláken.

Zvolit kolekci

Obecně byste měli použít obecné kolekce. 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. 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.

Chci... Možnosti Obecné kolekce Možnosti bez obecné kolekce Možnosti bezpečného a neměnného přístupu k vláknům
Ukládat položky jako páry klíč/hodnota pro rychlé vyhledání podle klíče Dictionary<TKey,TValue> Hashtable

(Kolekce párů klíč/hodnota, které jsou uspořádány na základě hash kódu klíče.)
ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Přístup k položkám podle indexu List<T> Array

ArrayList
ImmutableList<T>

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

ImmutableQueue<T>
Použití dat Last-in-first-out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Sekvenční přístup k položkám LinkedList<T> Bez doporučení Bez doporučení
Dostávat oznámení, když se položky odeberou nebo přidají do kolekce (implementuje INotifyPropertyChanged a INotifyCollectionChanged ) ObservableCollection<T> Bez doporučení Bez doporučení
Seřazená kolekce SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Sada pro matematické funkce HashSet<T>

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

ImmutableSortedSet<T>

Algoritmy složitosti kolekcí

Při výběru třídy kolekceje vhodné zvážit potenciální kompromisy ve výkonu. 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. Často neměnné typy kolekcí jsou méně výkonné, ale poskytují neměnnosti, což je často platná srovnávací výhoda.

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

List<T>Můžete efektivně vytvořit výčet pomocí for smyčky nebo foreach smyčky. ImmutableList<T>Ale v rámci smyčky se nejedná o špatnou úlohu for kvůli času o (protokolu n ) pro jeho 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í. 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.

Navíc SortedSet<T> má stejnou složitost jako ImmutableSortedSet<T> . To je proto, že používají binární stromy. Významným rozdílem samozřejmě je, že ImmutableSortedSet<T> používá neproměnlivý binární strom. 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.

Nadpis Popis
Výběr třídy kolekce V této části najdete popis různých kolekcí a pomůže vám to vybrat pro váš scénář.
Běžně používané typy kolekcí 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> .
Kdy použít obecné kolekce Popisuje použití obecných typů kolekcí.
Porovnání a řazení v rámci kolekcí Popisuje použití porovnávání rovnosti a porovnávání řazení v kolekcích.
Typy seřazených kolekcí Popisuje výkon a charakteristiky seřazených kolekcí.
Typy kolekce Hashtable a Dictionary Popisuje funkce obecných a neobecných typů slovníků založených na hodnotách hash.
kolekce Sejf vláken 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.
System. Collections. unmutable Zavádí neměnné kolekce a poskytuje odkazy na typy kolekcí.

Reference

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