Verzameling (informatica)

Een verzameling (Engels: set) is een datacontainer die geïnspireerd is op een verzameling zoals de wiskunde die kent.

Een verzameling bestaat uit een hoeveelheid unieke leden (Engels: members). Algemener (voor alle containers) heten de leden ook wel elementen of items.

Een verzameling lijkt op een bag, maar in een bag hoeven de elementen niet uniek te zijn.

Uitleg[bewerken | brontekst bewerken]

Er zijn formeel twee volkomen verschillende soorten verzamelingen. Een bitarray en een container. Een bitarray wordt toegepast als de mogelijke waarden van tevoren bekend zijn en dit aantal waarden niet al te groot wordt. De container-vorm kan gebruikt worden voor een verzameling van objecten, en heet ook wel een collection.

De manier waarop de taal Pascal een SET implementeert is een voorbeeld van een bitarray.

Een verzameling zoals de wiskunde die definieert is ongeordend, maar de implementatie binnen programmeertalen heeft door de aard van computers altijd een interne ordening. Meestal is dit in de programmeursinterface terug te vinden doordat er een manier bestaat om de leden van de verzameling op te sommen.

Operaties[bewerken | brontekst bewerken]

Een verzameling in een programmeertaal kent diverse operaties. De declaraties van deze functies zijn (in pseudocode):

Verzameling.Bevat(ElementType): BOOLEAN		// test op lidmaatschap van element Verzameling.Bevat(Verzameling): BOOLEAN		// test of het argument omsloten wordt Verzameling.operator+(ElementType): Verzameling	// geeft de verzameling plus het element Verzameling.operator+(Verzameling): Verzameling	// geeft de vereniging van twee verzamelingen Verzameling.operator-(ElementType): Verzameling	// geeft de verzameling minus het element Verzameling.operator-(Verzameling): Verzameling	// geeft de doorsnede van twee verzamelingen Verzameling.operator=(ElementType)		// toewijzing, maakt de verzameling leeg behalve één element Verzameling.operator=(Verzameling)		// toewijzing, kopieert de verzameling Verzameling.VoegToe(ElementType)		// Plus-operatie met toewijzing  Verzameling.VoegToe(Verzameling)		// Plus-operatie met toewijzing Verzameling.Verwijder(ElementType)		// Min-operatie met toewijzing Verzameling.Verwijder(Verzameling)		// Min-operatie met toewijzing 

Daarnaast is er vaak een manier om de leden van de verzameling op te sommen, al dan niet met behulp van een iterator.

Ook aan de objecten die in een verzameling opgenomen kunnen worden, worden minimale eisen gesteld. Om te beginnen moeten ze een methode definiëren om te bepalen of twee objecten gelijk zijn. In Java is de equals() methode hiervoor voor de hand liggende keuze. In C++ zou je hiervoor operator==() kunnen kiezen. Dit is theoretisch voldoende om een object in een verzameling op te kunnen nemen, maar om een en ander efficiënt te kunnen implementeren moeten deze objecten minstens ook een hash() methode bevatten óf een methode die een ordening aangeeft tussen twee objecten.

Voorbeelden van gebruik[bewerken | brontekst bewerken]

Het gebruik van een bitarray zou er zo uit kunnen zien:

// voorbeeld 1, verzameling gebaseerd op een bitarray ENUM kleur (groen, blauw, geel) FUNCTION meng(mengsel: BITARRAY<kleur>): kleur    IF mengsel.Bevat(geel) AND mengsel.Bevat(blauw) THEN       RETURN groen    ENDIF ENDFUN  VARIABELE verfmengsel= NEW BITARRAY<kleur> verfmengsel= blauw verfmengsel.VoegToe(geel) PRINT meng(verfmengsel) 

Het gebruik van een verzameling die gebaseerd is op een container zou er zo uit kunnen zien. Om het voorbeeld kort te houden is wederom gekozen voor niet OO-code en als lid van de verzameling is om dezelfde reden het type string gekozen.

// voorbeeld 2, verzameling gebaseerd op een container FUNCTION meng(mengsel: OBJECTVERZAMELING<string>): string    IF mengsel.Bevat("blauw") AND mengsel.Bevat("geel") THEN       RETURN "groen"    ENDIF ENDFUN  VARIABELE verfmengsel= NEW OBJECTVERZAMELING<string> verfmengsel= "blauw" verfmengsel.VoegToe("geel") PRINT meng(verfmengsel) 

Eigenlijk is het tweede voorbeeld bijna gelijk aan het eerste behalve dat het type 'kleur' vervangen is door het type 'string'. Dit is echter wel een essentieel verschil omdat aan de laatste verzameling elke denkbare string toegevoegd zou kunnen worden, terwijl de eerste slechts met de gedefinieerde kleuren kan werken. Het eerste voorbeeld heeft een sterkere typecontrole, het tweede is flexibeler. Het eerste voorbeeld produceert minder code en executeert sneller.