Share
Noen ganger vil du ha den fleksible størrelsen og brukervennligheten av en koblet liste, men trenger å ha en direkte (konstant tid) indeksering av en matrise. I disse tilfellene, an Arraylist kan gi en rimelig midtvei.
Arraylist er en samling som implementerer IList grensesnitt, men støttes av en array i stedet for en koblet liste. Som en koblet liste kan et vilkårlig antall elementer legges til (begrenset bare av tilgjengelig minne), men oppfører seg som en matrise i alle andre henseender.
ArrayList-klassen implementerer IList grensesnitt. IList gir alle metodene og egenskapene til ICollection samtidig som det legges til direkte indeksering og indeksbasert innføring og fjerning. Følgende kodeeksempel har stubber generert ved hjelp av Visual Studio 2010 Implement Interface-kommandoen.
Følgende kodeprøve inkluderer også tre tillegg til de genererte stubene:
Accentsconagua
T (_items). Denne gruppen vil holde elementene i samlingen.Arraylist klassen for å minimere antall ganger den interne gruppen trenger å bli omfordelt.offentlig klasse ArrayList: System.Collections.Generic.IList T [] _items; offentlig ArrayList (): denne (0) offentlige ArrayList (int lengde) hvis (lengde < 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(); Legge til et element i en Arraylist er hvor forskjellen mellom array og koblet liste virkelig viser. Det er to grunner til dette. Den første er at en Arraylist støtter å sette inn verdier i midten av samlingen, mens en koblet liste støtter legge til elementer til start eller slutt på listen. Det andre er at det å legge et element til en koblet liste alltid er en O (1) -operasjon, men å legge til elementer til en Arraylist er enten en O (1) eller en O (n) operasjon.
Etter hvert som elementer legges til samlingen, kan den interne arrayen etter hvert bli full. Når dette skjer, må følgende gjøres:
Det eneste spørsmålet vi må svare på på dette punktet, er hvilken størrelse skal den nye gruppen bli? Svaret på dette spørsmålet er definert av Arraylist vekstpolitikk.
Vi ser på to vekstpolitikker, og for hver av oss ser vi på hvor raskt matrisen vokser og hvordan det kan påvirke ytelsen.
Det er to implementeringer av Arraylist klasse vi kan se på nettet: Mono og Rotor. Begge bruker en enkel algoritme som dobler størrelsen på arrayet hver gang en tildeling er nødvendig. Hvis arrayet har en størrelse på null, er standardkapasiteten 16. Algoritmen er:
størrelse = størrelse == 0? 1: størrelse * 2;
Denne algoritmen har færre tildelinger og arraykopier, men slipper mer plass i gjennomsnitt enn Java-tilnærmingen. Med andre ord er det forspent mot å ha flere O (1) innlegg, som skal redusere antall ganger samlingen utfører den tidkrevende tildeling og kopiering. Dette kommer på bekostning av et større gjennomsnittlig minnefotavtrykk, og i gjennomsnitt flere tomme array-spor.
Java bruker en lignende tilnærming, men vokser arrayet litt langsommere. Algoritmen den bruker til å vokse oppstillingen er:
størrelse = (størrelse * 3) / 2 + 1;
Denne algoritmen har en langsommere vekstkurve, noe som betyr at den er partisk mot mindre minne overhead på bekostning av flere tildelinger. La oss se på vekstkurven for disse to algoritmer for en Arraylist med mer enn 200.000 varer lagt til.
Vekstkurven for Mono / Rotor versus Java for 200.000 + elementer Du kan se i denne grafen at det tok 19 tildelinger for doblingsalgoritmen for å krysse 200 000-grensen, mens det tok den langsommere (Java) algoritmen 30 tildelinger for å komme til samme punkt.
Så hvilken er riktig? Det er ikke noe riktig eller feil svar. Doubling utfører færre O (n) operasjoner, men har mer minne overhead i gjennomsnitt. Den langsommere vekstalgoritmen utfører flere O (n) operasjoner, men har mindre minneoverhode. For en generell samling er enten tilnærming akseptabel. Ditt problem domenen kan ha spesifikke krav som gjør en mer attraktiv, eller det kan kreve at du oppretter en annen tilnærming helt. Uansett hvilken tilnærming du tar, vil samlingenes grunnleggende oppførsel forbli uendret.
Våre Arraylist klassen vil bruke dobling (Mono / Rotor) tilnærming.
privat tomrom GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Oppførsel | Legger til den angitte verdien på den angitte indeksen i samlingen. Hvis den angitte indeksen er lik eller større enn Telle, et unntak kastes |
| Opptreden | På) |
Hvis du setter inn på en bestemt indeks, må du skifte alle elementene etter innsettingspunktet til høyre for en. Hvis backing-arrayet er fullt, må det dyrkes før skiftingen kan gjøres.
I det følgende eksemplet er det en matrise med en kapasitet på fem elementer, hvorav fire er i bruk. Verdien tre vil bli satt inn som det tredje elementet i gruppen (indeks to).
Arrangementet før innsatsen (en åpen spalte på slutten) 
Matrisen etter skifting til høyre 
Matrisen med det nye elementet lagt til på den åpne sporet offentlig tomrom Sett inn (int indeks, T-element) if (index> = Count) kaste ny IndexOutOfRangeException (); hvis (_items.Length == this.Count) this.GrowArray (); // Skift alle elementene som følger indeks ett spor til høyre. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = item; Teller ++;
| Oppførsel | Legger til den angitte verdien til slutten av samlingen. |
| Opptreden | O (1) når arraykapasiteten er større enn Count; O (n) når vekst er nødvendig. |
offentlig tomrom Legg til (T-punkt) hvis (_items.Length == Count) GrowArray (); _items [Count ++] = item;
| Oppførsel | Fjerner verdien på den angitte indeksen. |
| Opptreden | På) |
Hvis du fjerner ved en indeks, er det i hovedsak omvendt av Insert-operasjonen. Elementet blir fjernet fra arrayet og arrayet blir forskjøvet til venstre.
Arrangementet før verdien 3 fjernes 
Arrayet med verdien 3 fjernet 
Arrangementet skiftet til venstre, frigjøring av den siste sporet offentlig tomt FjernAt (int indeks) if (index> = Count) kaste ny IndexOutOfRangeException (); int shiftStart = indeks + 1; hvis (shiftStart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Oppførsel | Fjerner det første elementet i samlingen hvis verdi samsvarer med den angitte verdien. returer ekte hvis en verdi ble fjernet. Ellers returnerer den falsk. |
| Opptreden | På) |
offentlig bool Fjern (T element) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Oppførsel | Returnerer den første indeksen i samlingen, hvis verdi tilsvarer den angitte verdien. Returnerer -1 hvis ingen matchende verdi er funnet. |
| Opptreden | På) |
offentlig int IndexOf (T element) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Oppførsel | Går inn eller setter verdien på den angitte indeksen. |
| Opptreden | O (1) |
offentlig T denne [int indeks] få hvis (indeks < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Oppførsel | Returnerer sant hvis den angitte verdien finnes i samlingen. Ellers returnerer den falsk. |
| Opptreden | På) |
offentlig bool Inneholder (T-punkt) return IndexOf (item)! = -1;
| Oppførsel | Returnerer en IEnumerator eksempel som tillater oppsummering av listelistens verdier i rekkefølgen fra første til siste. |
| Opptreden | Å returnere opptellingene er en O (1) operasjon. Oppsummering av hvert element er en O (n) -operasjon. |
Legg merke til at vi ikke bare kan utsette til _items tabellens GetEnumerator fordi det også ville returnere elementene som for tiden ikke er fylt med data.
offentlig 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();
| Oppførsel | Fjerner alle elementene fra matelisten. |
| Opptreden | O (1) |
Det er to alternativer når du implementerer Klar. Arrayet kan stå alene eller det kan omfordeles som en 0-lengdes array. Denne implementeringen omfordeler en ny serie med en lengde på null. Et større utvalg vil bli tildelt når et element legges til i gruppen ved hjelp av Legg til eller Sett inn fremgangsmåter.
Offentlig tomretting Clear () _items = new T [0]; Count = 0;
| Oppførsel | Kopier innholdet i det interne arrayet fra start til slutt til det angitte arrayet som starter ved den angitte arrayindeksen. |
| Opptreden | På) |
Legg merke til at metoden ikke bare utsettes for _items tabellens Kopier til metode. Dette skyldes at vi bare vil kopiere rekkevidden fra indeksen 0 til Telle, ikke hele array kapasiteten. Ved hjelp av Array.Copy lar oss spesifisere antall elementer som skal kopieres.
Offentlig tomt CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Oppførsel | Returnerer et heltall som angir antall elementer i samlingen. Når listen er tom, er verdien 0. |
| Opptreden | O (1) |
Telle er rett og slett en automatisk implementert eiendom med en offentlig getter og privat setter. Den virkelige oppførselen skjer i funksjonene som manipulerer samlingsinnholdet.
offentlig inntekt get; privat sett;
| Oppførsel | Returnerer falsk fordi samlingen ikke er skrivebeskyttet. |
| Opptreden | O (1) |
offentlig bool IsReadOnly get return false;
