Arraylistan

Ibland vill du ha den flexibla dimensioneringen och användarvänligheten av en länkad lista, men behöver ha en direkt (konstant tid) indexering av en array. I dessa fall är en Arraylist kan ge en rimlig mellanklass.

Översikt

Arraylist är en samling som implementerar IList gränssnittet, men stöds av en array snarare än en länkad lista. Som en länkad lista kan ett godtyckligt antal objekt läggas till (begränsas endast av tillgängligt minne), men fungerar som en array i alla andra avseenden.

Klass Definition

ArrayList-klassen implementerar IList gränssnitt. IList ger alla metoder och egenskaper hos iCollection samtidigt som man lägger till direkt indexering och indexbaserad infogning och borttagning. Följande kodprov presenterar stubbar genererade genom att använda Visual Studio 2010: s Implement Interface-kommando.

Följande kodprov inkluderar också tre tillägg till de genererade stubbarna:

En uppsättning av T (_items). Denna array kommer att hålla objekten i samlingen.
En standardkonstruktor initierar matrisen till storlek noll.
En konstruktör som accepterar en heltalslängd. Denna längd blir standardkapaciteten för matrisen. Kom ihåg att kapaciteten i matrisen och samlingsräkningen inte är samma sak. Det kan finnas scenarier när du använder den icke-standardiserade konstruktören, tillåter användaren att ge en storleksanpassning till Arraylist klass för att minimera antalet gånger den interna gruppen behöver omfördelas.

offentlig klass ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): this (0)  public ArrayList (int längd) om (längd < 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();

Införande

Lägga till ett objekt i en Arraylist är där skillnaden mellan array och länklistan verkligen visar. Det finns två skäl till detta. Den första är den an Arraylist stödjer att infoga värden i mitten av samlingen, medan en länkad lista stöder att lägga till objekt i början eller slutet av listan. Det andra är att att lägga till en vara i en länkad lista alltid är en O (1) operation, men lägger till objekt i en Arraylist är antingen en O (1) eller en O (n) operation.

Växande arrayen

När objekt läggs till i samlingen kan den interna matrisen slutligen bli full. När detta händer måste följande göras:

Tilldela en större.
Kopiera elementen från den mindre till den större gruppen.
Uppdatera den interna gruppen för att vara den större gruppen.

Den enda frågan vi behöver svara vid denna punkt är vilken storlek ska den nya matrisen bli? Svaret på denna fråga definieras av Arraylist tillväxtpolitik.

Vi tittar på två tillväxtpolicyer, och för varje ser vi hur snabbt matrisen växer och hur det kan påverka prestanda.

Dubbla (Mono och Rotor)

Det finns två implementeringar av Arraylist klass vi kan titta på online: Mono och Rotor. Båda använder en enkel algoritm som fördubblar storleken på matrisen varje gång en fördelning behövs. Om arrayen har en storlek på noll är standardkapaciteten 16. Algoritmen är:

storlek = storlek == 0? 1: storlek * 2;

Denna algoritm har färre allokeringar och arraykopior, men slösar mer utrymme i genomsnitt än Java-tillvägagångssättet. Med andra ord är det förspänt mot att ha fler O (1) insatser, vilket bör minska antalet gånger samlingen utför den tidskrävande allokerings-och-kopia operationen. Detta kommer på bekostnad av ett större genomsnittligt minnesfotavtryck, och i genomsnitt mer tomma array-slitsar.

Långsammare tillväxt (Java)

Java använder ett liknande tillvägagångssätt men växer arrayen lite långsammare. Den algoritm som används för att växa matrisen är:

storlek = (storlek * 3) / 2 + 1;

Denna algoritm har en långsammare tillväxtkurva, vilket innebär att den är förspänd gentemot mindre minnesutgifter på bekostnad av fler tilldelningar. Låt oss titta på tillväxtkurvan för dessa två algoritmer för en Arraylist med mer än 200 000 artiklar tillagda.

Tillväxtkurvan för Mono / Rotor versus Java för 200 000+ objekt

Du kan se i denna graf att det tog 19 anslag för dubblingsalgoritmen för att korsa 200 000 gränsen, medan det tog långsammare (Java) algoritmen 30 anslag att komma till samma punkt.

Så vilken är korrekt? Det finns inget rätt eller fel svar. Doubling utför färre O (n) -operationer, men har mer minne i genomsnitt. Den långsammare tillväxtalgoritmen utför mer O (n) -operationer men har mindre minneöverhuvud. För en samling med allmänt ändamål är antingen tillvägagångssätt acceptabelt. Din problemdomän kan ha specifika krav som gör en tilltalande attraktivare, eller det kan kräva att du skapar ett helt annat tillvägagångssätt. Oavsett vilket sätt du tar, kommer samlingens grundläggande beteende att förbli oförändrat.

Vår Arraylist klassen kommer att använda fördubblingen (Mono / Rotor).

privat tomt GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;

Föra in

Beteende	Lägger till det angivna värdet vid det angivna indexet i samlingen. Om det angivna indexet är lika med eller större än `Räkna`, ett undantag kastas
Prestanda	På)

Om du lägger in i ett specifikt index måste du flytta alla objekt efter infogningspunkten till höger om en. Om backing-arrayen är full måste den odlas innan skiftningen kan utföras.

I följande exempel finns en array med en kapacitet på fem objekt, varav fyra är i bruk. Värdet tre kommer att införas som det tredje objektet i matrisen (index två).

Arrayet före insatsen (en öppen slits i slutet)

Arrayen efter att ha skiftats till höger

Arrayen med det nya objektet läggs till vid den öppna luckan

public void Infoga (int index, T item) if (index> = Count) släng nytt IndexOutOfRangeException ();  om (_items.Length == this.Count) this.GrowArray ();  // Skift alla objekt som följer index en plats till höger. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = item; Räkna ++;

Lägg till

Beteende	Lägger till det angivna värdet till slutet av samlingen.
Prestanda	O (1) när arraykapaciteten är större än Count; O (n) när tillväxt är nödvändig.

public void Lägg till (T item) if (_items.Length == Count) GrowArray ();  _items [Count ++] = item;

Radering

RemoveAt

Beteende	Tar bort värdet vid det angivna indexet.
Prestanda	På)

Att ta bort i ett index är i huvudsak bakom Insert-funktionen. Objektet tas bort från matrisen och matrisen flyttas till vänster.

Arrayet före värdet 3 tas bort

Arrayen med värdet 3 avlägsnades

Arrayet skiftades till vänster och frigjorde den sista luckan

public void RemoveAt (int index) if (index> = Count) släng nytt IndexOutOfRangeException ();  int shiftStart = index + 1; om (shiftStart < Count)  // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart);  Count--;

Ta bort

Beteende	Tar bort det första objektet i samlingen vars värde matchar det angivna värdet. Returer `Sann` om ett värde togs bort. Annars kommer det tillbaka `falsk`.
Prestanda	På)

public bool Ta bort (T item) for (int i = 0; i < Count; i++)  if (_items[i].Equals(item))  RemoveAt(i); return true;   return false;

indexering

Index för

Beteende	Returnerar det första indexet i samlingen vars värde motsvarar det angivna värdet. Returnerar -1 om inget matchande värde hittas.
Prestanda	På)

public int IndexOf (T item) for (int i = 0; i < Count; i++)  if (_items[i].Equals(item))  return i;   return -1;

Artikel

Beteende	Går eller ställer in värdet vid det angivna indexet.
Prestanda	O (1)

offentliga T detta [int index] get if (index < Count)  return _items[index];  throw new IndexOutOfRangeException();  set  if (index < Count)  _items[index] = value;  else  throw new IndexOutOfRangeException();

innehåller

Beteende	Returnerar sant om det angivna värdet finns i samlingen. Annars returneras det falskt.
Prestanda	På)

offentliga bool Innehåller (T-punkt) return IndexOf (item)! = -1;

Uppräkning

GetEnumerator

Beteende	Returnerar en `IEnumerator` instans som tillåter uppräkning av array listvärdena i ordning från första till sista.
Prestanda	Att återkomma uppräkningsinstansen är en O (1) operation. Att räkna upp varje objekt är en O (n) operation.

Observera att vi inte bara kan skjuta upp till _items arrayens GetEnumerator eftersom det också skulle returnera de objekt som för närvarande inte är fyllda 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();

Återstående IList metoder

Klar

Beteende	Tar bort alla objekt från matrislistan.
Prestanda	O (1)

Det finns två alternativ vid implementering Klar. Arrayet kan lämnas ensamt eller det kan omfördelas som en 0-längds array. Denna implementering omfördelar en ny array med en längd av noll. Ett större array kommer att tilldelas när ett objekt läggs till i arrayen med hjälp av Lägg till eller Föra in metoder.

Public void Clear () _items = new T [0]; Räkna = 0;

Kopia till

Beteende	Kopierar innehållet i den interna matrisen från början till slut i den angivna matrisen som börjar vid det angivna matrisindexet.
Prestanda	På)

Observera att metoden inte helt enkelt skjuter upp till _items arrayens Kopia till metod. Detta beror på att vi bara vill kopiera intervallet från index 0 till Räkna, inte hela array-kapaciteten. Använder sig av Array.Copy tillåter oss att ange hur många objekt som ska kopieras.

public void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);

Räkna

Beteende	Returnerar ett heltal som anger antalet objekt som för närvarande finns i samlingen. När listan är tom är värdet 0.
Prestanda	O (1)

Räkna är helt enkelt en automatiskt genomförd egendom med en offentlig getter och privat setter. Det verkliga beteendet händer i de funktioner som manipulerar samlingsinnehållet.

offentlig inträkning get; privat uppsättning

isReadonly

Beteende	Returnerar fel eftersom samlingen inte är skrivskyddad.
Prestanda	O (1)

offentlig bool IsReadOnly get return false;

Nästa Upp

Detta kompletterar den tredje delen om array listor. Därefter fortsätter vi vidare till stack och köer.

Koda