Raccolte e strutture di dati

  • Articolo

Dati simili possono spesso essere gestiti in modo più efficiente quando memorizzati e modificati come una raccolta. È possibile usare la System.Array classe o le classi negli System.Collectionsspazi dei nomi , System.Collections.Generic, System.Collections.Concurrente System.Collections.Immutable per aggiungere, rimuovere e modificare singoli elementi o un intervallo di elementi in una raccolta.

Esistono due tipi principali di raccolte: raccolte generiche e raccolte non generiche. Le raccolte generiche sono indipendenti dai tipi in fase di compilazione. Per questo motivo, le raccolte generiche offrono in genere prestazioni migliori. Le raccolte generiche accettano un parametro di tipo quando vengono costruite e non è necessario eseguire il cast da e verso il tipo Object quando si aggiungono o rimuovono elementi dalla raccolta. Inoltre, la maggior parte delle raccolte generiche è supportata nelle app dello Store Windows. Le raccolte non generiche archiviano gli elementi come Object, richiedono il cast e la maggior parte non è supportata per lo sviluppo di app dello Store Windows. Tuttavia, si possono vedere raccolte non generiche nel codice precedente.

A partire da .NET Framework 4, le raccolte nello spazio dei nomi forniscono operazioni thread-safe efficienti per l'accesso System.Collections.Concurrent agli elementi della raccolta da più thread. Le classi di raccolta non modificabili nello System.Collections.Immutable spazio dei nomi (pacchetto NuGet) sono intrinsecamente thread-safe perché le operazioni vengono eseguite su una copia dell'insieme originale e la raccolta originale non può essere modificata.

Funzionalità comuni delle raccolte

Tutte le raccolte forniscono metodi per aggiungere, rimuovere o trovare elementi nella raccolta. In aggiunta, tutte le raccolte che implementano direttamente o indirettamente l'interfaccia ICollection o l'interfaccia ICollection<T> condividono le funzionalità seguenti:

Inoltre, molte classi di raccolte contengono le seguenti funzionalità:

  • Proprietà capacità e conteggio

    La capacità di una raccolta è il numero di elementi che può contenere. Il conteggio di una raccolta è il numero di elementi che contiene effettivamente. Alcune raccolte nascondono la capacità o il conteggio oppure entrambi.

    La capacità della maggior parte delle raccolte si espande automaticamente quando viene raggiunta la capacità corrente. La memoria viene riallocata e gli elementi vengono copiati dalla raccolta precedente a quella nuova. Ciò riduce la quantità di codice necessario per usare la raccolta. Tuttavia, le prestazioni della raccolta possono essere influenzate negativamente. Ad esempio, per List<T>, se Count è minore di , l'aggiunta di Capacityun elemento è un'operazione O(1). Se la capacità deve essere aumentata per ospitare il nuovo elemento, l'aggiunta di un elemento diventa un'operazione O(n), dove n è Count. Il modo migliore per evitare una riduzione delle prestazioni causata da più riallocazioni consiste nell'impostare la capacità iniziale sulla dimensione prevista della raccolta.

    Un BitArray è un caso speciale: la sua capacità corrisponde alla sua lunghezza, che corrisponde al relativo conteggio.

  • Un limite inferiore coerente

    Il limite inferiore di una raccolta è l'indice del primo elemento. Tutte le raccolte indicizzate negli spazi dei nomi System.Collections hanno un limite inferiore pari a zero, ossia possono essere indicizzate da 0. Array ha un limite inferiore di zero per impostazione predefinita, ma è possibile definire un limite inferiore diverso quando si crea un'istanza della classe Array usando Array.CreateInstance.

  • Sincronizzazione per l'accesso da più thread (System.Collections solo classi).

    I tipi di raccolta non generici nello System.Collections spazio dei nomi forniscono una sicurezza del thread con la sincronizzazione, in genere esposti tramite i SyncRoot membri e IsSynchronized . Queste raccolte non sono thread-safe per impostazione predefinita. Se si richiede un accesso multithreading scalabile ed efficiente a una raccolta, usare una delle classi nello spazio dei nomi System.Collections.Concurrent o considerare l'uso di una raccolta non modificabile. Per altre informazioni, vedere Raccolte thread-safe.

Scegliere una raccolta

In generale, è necessario usare raccolte generiche. Nella tabella seguente vengono descritti alcuni scenari comuni di raccolta e le classi di raccolta che è possibile usare per gli scenari. Se si ha già familiarità con le raccolte generiche, questa tabella consente di scegliere la raccolta generica più adatta alla propria attività.

Si desidera... Opzioni di raccolta generica Opzioni di raccolta non generica Opzioni di raccolta thread-safe o non modificabile
Archiviare gli elementi come coppie chiave/valore per la ricerca rapida dalla chiave Dictionary<TKey,TValue> Hashtable

(Una raccolta di coppie chiave/valore che sono organizzate in base al codice hash della chiave).		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Accedere agli elementi in base all'indice List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Usare gli elementi first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Usare i dati Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Accedere agli elementi in sequenza LinkedList<T> Nessuna raccomandazione Nessuna raccomandazione
Ricevere notifiche quando gli elementi vengono rimossi o aggiunti alla raccolta. (implementa INotifyPropertyChanged e INotifyCollectionChanged) ObservableCollection<T> Nessuna raccomandazione Nessuna raccomandazione
Una raccolta ordinata SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Un set di funzioni matematiche HashSet<T>

SortedSet<T>		 Nessuna raccomandazione ImmutableHashSet<T>

ImmutableSortedSet<T>

Complessità algoritmica delle raccolte

Quando si sceglie una classe di raccolta, vale la pena considerare potenziali compromessi nelle prestazioni. Usare la tabella seguente per fare riferimento al confronto tra vari tipi di raccolta modificabili nella complessità algoritmica alle corrispondenti controparti non modificabili. Spesso i tipi di raccolta non modificabili sono meno efficienti, ma forniscono immutabili , che spesso è un vantaggio comparativo valido.

Modificabile Ammortizzato Caso peggiore Non modificabile Complessità
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>.AddRicerca 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> Ricerca O(1) O(1) – o rigorosamente O(n) ImmutableDictionary<T> Ricerca O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

Un oggetto List<T> può essere enumerato in modo efficiente usando un for ciclo o un foreach ciclo. Un ImmutableList<T>oggetto , tuttavia, esegue un processo povero all'interno di un for ciclo, a causa del tempo di O(log n) per il relativo indicizzatore. L'enumerazione di un ImmutableList<T> ciclo tramite un foreach ciclo è efficiente perché ImmutableList<T> usa un albero binario per archiviare i dati anziché una matrice semplice come List<T> gli usi. Una matrice può essere indicizzata molto rapidamente in, mentre un albero binario deve essere ridotto fino a quando non viene trovato il nodo con l'indice desiderato.

Inoltre, SortedSet<T> ha la stessa complessità di ImmutableSortedSet<T>. Questo perché usano entrambi alberi binari. La differenza significativa, naturalmente, è che ImmutableSortedSet<T> usa un albero binario non modificabile. Poiché ImmutableSortedSet<T> offre anche una classe che consente la System.Collections.Immutable.ImmutableSortedSet<T>.Builder mutazione, è possibile avere sia immutbilità che prestazioni.

Titolo Descrizione
Selezione di una classe Collection Vengono descritte le diverse raccolte e come selezionarne una per lo scenario.
Tipi di raccolta comunemente usati Vengono descritti i tipi di raccolta generici e non generici comunemente usati, quali System.Array, System.Collections.Generic.List<T> e System.Collections.Generic.Dictionary<TKey,TValue>.
Quando usare raccolte generiche Viene illustrato l'utilizzo di tipi di raccolta generici.
Confronti e ordinazioni all'interno di raccolte Viene illustrato l'utilizzo di confronti di uguaglianza e ordinamento nelle raccolte.
Tipi di raccolta ordinati Vengono descritte le caratteristiche e le prestazioni di raccolte ordinate
Tipi di Collection Hashtable e Dictionary Vengono descritte le funzionalità dei tipi di dizionario basati su hash generici e non generici.
Raccolte thread-Cassaforte Vengono descritti i tipi di raccolta quali System.Collections.Concurrent.BlockingCollection<T> e System.Collections.Concurrent.ConcurrentBag<T> che supportano l'accesso simultaneo sicuro ed efficiente da più thread.
System.Collections.Immutable Introduce le raccolte non modificabili e fornisce collegamenti ai tipi di raccolta.

Riferimento

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