Share
Uneori doriți dimensionarea flexibilă și ușurința utilizării unei liste legate, dar trebuie să aveți indexarea directă (constantă) a unei matrice. În aceste cazuri, un ArrayList poate oferi un teren mediu rezonabil.
ArrayList este o colecție care implementează IList dar este susținută de o matrice mai degrabă decât de o listă legată. Ca o listă legată, se poate adăuga un număr arbitrar de elemente (limitat numai de memoria disponibilă), dar se comportă ca un matrice în toate celelalte privințe.
Clasa ArrayList implementează IList interfață. IList oferă toate metodele și proprietățile lui ICollection adăugând în același timp și indexarea directă și inserarea și eliminarea pe bază de index. Următorul exemplu de cod prezintă trunchiuri generate utilizând comanda Implement Interface din Visual Studio 2010.
Următoarea mostră de cod include, de asemenea, trei adaosuri la stuburile generate:
Accentsconagua
T (_items). Această matrice va păstra elementele din colecție.ArrayList pentru a minimiza numărul de repetări a matricei interne.clasa publică ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): acest (0) public ArrayList (lungime int) if (lungime < 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(); Adăugarea unui element la un ArrayList este în cazul în care diferența dintre matrice și lista legate într-adevăr arată. Există două motive pentru aceasta. Primul este acela ArrayList acceptă introducerea valorilor în mijlocul colecției, în timp ce o listă legată acceptă adăugarea de elemente la începutul sau la sfârșitul listei. Al doilea este că adăugarea unui element la o listă legată este întotdeauna o operație O (1), dar adăugarea de elemente la o ArrayList este o operație O (1) sau O (n).
Pe măsură ce elementele sunt adăugate colecției, eventual ar putea deveni plină matricea internă. Când se întâmplă acest lucru, trebuie făcute următoarele:
Singura întrebare pe care trebuie să o răspundem în acest moment este ce dimensiune ar trebui să devină noua matrice? Răspunsul la această întrebare este definit de ArrayList politica de creștere economică.
Vom analiza două politici de creștere și pentru fiecare vom analiza cât de repede crește matricea și cum poate avea impact asupra performanței.
Există două implementări ale programului ArrayList clasa pe care o putem vedea online: Mono și Rotor. Ambele utilizează un algoritm simplu care dublează dimensiunea matricei de fiecare dată când este necesară o alocare. Dacă matricea are o dimensiune de zero, capacitatea implicită este 16. Algoritmul este:
dimensiune = dimensiune == 0? 1: dimensiunea * 2;
Acest algoritm are mai puține alocări și copii de array, dar are mai mult spațiu în medie decât abordarea Java. Cu alte cuvinte, este părtinitoare față de a avea mai multe inserții O (1), ceea ce ar trebui să reducă numărul de operațiuni de colectare și copiere care necesită timp. Acest lucru vine la costul unei amprente medii mai mari a memoriei și, în medie, la mai multe sloturi goale.
Java utilizează o abordare similară, dar crește matricea cu puțin mai lentă. Algoritmul pe care îl folosește pentru a crește matricea este:
dimensiunea = (dimensiunea * 3) / 2 + 1;
Acest algoritm are o curbă de creștere mai lentă, ceea ce înseamnă că este părtinitoare față de cheltuieli mai mici de memorie, cu costul mai multor alocări. Să ne uităm la curba de creștere a acestor doi algoritmi pentru o ArrayList cu mai mult de 200.000 de articole adăugate.
Curba de creștere pentru Mono / Rotor versus Java pentru 200.000 de articole Puteți vedea în acest grafic faptul că a fost nevoie de 19 alocări pentru algoritmul de dublare pentru a trece granița de 200.000, în timp ce algoritmul mai lent (Java) 30 a alocat pentru a ajunge la același punct.
Deci cine este corect? Nu există nici un răspuns corect sau greșit. Dublarea efectuează mai puține operații O (n), dar are mai mult spațiu de memorie în medie. Algoritmul de creștere mai lentă efectuează mai multe operații O (n), dar are o capacitate mai mică de memorie. Pentru o colecție de scopuri generale, fie este acceptabilă o abordare. Domeniul dvs. cu probleme poate avea cerințe specifice care fac una mai atractivă sau poate necesita o altă abordare. Indiferent de abordarea pe care o adoptați, comportamentele fundamentale ale colecției vor rămâne neschimbate.
Al nostru ArrayList clasa va folosi dublarea (Mono / Rotor).
privată voidă GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Comportament | Adaugă valoarea furnizată la indexul specificat din colecție. Dacă indicele specificat este egal sau mai mare decât Numara, o excepție este aruncată |
| Performanţă | Pe) |
Introducerea la un anumit index necesită deplasarea tuturor elementelor după punctul de inserție la dreapta cu unul. Dacă matricea suport este plină, va trebui să fie cultivată înainte ca schimbarea să se facă.
În exemplul următor, există o matrice cu o capacitate de cinci elemente, dintre care patru sunt utilizate. Valoarea trei va fi introdusă ca al treilea element în matrice (indexul doi).
Matricea înainte de inserție (un slot deschis la sfârșit) 
Matricea după mutarea spre dreapta 
Matricea cu elementul nou adăugat la slotul deschis public void Insert (int index, element T) if (index> = Count) arunca noua IndexOutOfRangeException (); dacă (_items.Length == this.Count) this.GrowArray (); / / Shift toate elementele urmând indexul un slot la dreapta. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = element; Count ++;
| Comportament | Se adaugă valoarea furnizată la sfârșitul colecției. |
| Performanţă | O (1) când capacitatea matricei este mai mare decât Count; O (n) atunci când este necesară creșterea. |
public void Adăugați (element T) if (_items.Length == Count) GrowArray (); _items [Count ++] = element;
| Comportament | Elimină valoarea la indexul specificat. |
| Performanţă | Pe) |
Eliminarea la un index este, în esență, inversa operației Insert. Elementul este eliminat din matrice și matricea este deplasată spre stânga.
Matricea înainte de valoarea 3 este eliminată 
Matricea cu valoarea 3 a fost eliminată 
Matricea sa mutat spre stânga, eliberând ultimul slot public void RemoveAt (index int) if (index> = Count) arunca noua IndexOutOfRangeException (); int shiftStart = index + 1; dacă (shiftStart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Comportament | Înlătura primul element din colecția a cărui valoare corespunde valorii furnizate. Se intoarce Adevărat dacă o valoare a fost eliminată. Altfel se întoarce fals. |
| Performanţă | Pe) |
bool public Eliminare (element T) pentru (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Comportament | Returnează primul index din colecția a cărui valoare este egală cu valoarea furnizată. Returnează -1 dacă nu se găsește nicio valoare potrivită. |
| Performanţă | Pe) |
public int IndexOf (element T) pentru (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Comportament | Obține sau stabilește valoarea la indexul specificat. |
| Performanţă | O (1) |
public T acest [index int] get if (index < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Comportament | Returnează true dacă valoarea furnizată există în colecție. În caz contrar, se întoarce false. |
| Performanţă | Pe) |
bool public Contine (element T) return IndexOf (item)! = -1;
| Comportament | Returnează un IEnumerator instanță care permite enumerarea valorilor listei de matrice în ordine de la primul la ultimul. |
| Performanţă | Returnează instanța enumerator este o operație O (1). Enumerarea fiecărui element este o operație O (n). |
Rețineți că nu putem doar să amânați _items matrice lui GetEnumerator deoarece ar reveni, de asemenea, elementele care nu sunt în prezent completate cu date.
public System.Collections.Generic.IEnumerator GetEnumerator () pentru (int i = 0; i < Count; i++) yield return _items[i]; System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() return GetEnumerator();
| Comportament | Elimină toate elementele din lista de matrice. |
| Performanţă | O (1) |
Există două opțiuni la implementare clar. Matricea poate fi lăsată singură sau poate fi realocată ca o matrice de lungime 0. Această implementare realocă o matrice nouă cu o lungime de zero. O matrice mai mare va fi alocată atunci când un element este adăugat la matrice utilizând Adăuga sau Introduce metode.
Void public Clear () _items = nou T [0]; Conținut = 0;
| Comportament | Copiază conținutul matricei interne de la început până la sfârșit în matricea furnizată, începând de la indexul de matrice specificat. |
| Performanţă | Pe) |
Rețineți că metoda nu doar amână la _items matrice lui Copiaza in metodă. Acest lucru se datorează faptului că dorim doar să copiem intervalul din index 0 la Numara, nu întreaga capacitate a matricei. Utilizarea Array.Copy ne permite să specificăm numărul de elemente de copiat.
public void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Comportament | Returnează un număr întreg care indică numărul de articole care se află în prezent în colecție. Când lista este goală, valoarea este 0. |
| Performanţă | O (1) |
Numara este pur și simplu o proprietate implementată automat cu un getter public și setter privat. Comportamentul real se întâmplă în funcțiile care manipulează conținutul colecției.
public int Count get; set privat;
| Comportament | Returnează fals deoarece colecția nu este numai pentru citire. |
| Performanţă | O (1) |
boolean public IsReadOnly get return false;
