Menge (Datenstruktur)
# Menge (Datenstruktur)

Die Datenstruktur Menge, auch Set genannt, ist eine ungeordnete Sammlung von Elementen eines bestimmten Datentyps, von denen jeweils maximal ein Exemplar enthalten ist. Sie ist der endlichen Menge in der Mathematik nachempfunden. Es ist meist aus Effizienzgründen sinnvoll, konstante Mengen anders zu repräsentieren als dynamische Mengen.

Zu den verfügbaren Operationen zählen meist:

* Erzeugen einer Menge aus den Elementen
* Prüfung, ob ein Element bereits enthalten ist.
* Prüfung, ob eine Menge Untermenge einer anderen ist.
* Bildung von Schnittmenge, Vereinigung, Differenzmenge usw.
* Aufzählen der Elemente der Menge in einer beliebigen Ordnung

Dynamische Mengen unterstützen zusätzlich folgende Funktion:

Je nach Anwendung können jeweils mehr oder weniger der genannten Operationen implementiert werden.

## Implementation

Dynamische Mengen werden üblicherweise mit Datenstrukturen wie Hashtabellen oder balancierten Suchbäumen implementiert.

Wenn ausschließlich Untermengen einer bekannten Menge behandelt werden (z. B. ein Intervall der natürlichen Zahlen), ist auch eine Darstellung als Feld von Bits möglich. Dabei stellt beispielsweise eine Eins an Stelle n dar, dass das Element n in der Menge enthalten ist. Die üblichen Mengenoperationen lassen sich dann gut als binäre Operationen implementieren. Inklusionstests lassen sich dann in konstanter Zeit durchführen.

Wenn eine binäre Kodierung für die Elemente einer Menge verfügbar ist, können Mengen auch als Binäres Entscheidungsdiagramm repräsentiert werden. Dabei wird die Menge als Boolesche Funktion repräsentiert, die für die Kodierung ihrer Elemente Eins, für alle anderen Kodierungen Null ergibt. Das kann für bestimmte sehr große, aber einfach strukturierte Mengen sinnvoll sein, wie sie etwa beim Model Checking auftreten können.

Einige Programmiersprachen, wie zum Beispiel Modula-2, Oberon oder Python, haben Mengen im Sprachumfang integriert, wobei dieser Datentyp dann typischerweise mit "SET" oder "BITSET" deklariert wird. Viele Programmiersprachen haben allerdings keinen elementaren Datentyp für Mengen im Definitionsumfang, und da in diesen Fällen oft Mengenoperationen mit ganzzahligen Datentypen zugelassen sind, ist die Zuweisungskompatibilität erheblich eingeschränkt, was leicht zu Programmfehlern führen kann. Daher ist es im Allgemeinen wesentlich besser und sicherer, Bibliotheksfunktionen für Mengenoperationen zu implementieren und zu benutzen (siehe zum Beispiel in Java die Klasse "Bitset").

## Programmierung

### C++

In der Programmiersprache C++ sind Mengen ein Datentyp von assoziativen Containern, in denen jedes Element eindeutig sein muss, weil der Wert des Elements es identifiziert. Der Wert des Elements kann nicht geändert werden, sobald es der Menge hinzugefügt wurde. Es ist jedoch möglich, den geänderten Wert dieses Elements zu entfernen und hinzuzufügen. Einige grundlegende Funktionen des Datentyps Set in C++ sind:

* begin: Gibt einen Iterator zum ersten Element in der Menge zurück.
* end: Gibt einen Iterator zu dem theoretischen Element zurück, das auf das letzte Element in der Menge folgt.
* size: Gibt die Anzahl der Elemente in der Menge zurück.
* max_size: Gibt die maximale Anzahl von Elementen zurück, die die Menge enthalten kann.
* empty: Gibt zurück, ob die Menge leer ist.

Außerdem stellt die C++-Standardbibliothek Methoden für die Verwendung eines Iterators zur Verfügung, der die Elemente der Menge in einer vorgegebenen Reihenfolge durchläuft.

Das folgende Beispiel mit Vornamen zeigt die Verwendung der Klasse set der C++-Standardbibliothek (siehe auch Template (C++) - Klassen-Templates). Bei der Ausführung des Programms wird die Methode main verwendet.

### C#

Die Klassenbibliothek der Programmiersprache C# stellt die Klasse HashSet zur Verfügung, die eine Menge als generischen Typ implementiert. Die Kapazität eines Objekts vom Typ HashSet erhöht sich automatisch, wenn dem Objekt Elemente hinzugefügt werden. Die Klasse HashSet basiert auf dem Modell mathematischer Mengen und bietet Methoden für Mengenoperationen an. Ein HashSet ist nicht sortiert und kann keine mehrfachen Elemente (Duplikate) enthalten.

Einige grundlegende Methoden der Klasse HashSet in C# sind:

* Add(x): Fügt das Element x der Menge hinzu.
* Remove(x): Entfernt das Element x aus der Menge.
* Contains(x): Bestimmt, ob die Menge das Element x enthält.
* Clear: Entfernt alle Elemente der Menge.
* CopyTo(A): Kopiert alle Elemente der Menge in das Array A.
* IntersectWith(S): Bildet die Schnittmenge mit der Menge S, indem alle Elemente entfernt werden, die die Menge S nicht enthält.
* UnionWith(S): Bildet die Vereinigungsmenge mit der Menge S, indem alle Elemente von S in die Menge kopiert werden, die die Menge nicht enthält.
* ExceptWith(S): Bildet die Differenzmenge mit der Menge S, indem alle Elemente entfernt werden, die die Menge S enthält.
* SetEquals(S): Bestimmt, ob die Menge und die Menge S dieselben Elemente enthalten.
* IsSubsetOf(S): Bestimmt, ob die Menge eine Teilmenge der Menge S ist.
* IsSupersetOf(S): Bestimmt, ob die Menge eine Obermenge der Menge S ist.
* GetEnumerator: Gibt ein Objekt der Klasse Enumerator zurück, das durch die Elemente der Menge iterieren kann.

Das folgende Beispiel in der Programmiersprache C# mit Spielkarten zeigt die Verwendung des generischen Typs HashSet mit Typparameter string. Die Bezeichnungen der Spielkarten werden der ersten Menge hinzugefügt und jeweils in Symbol und Wert zerlegt. Die Symbole werden der zweiten Menge und die Werte werden der dritten Menge hinzugefügt. Anschließend werden die Symbole und Werte und ihre Anzahl auf der Konsole ausgegeben.

Für die Ausgabe des HashSet wird folgende Methode verwendet:

Das folgende Beispiel mit Berufen und politischen Ämtern zeigt die Verwendung der Methoden IntersectWith(...), UnionWith(...) und ExceptWith(...):

