Share
A volte si desidera il dimensionamento flessibile e la facilità d'uso di un elenco collegato, ma è necessario avere l'indicizzazione diretta (a tempo costante) di un array. In questi casi, a Lista di array può fornire una ragionevole via di mezzo.
Lista di array è una collezione che implementa il IList interfaccia ma è supportato da una matrice piuttosto che da una lista collegata. Come una lista collegata, è possibile aggiungere un numero arbitrario di elementi (limitato solo dalla memoria disponibile), ma comportarsi come un array in tutti gli altri aspetti.
La classe ArrayList implementa il IList interfaccia. IList fornisce tutti i metodi e le proprietà di ICollection aggiungendo anche indicizzazione diretta e inserimento e rimozione basati su indice. Il seguente codice di esempio presenta gli stub generati utilizzando il comando Implement Interface di Visual Studio 2010.
Il seguente esempio di codice include anche tre aggiunte agli stub generati:
Accentsconagua
T (_items). Questo array manterrà gli elementi nella raccolta.Lista di array classe per ridurre al minimo il numero di volte in cui l'array interno deve essere riallocato.public class ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): this (0) public ArrayList (int length) if (length < 0) throw new ArgumentException("length"); _items = new T[length]; public int IndexOf(T item) throw new NotImplementedException(); public void Insert(int index, T item) throw new NotImplementedException(); public void RemoveAt(int index) throw new NotImplementedException(); public T this[int index] get throw new NotImplementedException(); set throw new NotImplementedException(); public void Add(T item) throw new NotImplementedException(); public void Clear() throw new NotImplementedException(); public bool Contains(T item) throw new NotImplementedException(); public void CopyTo(T[] array, int arrayIndex) throw new NotImplementedException(); public int Count get throw new NotImplementedException(); public bool IsReadOnly get throw new NotImplementedException(); public bool Remove(T item) throw new NotImplementedException(); public System.Collections.Generic.IEnumerator GetEnumerator() throw new NotImplementedException(); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() throw new NotImplementedException(); Aggiungere un oggetto a un Lista di array è dove mostra la differenza tra la matrice e la lista collegata. Ci sono due ragioni per questo. Il primo è quello Lista di array supporta l'inserimento di valori nel mezzo della raccolta, mentre un elenco collegato supporta l'aggiunta di elementi all'inizio o alla fine dell'elenco. Il secondo è che l'aggiunta di un elemento a un elenco collegato è sempre un'operazione O (1), ma l'aggiunta di elementi a un Lista di array è un'operazione O (1) o O (n).
Quando gli oggetti vengono aggiunti alla raccolta, alla fine l'array interno potrebbe diventare pieno. Quando ciò accade, è necessario fare quanto segue:
L'unica domanda a cui dobbiamo rispondere a questo punto è quale dimensione dovrebbe assumere il nuovo array? La risposta a questa domanda è definita dal Lista di array politica di crescita.
Analizzeremo due criteri di crescita e, per ciascuno di essi, esamineremo la rapidità con cui l'array cresce e il suo impatto sulle prestazioni.
Ci sono due implementazioni del Lista di array classe che possiamo guardare online: mono e rotore. Entrambi utilizzano un semplice algoritmo che raddoppia le dimensioni dell'array ogni volta che è necessaria un'allocazione. Se la matrice ha una dimensione pari a zero, la capacità predefinita è 16. L'algoritmo è:
size = size == 0? 1: dimensione * 2;
Questo algoritmo ha meno allocazioni e copie di array, ma spreca più spazio in media rispetto all'approccio Java. In altre parole, è polarizzato verso più inserti O (1), che dovrebbero ridurre il numero di volte in cui la raccolta esegue l'operazione di allocazione e copia che richiede tempo. Ciò comporta un ingombro di memoria medio maggiore e, in media, più slot di array vuoti.
Java usa un approccio simile ma aumenta la gamma un po 'più lentamente. L'algoritmo che usa per far crescere l'array è:
size = (size * 3) / 2 + 1;
Questo algoritmo ha una curva di crescita più lenta, il che significa che è polarizzato verso un minore sovraccarico della memoria al costo di più allocazioni. Diamo un'occhiata alla curva di crescita per questi due algoritmi per un Lista di array con oltre 200.000 articoli aggiunti.
La curva di crescita per Mono / Rotor rispetto a Java per oltre 200.000 articoli È possibile vedere in questo grafico che sono state necessarie 19 allocazioni per l'algoritmo di raddoppiamento per superare il limite di 200.000, mentre è necessario l'algoritmo più lento (Java) per 30 allocazioni per raggiungere lo stesso punto.
Quindi quale è corretto? Non c'è una risposta giusta o sbagliata. Il raddoppio esegue meno operazioni O (n), ma ha un sovraccarico di memoria in media. L'algoritmo di crescita più lento esegue più operazioni O (n) ma ha un sovraccarico di memoria inferiore. Per una raccolta di carattere generale, entrambi gli approcci sono accettabili. Il dominio del problema potrebbe avere requisiti specifici che ne rendono più attraente o potrebbe richiedere la creazione di un altro approccio. Indipendentemente dall'approccio che segui, i comportamenti fondamentali della collezione rimarranno invariati.
Nostro Lista di array la classe utilizzerà l'approccio del raddoppio (mono / rotore).
private void GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Comportamento | Aggiunge il valore fornito all'indice specificato nella raccolta. Se l'indice specificato è uguale o superiore a Contare, viene generata un'eccezione |
| Prestazione | Sopra) |
L'inserimento in un indice specifico richiede lo spostamento di tutti gli elementi dopo il punto di inserimento a destra di uno. Se il backing array è pieno, dovrà essere cresciuto prima di poter eseguire lo spostamento.
Nell'esempio seguente, c'è una matrice con una capacità di cinque elementi, quattro dei quali sono in uso. Il valore tre verrà inserito come terzo elemento dell'array (indice due).
La matrice prima dell'inserto (uno slot aperto alla fine) 
L'array dopo il passaggio a destra 
La matrice con il nuovo elemento aggiunto nello slot aperto public public Insert (int index, T item) if (index> = Count) throw new IndexOutOfRangeException (); if (_items.Length == this.Count) this.GrowArray (); // Sposta tutti gli articoli seguendo lo slot di indice uno a destra. Array.Copy (_items, index, _items, index + 1, Count - index); _items [indice] = elemento; Conte ++;
| Comportamento | Aggiunge il valore fornito alla fine della raccolta. |
| Prestazione | O (1) quando la capacità dell'array è maggiore di Count; O (n) quando la crescita è necessaria. |
pubblico vuoto Aggiungi (elemento T) if (_items.Length == Count) GrowArray (); _items [Count ++] = item;
| Comportamento | Rimuove il valore nell'indice specificato. |
| Prestazione | Sopra) |
La rimozione di un indice è essenzialmente il contrario dell'operazione di inserimento. L'elemento viene rimosso dall'array e l'array viene spostato a sinistra.
L'array prima del valore 3 viene rimosso 
La matrice con il valore 3 rimosso 
L'array si è spostato a sinistra, liberando l'ultimo slot pubblico vuoto RemoveAt (int index) if (index> = Count) throw new IndexOutOfRangeException (); int shiftStart = indice + 1; se (shiftStart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Comportamento | Rimuove il primo elemento della raccolta il cui valore corrisponde al valore fornito. ritorna vero se un valore è stato rimosso. Altrimenti ritorna falso. |
| Prestazione | Sopra) |
public bool Remove (T item) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Comportamento | Restituisce il primo indice nella raccolta il cui valore è uguale al valore fornito. Restituisce -1 se non viene trovato alcun valore corrispondente. |
| Prestazione | Sopra) |
public int IndexOf (T item) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Comportamento | Ottiene o imposta il valore sull'indice specificato. |
| Prestazione | O (1) |
pubblico T questo [int index] get if (indice < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Comportamento | Restituisce true se il valore fornito esiste nella raccolta. Altrimenti restituisce falso. |
| Prestazione | Sopra) |
public bool Contains (T item) return IndexOf (item)! = -1;
| Comportamento | Restituisce un IEnumerator istanza che consente di enumerare i valori dell'elenco di matrice in ordine dal primo all'ultimo. |
| Prestazione | Il ritorno dell'istanza dell'enumeratore è un'operazione O (1). L'enumerazione di ogni elemento è un'operazione O (n). |
Nota che non possiamo semplicemente rimandare al _elementi serie di GetEnumerator perché ciò restituirebbe anche gli articoli che al momento non sono pieni di dati.
pubblico System.Collections.Generic.IEnumerator GetEnumerator () for (int i = 0; i < Count; i++) yield return _items[i]; System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() return GetEnumerator();
| Comportamento | Rimuove tutti gli elementi dall'elenco di array. |
| Prestazione | O (1) |
Ci sono due opzioni quando si implementa Chiaro. La matrice può essere lasciata da sola o può essere riallocata come una matrice di lunghezza 0. Questa implementazione rialloca un nuovo array con una lunghezza pari a zero. Un array più grande verrà assegnato quando un elemento viene aggiunto all'array usando il Inserisci o Inserire metodi.
Public void Clear () _items = new T [0]; Conteggio = 0;
| Comportamento | Copia il contenuto dell'array interno dall'inizio alla fine nell'array fornito a partire dall'indice dell'array specificato. |
| Prestazione | Sopra) |
Si noti che il metodo non si limita a rimandare a _elementi serie di Copia a metodo. Questo perché vogliamo solo copiare l'intervallo dall'indice 0 a Contare, non l'intera capacità dell'array. utilizzando Array.Copy ci consente di specificare il numero di elementi da copiare.
public void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Comportamento | Restituisce un numero intero che indica il numero di elementi attualmente nella raccolta. Quando la lista è vuota, il valore è 0. |
| Prestazione | O (1) |
Contare è semplicemente una proprietà implementata automaticamente con un getter pubblico e un setter privato. Il vero comportamento si verifica nelle funzioni che manipolano i contenuti della raccolta.
int pubblico count; set privato;
| Comportamento | Restituisce false perché la raccolta non è di sola lettura. |
| Prestazione | O (1) |
public bool IsReadOnly get return false;
