Sdílet prostřednictvím

Kolekce a datové struktury

Podobná data je často možné zpracovávat efektivněji při ukládání a manipulaci jako s kolekcí. Můžete použít třídu System.Array nebo třídy v jmenných prostorech System.Collections, System.Collections.Generic, System.Collections.Concurrent a System.Collections.Immutable k přidání, odebrání a úpravě jednotlivých prvků nebo rozsahu prvků v kolekci.

Existují dva hlavní typy kolekcí; obecné kolekce a jiné než obecné kolekce. Obecné kolekce jsou v době kompilace typově bezpečné. Z tohoto důvodu obecné kolekce obvykle nabízejí lepší výkon. Obecné kolekce přijímají parametr typu při jejich vytváření. Při přidávání nebo odebírání položek z kolekce nevyžadují přetypování na a z typu Object. Kromě toho se v aplikacích pro Windows Store podporuje většina obecných kolekcí. Kolekce, které nejsou obecné, 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 zobrazovat ne generické kolekce.

V rozhraní .NET Framework 4 a novějších verzích 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ů (balíček NuGet) 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 upravit.

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:

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 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 zvětší. Paměť je relokovaná a prvky se zkopírují ze staré kolekce do nové. Tento návrh snižuje 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>Count 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, stane se přidáním položky operace O(n), kde n je Count. Nejlepším způsobem, jak se vyhnout nízkému výkonu způsobenému více relokací, je nastavit počáteční kapacitu tak, aby byla odhadovaná velikost kolekce.

    A BitArray je zvláštní případ; její kapacita je stejná jako její délka, což je stejné jako 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í hranici nula, což znamená, že jsou indexované od nuly. Array má ve výchozím nastavení dolní mez, která je nula, ale při vytváření instance třídy Array pomocí Array.CreateInstance lze definovat jinou dolní mez.

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

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

Vyberte kolekci

Obecně 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 pro tyto scénáře použít. Pokud s obecnými kolekcemi začínáte, pomůže vám následující tabulka zvolit obecnou kolekci, která bude pro vaši úlohu nejvhodnější:

Chci... Obecné možnosti kolekce Možnosti kolekce bez generické povahy Možnosti kolekce bezpečné pro přístup z více vláken 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žijte položky metodou první dovnitř, první ven (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Použití dat last-in-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Přístup k položkám postupně LinkedList<T> Žádné doporučení Žádné doporučení
Přijímat oznámení, když se položky odeberou nebo přidají 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. V následující tabulce se dozvíte, jak různé proměnlivé typy 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ý Komplexnost
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(logaritmus n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(logaritmus n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, vyhledat O(1) O(n) ImmutableHashSet<T>.Add O(logaritmus n)
SortedSet<T>.Add O(logaritmus n) O(n) ImmutableSortedSet<T>.Add O(logaritmus n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(logaritmus n)
Dictionary<T> vyhledat O(1) O(1) – nebo přísně O(n) ImmutableDictionary<T> vyhledat O(logaritmus n)
SortedDictionary<T>.Add O(logaritmus n) O(n protokol n) ImmutableSortedDictionary<T>.Add O(logaritmus n)

List<T> lze efektivně vyčíslit pomocí smyčky for nebo foreach. Nicméně ImmutableList<T>, dělá špatnou úlohu uvnitř for smyčky kvůli času O(log n) pro jeho indexer. Procházení ImmutableList<T> pomocí smyčky foreach je efektivní, protože ImmutableList<T> používá binární strom k ukládání dat namísto pole, které používá List<T>. Pole lze rychle indexovat do, zatímco binární strom musí být procházený dolů, dokud se nenajde uzel s požadovaným indexem.

Kromě toho SortedSet<T> má stejnou složitost, jako ImmutableSortedSet<T> když obě používají binární stromy. Významným rozdílem je, že ImmutableSortedSet<T> používá neměnný binární strom. ImmutableSortedSet<T> také nabízí třídu System.Collections.Immutable.ImmutableSortedSet<T>.Builder, která umožňuje mutaci, takže můžete zajistit jak neměnnost, tak i výkon.

Titulek Popis
Výběr třídy kolekce Popisuje různé kolekce a pomůže vám vybrat jednu z kolekcí pro váš scénář.
Běžně používané typy kolekcí Popisuje běžně používané generické a neobecné typy kolekcí, jako jsou 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 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 kolekcí Hashtable a Dictionary Popisuje funkce obecných a ne generických typů slovníků založených na hodnotě hash.
Thread-Safe kolekce Popisuje typy kolekcí, 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.Immutable Představuje neměnné kolekce a poskytuje odkazy na typy kolekcí.

Odkazy

  • Last updated on