Menge (Datenstruktur)

Grundidee und zentrale Operationen

Eine Menge, auch Set genannt, ist eine ungeordnete Sammlung von Elementen eines bestimmten Datentyps. Jedes Element darf höchstens einmal enthalten sein; Duplikate werden daher nicht mehrfach gespeichert. Die Datenstruktur ist der endlichen Menge aus der Mathematik nachempfunden. Konstante Mengen, deren Inhalt unverändert bleibt, werden aus Effizienzgründen häufig anders dargestellt als dynamische Mengen, deren Inhalt verändert werden kann.

Typische Operationen sind das Erzeugen einer Menge aus Elementen, die Prüfung auf enthaltene Elemente und die Prüfung, ob eine Menge Untermenge einer anderen ist. Außerdem können Schnittmenge, Vereinigung und Differenzmenge gebildet und die Elemente in beliebiger Ordnung aufgezählt werden. Dynamische Mengen erlauben zusätzlich das Hinzufügen und Entfernen einzelner Elemente. Welche dieser Operationen tatsächlich vorhanden sind, hängt von der jeweiligen Anwendung und Implementierung ab.

Möglichkeiten der technischen Umsetzung

Dynamische Mengen werden üblicherweise mithilfe von Hashtabellen oder balancierten Suchbäumen implementiert. Eine Hashtabelle ordnet Elemente über berechnete Schlüssel Speicherplätzen zu. Ein balancierter Suchbaum hält seine Baumstruktur so ausgeglichen, dass Elemente effizient gesucht, eingefügt und entfernt werden können.

Wenn nur Untermengen einer bekannten Grundmenge betrachtet werden, beispielsweise eines Intervalls natürlicher Zahlen, kann ein Feld von Bits verwendet werden. Eine Eins an der Stelle n bedeutet dann etwa, dass das Element n enthalten ist. Übliche Mengenoperationen lassen sich bei dieser Darstellung als binäre Operationen umsetzen. Inklusionstests, also Prüfungen, ob ein bestimmtes Element enthalten ist, sind in konstanter Zeit möglich.

Steht für die Elemente eine binäre Kodierung zur Verfügung, kann eine Menge auch durch ein Binäres Entscheidungsdiagramm dargestellt werden. Dabei entspricht die Menge einer Booleschen Funktion: Für Kodierungen enthaltener Elemente liefert sie Eins, für alle anderen Kodierungen Null. Diese Darstellung kann bei bestimmten sehr großen, aber einfach strukturierten Mengen sinnvoll sein, wie sie beim Model Checking auftreten.

Einige Programmiersprachen, darunter Modula-2, Oberon und Python, haben Mengen direkt in ihren Sprachumfang integriert; der Datentyp wird dabei typischerweise mit „SET“ oder „BITSET“ bezeichnet. In vielen anderen Sprachen gibt es keinen elementaren Mengentyp. Werden Mengenoperationen stattdessen mit ganzzahligen Datentypen ausgeführt, ist die Zuweisungskompatibilität erheblich eingeschränkt, was leicht Programmfehler verursacht. Deshalb ist es im Allgemeinen sicherer, dafür vorgesehene Bibliotheksfunktionen zu implementieren und zu verwenden, beispielsweise die Klasse „Bitset“ in Java.

Mengen in C++

In C++ gehört set zu den assoziativen Containern. Jedes Element muss eindeutig sein, weil sein Wert zugleich zu seiner Identifikation dient. Nach dem Einfügen kann dieser Wert nicht direkt geändert werden. Soll er verändert werden, muss das bisherige Element entfernt und der neue Wert anschließend hinzugefügt werden.

Wichtige Funktionen sind:

• begin(): liefert einen Iterator zum ersten Element. Ein Iterator ist ein Objekt, mit dem die Elemente eines Containers schrittweise durchlaufen werden.
• end(): liefert einen Iterator auf die theoretische Position unmittelbar hinter dem letzten Element.
• size(): liefert die Anzahl der enthaltenen Elemente.
• max_size(): liefert die maximale mögliche Elementanzahl.
• empty(): gibt an, ob die Menge leer ist.

Die C++-Standardbibliothek bietet außerdem Iteratoren, mit denen eine Menge in einer vorgegebenen oder umgekehrten Reihenfolge durchlaufen werden kann.

Im Beispiel wird ein set<string> mit den Vornamen Noah, Oliver, Isabella, Elijah und Emma aufgebaut. Mehrfach eingefügte Namen wie Oliver, Isabella und Elijah erscheinen trotzdem nur einmal. Die Menge enthält deshalb fünf Elemente. In normaler Reihenfolge lautet die Ausgabe „Elijah Emma Isabella Noah Oliver“, in umgekehrter Reihenfolge „Oliver Noah Isabella Emma Elijah“. Nach dem Entfernen von Oliver und Noah bleiben Elijah, Emma und Isabella übrig. Der Versuch, Otto zu entfernen, ändert nichts, weil Otto nicht enthalten ist.

HashSet und Mengenoperationen in C#

Die C#-Klassenbibliothek stellt mit HashSet einen generischen Mengentyp bereit. „Generisch“ bedeutet, dass beim Anlegen festgelegt wird, welchen Elementtyp die Menge enthält, beispielsweise string. Die Kapazität eines HashSet-Objekts wächst automatisch, wenn Elemente hinzugefügt werden. Ein HashSet orientiert sich am Modell mathematischer Mengen, ist nicht sortiert und enthält keine Duplikate.

Zentrale Methoden sind:

• Add(x) fügt x hinzu, Remove(x) entfernt x und Contains(x) prüft, ob x enthalten ist.
• Clear() entfernt alle Elemente, CopyTo(A) kopiert sie in das Array A.
• IntersectWith(S) bildet die Schnittmenge, indem alle nicht in S enthaltenen Elemente entfernt werden.
• UnionWith(S) bildet die Vereinigung, indem die bisher fehlenden Elemente aus S übernommen werden.
• ExceptWith(S) bildet die Differenz, indem alle auch in S enthaltenen Elemente entfernt werden.
• SetEquals(S) prüft, ob beide Mengen dieselben Elemente enthalten.
• IsSubsetOf(S) prüft, ob die Menge eine Teilmenge von S ist; IsSupersetOf(S) prüft, ob sie eine Obermenge von S ist.
• GetEnumerator() liefert einen Enumerator, mit dem die Elemente durchlaufen werden können.

Im Spielkartenbeispiel werden sechs Kartenbezeichnungen in ein HashSet<string> eingefügt. Jede Bezeichnung wird in Symbol und Wert zerlegt. Daraus entstehen eine Symbolmenge mit Herz, Karo und Kreuz sowie eine Wertemenge mit Bube, Dame, König, Ass und 10. Die Anzahlen betragen entsprechend drei und fünf. Eine zusätzliche Methode ToString durchläuft ein HashSet und setzt seine Elemente zu einem Text der Form „(A, B, C, ...)“ zusammen.

Ein weiteres Beispiel veranschaulicht Schnittmenge, Vereinigung und Differenz anhand wissenschaftlicher, künstlerischer, handwerklicher und politischer Berufe. Die Schnittmenge aus wissenschaftlichen und politischen Berufen enthält nur „Forschungsminister“. Für die nicht handwerklichen Berufe werden wissenschaftliche, künstlerische und politische Berufe vereinigt und anschließend die handwerklichen Berufe entfernt. Das Ergebnis enthält „Informatiker, Physiker, Biologe, Forschungsminister, Musiker, Autor, Maler, Kulturminister, Regierungschef, Abgeordneter“. Für die nicht politischen Berufe werden wissenschaftliche, künstlerische und handwerkliche Berufe vereinigt und danach die politischen Berufe entfernt. Übrig bleiben „Informatiker, Physiker, Biologe, Ingenieur, Musiker, Autor, Maler, Bildhauer, Bauarbeiter, Installateur“.