Wenn die Elemente einer Menge nicht-negative, ganze Zahlen aus einem nicht allzu großen Intervall sind, gibt es dafür eine besonders effiziente Darstellung: Jede ganze Zahl wird als Nummer eines Bits aufgefasst und die Menge als ein Array von int implementiert, in dem das Bit mit der Nummer i genau dann gesetzt ist, wenn die Zahl i zur Menge gehört. Abbildung 2.28 zeigt eine solche Darstellung einer Menge von ganzen Zahlen als Bitvektor.

Abbildung 2.28. Eine Menge von ganzen Zahlen realisiert als Bitvektor

Jedes gesetzte Bit entspricht einer Zahl aus dem Intervall [0..31]. Zur Speicherung von 28 Zahlen wird hier nur ein einziger int, also 4 Bytes, benötigt.

Dabei muss die 0 nicht unbedingt die Untergrenze des Intervalls sein. Durch entsprechende Indexarithmetik können selbstverständlich auch negative ganze Zahlen in einem Bitvektor dargestellt werden.

Diese Implementierung spart Platz und Zeit gegenüber einem herkömmlichen Array oder einer Liste, wenn die Zahlen aus einem nicht allzu großen Bereich stammen, und viele Zahlen aus diesem Bereich zur Menge gehören: Ist N die Breite des Intervalles, so benötigt diese Struktur auf einer Maschine, bei der der Typ int M Bit groß ist, ungefähr N/M viele ints. Der Zugriff auf ein einzelnes Element ist besonders schnell: Er ist mit konstant vielen Operationen möglich, während in einem Array oder einer Liste erst gesucht werden müsste.

Für Mengendarstellungen dieser Art bietet LEDA die Klassen int_set und d_int_set an. Für erstere muss das Minimum und das Maximum der abzuspeichernden Zahlen im Voraus bekannt sein und bei der Definition angegeben werden. Zweitere kommt dann zum Zuge, wenn dies nicht möglich oder nicht erwünscht ist.

Diese Klassen bieten keinen Vorteil, wenn insgesamt nur wenige Zahlen gespeichert werden, oder die Intervallbreite N sehr groß ist. Dann lohnt sich dagegen eher ein set, ein gewöhnliches array oder eine list.