Samlingar och datastrukturer

Liknande data kan ofta hanteras effektivare när de lagras och manipuleras som en samling. Du kan använda System.Array klassen eller klasserna i System.Collectionsnamnrymderna , System.Collections.Generic, System.Collections.Concurrentoch System.Collections.Immutable för att lägga till, ta bort och ändra antingen enskilda element eller ett intervall med element i en samling.

Det finns två huvudsakliga typer av samlingar. generiska samlingar och icke-generiska samlingar. Allmänna samlingar är typsäkra vid kompilering. Därför ger allmänna samlingar vanligtvis bättre prestanda. Allmänna samlingar accepterar en typparameter när de skapas och kräver inte att du konverterar till och från Object typen när du lägger till eller tar bort objekt från samlingen. Dessutom stöds de flesta allmänna samlingar i Windows Store-appar. Icke-generiska samlingar lagrar objekt som Object, kräver omvandling och de flesta stöds inte för Windows Store-apputveckling. Du kan dock se icke-generiska samlingar i äldre kod.

Från och med .NET Framework 4 ger samlingarna i System.Collections.Concurrent namnområdet effektiva trådsäkra åtgärder för att komma åt samlingsobjekt från flera trådar. De oföränderliga samlingsklasserna i System.Collections.Immutable namnområdet (NuGet-paketet) är trådsäkra eftersom åtgärder utförs på en kopia av den ursprungliga samlingen och den ursprungliga samlingen inte kan ändras.

Vanliga samlingsfunktioner

Alla samlingar innehåller metoder för att lägga till, ta bort eller hitta objekt i samlingen. Dessutom delar alla samlingar som direkt eller indirekt implementerar ICollection gränssnittet eller ICollection<T> gränssnittet följande funktioner:

• Möjligheten att räkna upp samlingen

  .NET-samlingar implementerar System.Collections.IEnumerable eller System.Collections.Generic.IEnumerable<T> gör det möjligt att iterera samlingen. En uppräknare kan betraktas som en flyttbar pekare till alla element i samlingen. Foreach, i -instruktionen och For Each... Nästa instruktion använder uppräknaren som exponeras av GetEnumerator metoden och döljer komplexiteten i att manipulera uppräknaren. Dessutom betraktas alla samlingar som implementerar System.Collections.Generic.IEnumerable<T> som frågebara typer och kan efterfrågas med LINQ. LINQ-frågor ger ett vanligt mönster för åtkomst till data. De är vanligtvis mer koncisa och läsbara än standardloopar foreach och tillhandahåller funktioner för filtrering, ordning och gruppering. LINQ-frågor kan också förbättra prestanda. Mer information finns i LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallell LINQ (PLINQ), Introduktion till LINQ-frågor (C#) och Grundläggande frågeåtgärder (Visual Basic).

• Möjligheten att kopiera samlingsinnehållet till en matris

  Alla samlingar kan kopieras till en matris med hjälp av metoden CopyTo . Ordningen på elementen i den nya matrisen baseras dock på den sekvens där uppräknaren returnerar dem. Den resulterande matrisen är alltid endimensionell med en lägre gräns på noll.

Dessutom innehåller många samlingsklasser följande funktioner:

• Egenskaper för kapacitet och antal

  Kapaciteten för en samling är antalet element som den kan innehålla. Antalet av en samling är antalet element som den faktiskt innehåller. Vissa samlingar döljer kapaciteten, antalet eller båda.

  De flesta samlingar expanderas automatiskt i kapacitet när den aktuella kapaciteten nås. Minnet omallokeras och elementen kopieras från den gamla samlingen till den nya. Detta minskar den kod som krävs för att använda samlingen. Samlingens prestanda kan dock påverkas negativt. För , om Count är mindre än Capacity, är det till exempel List<T>en O(1)-åtgärd att lägga till ett objekt. Om kapaciteten behöver ökas för att rymma det nya elementet blir tillägg av ett objekt en O(n)-åtgärd, där n är Count. Det bästa sättet att undvika dåliga prestanda som orsakas av flera omallokeringar är att ange den ursprungliga kapaciteten till den uppskattade storleken för samlingen.

  A BitArray är ett specialfall. Dess kapacitet är samma som dess längd, vilket är samma som dess antal.

• En konsekvent nedre gräns

  Den nedre gränsen för en samling är indexet för det första elementet. Alla indexerade samlingar i System.Collections namnrymderna har en lägre gräns på noll, vilket innebär att de är 0-indexerade. Array har en lägre gräns på noll som standard, men en annan nedre gräns kan definieras när du skapar en instans av klassen Array med hjälp Array.CreateInstanceav .

• Synkronisering för åtkomst från flera trådar (System.Collections endast klasser).

  Icke-generiska samlingstyper i System.Collections namnområdet ger viss trådsäkerhet med synkronisering. De exponeras vanligtvis via SyncRoot medlemmarna och IsSynchronized . Dessa samlingar är inte trådsäkra som standard. Om du behöver skalbar och effektiv flertrådad åtkomst till en samling kan du använda någon av klasserna i System.Collections.Concurrent namnområdet eller överväga att använda en oföränderlig samling. Mer information finns i Thread-Valv Collections(Tråd-Valv-samlingar).

Välj en samling

I allmänhet bör du använda allmänna samlingar. I följande tabell beskrivs några vanliga samlingsscenarier och de samlingsklasser som du kan använda för dessa scenarier. Om du inte har använt allmänna samlingar tidigare hjälper den här tabellen dig att välja den generiska samling som fungerar bäst för din uppgift.

Jag vill...	Allmänna samlingsalternativ	Alternativ för icke-generisk samling	Alternativ för trådsäker eller oföränderlig samling
Lagra objekt som nyckel/värde-par för snabb uppslag efter nyckel	Dictionary<TKey,TValue>	Hashtable (En samling nyckel/värde-par som är ordnade baserat på nyckelns hashkod.)	ConcurrentDictionary<TKey,TValue> ReadOnlyDictionary<TKey,TValue> ImmutableDictionary<TKey,TValue>
Komma åt objekt efter index	List<T>	Array ArrayList	ImmutableList<T> ImmutableArray
Använda objekt först in först ut (FIFO)	Queue<T>	Queue	ConcurrentQueue<T> ImmutableQueue<T>
Använda Data Last-In-First-Out (LIFO)	Stack<T>	Stack	ConcurrentStack<T> ImmutableStack<T>
Komma åt objekt sekventiellt	LinkedList<T>	Ingen rekommendation	Ingen rekommendation
Ta emot meddelanden när objekt tas bort eller läggs till i samlingen. (implementerar INotifyPropertyChanged och INotifyCollectionChanged)	ObservableCollection<T>	Ingen rekommendation	Ingen rekommendation
En sorterad samling	SortedList<TKey,TValue>	SortedList	ImmutableSortedDictionary<TKey,TValue> ImmutableSortedSet<T>
En uppsättning för matematiska funktioner	HashSet<T> SortedSet<T>	Ingen rekommendation	ImmutableHashSet<T> ImmutableSortedSet<T>

Algoritmisk komplexitet i samlingar

När du väljer en samlingsklass är det värt att överväga potentiella kompromisser i prestanda. Använd följande tabell för att referera till hur olika föränderliga samlingstyper kan jämföras i algoritmisk komplexitet med motsvarande oföränderliga motsvarigheter. Ofta är oföränderliga samlingstyper mindre högpresterande men ger oföränderlighet – vilket ofta är en giltig jämförande fördel.

Föränderlig	Amorterad	Värsta fall	Oföränderliga	Komplexitet
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>.AddSökning	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> Sökning	O(1)	O(1) – eller strikt O(n)	ImmutableDictionary<T> Sökning	O(log n)
SortedDictionary<T>.Add	O(log n)	O(n log n)	ImmutableSortedDictionary<T>.Add	O(log n)

A List<T> kan effektivt räknas upp med hjälp av antingen en for loop eller en foreach loop. Ett ImmutableList<T>, men gör ett dåligt jobb i en for loop, på grund av O(log n) tid för dess indexerare. Att räkna upp en ImmutableList<T> använda en foreach loop är effektivt eftersom ImmutableList<T> använder ett binärt träd för att lagra sina data i stället för en enkel matris som List<T> använder. En matris kan indexeras mycket snabbt till, medan ett binärt träd måste gå nedåt tills noden med önskat index hittas.

Dessutom SortedSet<T> har samma komplexitet som ImmutableSortedSet<T>. Det beror på att båda använder binära träd. Den stora skillnaden är naturligtvis att ImmutableSortedSet<T> använder ett oföränderligt binärt träd. Eftersom ImmutableSortedSet<T> även erbjuder en System.Collections.Immutable.ImmutableSortedSet<T>.Builder klass som tillåter mutation kan du ha både oföränderlighet och prestanda.

Relaterade ämnen

Rubrik	Beskrivning
Välja en samlingsklass	Beskriver de olika samlingarna och hjälper dig att välja en för ditt scenario.
Vanliga samlingstyper	Beskriver vanliga generiska och icke-generiska samlingstyper som System.Array, System.Collections.Generic.List<T>och System.Collections.Generic.Dictionary<TKey,TValue>.
När du ska använda allmänna samlingar	Beskriver användningen av generiska samlingstyper.
Jämförelser och sortering i samlingar	Diskuterar användningen av likhetsjämförelser och sorteringsjämförelser i samlingar.
Sorterade samlingstyper	Beskriver prestanda och egenskaper för sorterade samlingar
Samlingstyper för hashtable och ordlista	Beskriver funktionerna i generiska och icke-generiska hash-baserade ordlistetyper.
Tråd-Valv-samlingar	Beskriver samlingstyper som System.Collections.Concurrent.BlockingCollection<T> och System.Collections.Concurrent.ConcurrentBag<T> som stöder säker och effektiv samtidig åtkomst från flera trådar.
System.Collections.Immutable	Introducerar oföränderliga samlingar och innehåller länkar till samlingstyperna.

Referens

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