In che modo l'elenco <T> funziona in modo dinamico sebbene utilizzi internamente l'array (che è corretto)?

Question

Conosco già generici e array in C# (conosco array dinamici usando puntatori in C++), so anche che gli array hanno dimensioni fisse quindi non possiamo cambiare le sue dimensioni dopo l'inizializzazione, dobbiamo allocarne uno nuovo quindi copia ......

Ultimamente, sto usando ILspy per vedere il codice sorgente di .net assembly e ho scoperto che l'Elenco si basa su un array privato ma non riesco a capire come funziona , quindi, mi chiedevo, quanto tecnicamente cresce o viene ridimensionato in memoria quando lo compongo?

Answer 1

Il List<T> alloca un array T[] di alcune dimensioni e lo utilizza come spazio di archiviazione per i suoi elementi fino a quando l'array non si riempie. Quando un nuovo elemento deve essere aggiunto dopo che ciò accade, l'elenco alloca un nuovo array più grande e copia tutti gli elementi dal vecchio array a quello nuovo. Il nuovo oggetto può quindi essere aggiunto senza problemi.

Come risultato di questo comportamento, aggiungendo elementi a un List è descritto come amortized O (1) Funzionamento: la maggior parte accodamento richiederanno costante di tempo poiché non v'è spazio libero nella matrice di supporto, ma alcuni accodamento attiveranno una riallocazione di array e richiede molto più tempo.

La modalità di attuazione emerge anche dalla interfaccia pubblica di List: c'è una proprietà Capacity che controlla il numero di elementi della lista può contenere senza ridimensionamento e anche un constructor che consente di riservare un po 'di capacità specificata in anticipo (utile per evitare inutili operazioni di ridimensionamento quando si sa da prima che la lista sarà almeno di una certa dimensione).