Collection klasser

Ligesom C++ har sit Standard Template Library (STL) og Java har sine collection klasser i java.util, sådan har også C# en samling collection klasser. Det er dem vi vil se nærmere på i det følgende. De befinder sig alle i det namespace der hedder: System.Collections. Man skal derfor huske:

using System.Collections;

i starten af de kildetekster, der anvender collection klasser.

1. Interfaces

Containerne, vi senere skal se på, implementere diverse interfaces. Vi vil derfor først se disse interfaces og hvad der er formålet med dem.

Der er i alt otte interfaces; hvoraf de seks har relationer til hinanden. Vi vil først se på de følgende fire:

Figur 1:
IEnumerable's interfaces

1.1 IEnumerable

Øverst i figur 1's hierarki finder vi IEnumerable. Interfacet har kun en metode:

IEnumerator GetEnumerator()

Som vi senere skal se i beskrivelsen af IEnumerator, kan en IEnumerator bruges til at iterere en collection. IEnumerable interfacet giver os blot adgang til en fabriks-metode, der giver os en sådan iterator. Dette er i tråd med idéen i Iterator Pattern.

Dette interface er særlig vigtigt af en speciel grund. Instanser af klasser, der implementerer IEnumerable, kan nemlig gennemløbes med den specielle variant af for-løkken: foreach:

1.1.1 foreach-løkken

foreach-løkken har følgende syntax:

foreach ( <Element-klasse> <variabel> in <Container> )

Det skal læses som: "For hver <variabel> af typen <Element-klasse> i <Container> så:". I foreach-løkkens krop bruger man <variabel> som reference til den aktuelle instans af <Element-klasse>, som man er kommet til i iterationen.

Lad os først se et eksempel med, hvad der ellers er en primitiv type, int:

int[] tabel = { 2, 3, 5, 7, 9, 11, 13 };

foreach ( int element in tabel )
  Console.Write( element + " " ); 
Console.WriteLine();

Arrays

Der indgår ikke nogen egentlige klasser i dette eksempel - det vil vi vende tilbage til når vi ser på nogle containerklasser - men den generelle mulighed for at anvende foreach-løkken med arrays illustrerer idéen.

Lad os dernæst se et eksempel hvor <Element-klasse> i det mindste er en rigtig klasse:

string[] tabel = { "Dette", "er", "en", "test" };

foreach ( string element in tabel )
  Console.Write( element + " " ); 
Console.WriteLine();

Vi arbejder stadig med et array som <Container>, men <Element-klasse> er nu klassen string.

Som nævnt vil vi vende tilbage til foreach-løkken, efterhånden som vi lærer nogle collection-klasser som vi kan bruge den på.

1.2 ICollection

ICollection implementerer IEnumerable, og alle containere implementerer ICollection. Det er derfor et vigtigt interface, da det fortæller os om C#'s opfattelse af en container.

1.2.1 Properties

ICollection har følgende properties (alle er kun get-properties):

int Count
bool IsReadOnly
bool IsSynchronized
object SyncRoot

Count fortæller hvor mange elementer der er i containeren (kardinaliteten). IsReadOnly, om man kun kan læse fra den. IsSynchronized fortæller om containeren er thread-safe, og SyncRoot returnerer et objekt, som man kan synkronisere på.

[Note: Det er uklart om IsReadOnly er erklæret i ICollection eller først optræder i IList og IDirectory]

1.2.2 Metoder

ICollection har kun én metode:

void CopyTo( Array array, int index )

Kopierer til array

Array er baseklasse for alle arrays. Den første parameter kan derfor være et hvilket som helst array (det skal dog være en-dimensionelt). Metoden kopierer elementerne fra containeren til det array som gives med som parameter. Denne kopiering starter fra det angivne index i array. Der kastes en ArgumentException hvis der ikke er plads.

1.3 IList

Har index'er

IList repræsenterer en container hvor elementerne kan refereres med index. Det er derfor ikke overraskende at IList har en index'er.

1.3.1 Properties

IList har følgende property (er kun en get-property):

bool IsFixedSize

IsFixedSize fortæller om containeren har en fast kapacitet - dvs. om der er et fast maximum for, hvor mange elementer den kan indeholde.

1.3.2 Metoder

Først er der metoder til at tilføje elementer

Tilføje

int Add( object value )
void Insert( int index, object value )

Add returnerer hvor elementet er blevet placeret (index). Insert placerer elementet det angivne sted. Insert kan kaste en ArgumentOutOfRangeException.

Dernæst er der de søgende metoder:

Søge

bool Contains( object value )
int IndexOf( object value )

Contains fortælle om elementet overhovedet findes i containeren, mens IndexOf fortæller hvor (index). Hvis elementet ikke findes, returnerer IndexOf: -1.

Hvis man skulle få behov for at fjerne elementer, er der:

Fjerne

void Remove( object value )
void RemoveAt( int index )

Remove fjerner et element. Bemærk at denne metode ikke fortæller om et element rent faktisk er blevet fjernet; hvis det er vigtigt at vide, må man først kalde Contains. RemoveAt fjerner elementet på den angivne placerering (index). RemoveAt kan kaste en ArgumentOutOfRangeException.

Endelig er der:

void Clear()

som tømmer containeren for alle elementer - så den er tom.

1.4 IDictionary

Mapping

Et IDictionary repræsenterer en samling af elementer med tilhørende nøgle. Man kalder det også en mapping mellem nøgler og værdier - en entydig afbildning af nøgler over i værdier - en funktion (i matematisk forstand). I Java anvendes betegnelsen "map" for disse containere.

Har index'er

IDirectory har en index'er. Den tager nøglen som index og giver elementet.

1.4.1 Properties

IList har følgende properties (alle er kun get-properties):

bool IsFixedSize
ICollection Keys
ICollection Values

Ligesom for IList fortæller IsFixedSize om containeren har en fast kapacitet.

Keys og Values returnerer containerens nøgler henholdsvis elementer i en container (hvor om det kun vides, at den implementerer ICollection interfacet).

1.4.2 Metoder

void Add( object key, object value )
bool Contains( object key )
void Remove( object key )
void Clear()

Add tilføjer et element. Bemærk at key ikke må være null. Add kaster en ArgumentAxception, hvis key allerede findes i containeren.

Contains returnerer om en bestemt nøgle findes i containeren.

Remove fjerner et element fra containeren. Denne metode oplyser ikke om elementet fandtes før det blev fjernet.

Clear tømmer containeren for elementer.

Endelig har IDictionary en anden udgave af GetEnumerator (ellers erklæret i IEnumerable):

IDictionaryEnumerator getEnumerator()

Denne metode returnerer en særlig iterator til directories - mere om den senere.

De to sidste, af de seks interfaces der har relationer til hinanden, udgør naturligvis et langt mindre hierarki:

Figur 2:
IEnumerator's interfaces

Ikke robuste

Der er i begge tilfælde tale om iteratorer. Man skal bemærke, at der ikke er tale om robuste iteratorer.

1.5 IEnumerator

IEnumerator repræsenterer en generel iterator, som returneres af fabriks-metoden i IEnumerable.

Iteratorerne initialiseres til at være én position før det første element i containeren, så man skal altid gå et skridt frem for at finde det første element.

1.5.1 Properties

IEnumerator har følgende property (er kun get-property):

object Current

Current returnerer det element som iteratoren er kommet til.

1.5.2 Metoder

bool MoveNext()
void Reset()

MoveNext flytter frem til det næste element, og returnerer boolsk om der er et sådant element. Hvis man når hen til enden af containeren, vil gentagne kald af MoveNext blive ved med at returnere false.

Reset placerer iteratoren én position før det første element i containeren.

Bemærk at man altid skal kalde MoveNext efter Reset (eller når man første gang anvender iteratoren) for at finde det første element. At iteratoren starter én position før første element i containeren, gør det (som bekendt) enkelt at opbygge en iteration over containerens elementer med en while-løkke:

IEnumerator iterator = ...

...

iterator.Reset();
while ( iterator.MoveNext() ) {
  Element e = (Element) iterator.Current;
  ...
}

1.6 IDictionaryEnumerator

IDictionaryEnumerator anvender de samme iterator-metoder som den arver fra IEnumerator. Det nye i IDictionaryEnumerator er behovet for at erstatte Current, med properties der tilgår nøglen og det tilhørende element.

1.6.1 Properties

IDictionaryEnumerator har følgende properties (alle er kun get-properties):

DictionaryEntry Entry
object Key
object Value

Key og Value giver adgang til "Current" elementet (der her er et 2-tuple bestående af nøgle og tilhørende element). Entry giver adgang til dem begge på en gang, samlet i en instans af DictionaryEntry, der er en struct med de to properties Key og Value.

Endelig har vi to interfaces, der ikke har relationer til de andre:

1.7 IComparer

IComparer kunne lige så godt være et delegat, da det er et interface med kun én metode og ingen properties. Idéen med IComparer er at stille en metode til rådighed, som kan sammenligne to objekter. Metoden er:

int Compare( object x, object y )

Metoden fungerer på samme måde som compareTo-metoden i Java.

1.8 IHashCodeProvider

IHashCodeProvider kunne for så vidt også være et delegat, da den ligeledes kun har én metode og ingen properties. Metoden er:

int GetHashCode( object obj )

Metoden er en hashfunktion, der returnerer en hashværdi for det givne objekt.

2. Containere

De interfaces vi har gennemgået i det foregående implementeres i forskelligt omfang af de følgende container klasser. Alle container-klasser implementerer ICollection og IEnumerable. Metoder og properties fra disse to interfaces vil derfor ikke blive nævnt i det følgende:

2.1 ArrayList

IList

ArrayList er et dynamisk array af object's. Det fungerer i stil med java.util.Vector i Java (Ligesom Vector fordobler sin størrelse, når den løber fuld, således gør ArrayList det også). ArrayList implementerer IList. Der ud over har ArrayList en række properties og metoder:

2.1.1 Konstruktorer

ArrayList har følgende konstruktorer:

ArrayList()
ArrayList( int capacity )
ArrayList( ICollection c )

Initiel kapacitet

Default-konstruktoren initialiserer naturligvis listen til at være tom og have den initielle default kapacitet (16). Konstruktoren der tager en int som parameter sætter i stedet den initielle kapacitet til den angivne størrelse.

Kopierer

Den sidste konstruktor kopierer elementerne fra den givne container, til sig selv, og sætter sin kapacitet til det kopierede antal elementer - dvs. ingen overskydende plads!

2.1.2 Properties

ArrayList har følgende property (er kun get-property):

int Capacity

Capacity fortæller hvor meget plads (totalt) der er i arrayet, på nuværende tidspunkt. Eftersom ArrayList er et dynamisk array, vil det udvide sin kapacitet efter behov.

2.1.3 Metoder

ArrayList er rig på metoder - der er over tredive. Vi vil derfor nøjes med dem, der må formodes at være de mest anvendte:

void AddRange( ICollection c )
ArrayList GetRange( int index, int count )
void InsertRange( int index, ICollection c )
void RemoveRange( int index, int count )
void SetRange( int index, ICollection c )

object[] ToArray()
Array ToArray( Type type )

void Reverse()
void Reverse( int index, int count )

void CopyTo( Array array )
void CopyTo( int index, Array array, int arrayIndex, int count )

IEnumerator GetEnumerator( int index, int count )

int BinarySearch( object value )
int BinarySearch( object value, IComparer comparer )
int BinarySearch( int index, int count, object value, IComparer comparer )

void Sort()
void Sort( IComparer comparer )
void Sort( int index, int count, IComparer comparer )

int IndexOf( object value, int startIndex )
int IndexOf( object value, int startIndex, int count )

int LastIndexOf( object value )
int LastIndexOf( object value, int startIndex )
int LastIndexOf( object value, int startIndex, int count )

2.2 BitArray

Boolske værdier som pakkede bits

Navnet BitArray beskriver primært den interne repræsentation der anvendes, nemlig pakkede bits. Med pakkede bits menes bits der er samlet i de enkelte bytes (8 stk.) så der ikke går plads til spilde. Ud ad til fremstår BitArray som en container, der kan indeholde boolske værdier - dvs. elementer af typen bool.

2.2.1 Konstruktorer

BitArray har først og fremmest en copy-konstruktor:

BitArray( BitArray bits )
BitArray( bool[] values )

Ud over copy-konstruktoren er der også, hvad man kunne kalde en "virtuel set-konstrutor". Ud ad til fremstår BitArray jo som et array af boolske værdier.

Dernæst har vi et par konstruktorer, der laver initialiserede BitArray's af en vis længde:

BitArray( int length )
BitArray( int length, bool defaultValue )

I begge tilfælde angiver length længden af BitArray'et. I det første tilfælde initialiseres alle indgange til false (0), mens den anden giver mulighed for at man selv kan angive initialiseringsværdien.

Endelig har BitArray et par konstruktorer, der gør det muligt at initialisere ud fra den interne repræsentation - nemlig pakkede bits:

BitArray( byte[] bytes )
BitArray( int[] values )

Den første går direkte på den interne repræsentation - et array af byte's, mens den anden tager lidt større bider (en int er som bekendt fire bytes).

Lad os se et eksempel (forudsætter at man er fortrolig med hexadecimal notation):

using System;
using System.Collections;

public class Test {
  public static void Main() {
    byte[] bytes = { 0x01, 0x23, 0x45, 0x67 };
    int[] integers = { 0x01234567 };
    
    BitArray bArray = new BitArray( bytes );
    BitArray iArray = new BitArray( integers );
    
    Print( bArray );
    Print( iArray ); 
  }
  
  private static void Print( BitArray array ) {
    foreach ( bool bit in array ) {
      switch ( bit ) {
        case true:
          Console.Write( "1" );
          break;
        case false:
          Console.Write( "0" );
          break;
      } 
    }
    Console.WriteLine();
  } 
}

10000000110001001010001011100110
11100110101000101100010010000000

Den første bit er bit 0, den næste er bit 1 osv. Det kan være lidt svært at gennemskue output'et, da det skal læses bagfra; hvis man vil sammenligne med de to arrays. Omsætter man i første omgang hver nibble til hex, får man:

10325476
76543210

Dette skal fortsat læses bagfra. I den øverste linie er 1 den første nibble - dvs. mindst betydende - den der repræsenterer indgangene 0-3 i bArray. Læser man bagfra, får man:

67452301
01234567

Hvis vi tager den nederste linie først, ser vi at bit 0-15 i vores integer er blevet afbildet direkte over i indgang 0-15 i arrayet. For byte-arrayet er det det samme system, men måske lidt sværere at se. Den første byte i vores array: bytes[0] er blevet indgang 0-7, det næste bytes[1] er blevet indgang 8-15 osv. På samme måde som for int'en svarer bit-positionerne i den binære repræsentation til indgangene (absolut for bytes[0] og relativt for de andre).

2.2.2 Properties

BitArray har propertien (kun get-property):

Length

der giver arrayets længde - dvs. antallet af bits i arrayet.

BitArray har desuden en index'er

2.2.3 Metoder

And
Not
Or
Xor

Get
Set
SetAll

CopyTo

2.3 Hashtable

2.4 Queue

2.5 SortedList

2.6 Stack

3. Type-specifikke containere

3.x StringCollection