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 (eng: 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

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

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

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.