Kolekce a datové struktury

  • Článek

Podobná data se často dají efektivněji zpracovávat při ukládání a manipulaci s nimi jako s kolekcí. Třídu nebo třídy v sadě System.Collections, , System.Collections.Generic, System.Collections.Concurrenta System.Collections.Immutable obory názvů můžete použít System.Array k přidání, odebrání a úpravě jednotlivých prvků nebo rozsah prvků v kolekci.

Existují dva hlavní typy kolekcí; obecné kolekce a ne generické kolekce. Obecné kolekce jsou v době kompilace bezpečné. Z tohoto důvodu obecné kolekce obvykle nabízejí lepší výkon. Obecné kolekce přijímají parametr typu, když jsou vytvořené a nevyžadují přetypování do a z Object typu při přidávání nebo odebírání položek z kolekce. Kromě toho se většina obecných kolekcí podporuje v aplikacích pro Windows Store. Ne generické kolekce ukládají položky jako Object, vyžadují přetypování a většina z nich není podporovaná pro vývoj aplikací pro Windows Store. Ve starším kódu se ale můžou zobrazit jiné než obecné kolekce.

Počínaje .NET Framework 4 poskytují kolekce v System.Collections.Concurrent oboru názvů efektivní operace bezpečné 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íčku) jsou ze své podstaty bezpečné pro vlákna, protože operace se provádějí na kopii původní kolekce a původní kolekci nelze změnit.

Běžné funkce kolekce

Všechny kolekce poskytují metody pro přidávání, odebírání nebo 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:

Mnoho tříd kolekce navíc obsahuje následující funkce:

  • Vlastnosti kapacity a počtu

    Kapacita kolekce je počet prvků, které může obsahovat. Počet kolekcí je počet prvků, které skutečně obsahuje. Některé kolekce skryjí kapacitu nebo počet nebo obojí.

    Při dosažení aktuální kapacity se většina kolekcí automaticky rozšíří. Paměť se relokuje a prvky se zkopírují ze staré kolekce do nové. Tím se sníží kód potřebný k použití kolekce; Výkon kolekce však může být negativně ovlivněný. Pokud je například List<T>menší než Capacity, Count přidání položky je operace O(1). Pokud je potřeba zvýšit kapacitu tak, aby vyhovovala novému prvku, stane se přidáním položky operace O(n), kde n je Count. Nejlepší způsob, jak se vyhnout nízkému výkonu způsobenému více relokacemi, je nastavit počáteční kapacitu tak, aby byla odhadovaná velikost kolekce.

    A BitArray je zvláštní případ; jeho kapacita je stejná jako její délka, což je stejné jako jeho počet.

  • Konzistentní dolní mez

    Dolní mez kolekce je index prvního prvku. Všechny indexované kolekce v System.Collections oborech názvů mají dolní mez nuly, což znamená, že jsou indexované 0. Array má ve výchozím nastavení dolní mez nuly, ale při vytváření instance třídyArray.CreateInstanceArray lze definovat jinou dolní mez.

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

    Ne generické typy kolekcí v System.Collections oboru názvů poskytují určitou bezpečnost vláken se synchronizací, obvykle vystavené prostřednictvím SyncRoot členů a IsSynchronized členů. Tyto kolekce nejsou ve výchozím nastavení bezpečné pro vlákna. Pokud potřebujete škálovatelný a efektivní přístup k kolekci s více vlákny, 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.

Volba kolekce

Obecně platí, že byste měli používat obecné kolekce. Následující tabulka popisuje některé běžné scénáře kolekce a třídy kolekcí, které můžete použít pro tyto scénáře. Pokud s obecnými kolekcemi začínáte, pomůže vám tato tabulka vybrat obecnou kolekci, která nejlépe vyhovuje vašemu úkolu.

Chci... Obecné možnosti kolekce Jiné než obecné možnosti kolekce Možnosti kolekce bezpečné pro vlákno nebo neměnné
Ukládání položek jako párů klíč/hodnota pro rychlé vyhledávání podle klíče Dictionary<TKey,TValue> Hashtable

(Kolekce párů klíč/hodnota uspořádaných na základě kódu hash 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 prvního v prvním outu (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Použití funkce LIFO (Last-In-First-Out) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Přístup k položkám sekvenčním způsobem LinkedList<T> Žádné doporučení Žádné doporučení
Příjem oznámení, když jsou položky odebrány nebo přidány do kolekce. (implementuje INotifyPropertyChanged a INotifyCollectionChanged) ObservableCollection<T> Žádné doporučení Žádné doporučení
Seřazená kolekce SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

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

SortedSet<T>		 Žádné doporučení ImmutableHashSet<T>

ImmutableSortedSet<T>

Algoritmická složitost kolekcí

Při výběru třídy kolekce je vhodné zvážit potenciální kompromisy v výkonu. Pomocí následující tabulky můžete odkazovat na to, jak různé typy mutable kolekcí porovnávají algoritmickou složitost s odpovídajícími neměnnými protějšky. Často neměnné typy kolekcí jsou méně výkonné, ale poskytují neměnnost – 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(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>.AddVyhledávání 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> Vyhledávání O(1) O(1) – nebo přísně O(n) ImmutableDictionary<T> Vyhledávání O(log n)
SortedDictionary<T>.Add O(log n) O(n protokol n) ImmutableSortedDictionary<T>.Add O(log n)

A List<T> lze efektivně vytvořit výčet pomocí for smyčky nebo foreach smyčky. Nicméně ImmutableList<T>, dělá špatnou for úlohu uvnitř smyčky, protože čas O(log n) pro jeho indexer. ImmutableList<T> Výčet použití 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 List<T> je použití. Pole může být velmi rychle indexováno, zatímco binární strom musí být procházený dolů, dokud se nenajde uzel s požadovaným indexem.

SortedSet<T> Navíc má stejnou složitost jako ImmutableSortedSet<T>. To je proto, že oba používají binární stromy. Významným rozdílem je samozřejmě použití ImmutableSortedSet<T> neměnného binárního stromu. Vzhledem k tomu ImmutableSortedSet<T> , že nabízí System.Collections.Immutable.ImmutableSortedSet<T>.Builder také třídu, která umožňuje mutaci, můžete mít neměnnost i výkon.

Nadpis Popis
Výběr třídy kolekce Popisuje různé kolekce a pomůže vám vybrat jednu pro váš scénář.
Běžně používané typy kolekcí Popisuje běžně používané obecné a negenerické typy kolekcí, jako jsou System.Array, a System.Collections.Generic.Dictionary<TKey,TValue>System.Collections.Generic.List<T>.
Kdy použít obecné kolekce Popisuje použití obecných typů kolekcí.
Porovnání a řazení v kolekcích Popisuje použití porovnání rovnosti a řazení v kolekcích.
Seřazené typy kolekcí Popisuje výkon a charakteristiky seřazených kolekcí.
Typy kolekce Hashtable a Dictionary Popisuje funkce obecných a ne generických typů slovníků založených na hodnotě hash.
Kolekce Sejf vláken Popisuje typy kolekcí, jako System.Collections.Concurrent.BlockingCollection<T>System.Collections.Concurrent.ConcurrentBag<T> jsou a které podporují bezpečný a efektivní souběžný přístup z více vláken.
System.Collections.Immutable Představuje 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