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:

Hinzufügen und Entfernen einzelner Elemente.

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.^[1]

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.^[2]

#include <set> // Bindet den Datentyp set in das Programm ein
#include <iostream>

using namespace std;

int main()
{
    set<string> mySet; // Deklariert eine Menge mit dem Elementtyp string

    // Fügt Elemente vom Typ string in die Menge ein
    mySet.insert("Noah");
    mySet.insert("Oliver");
    mySet.insert("Oliver"); // Duplikat
    mySet.insert("Isabella");
    mySet.insert("Oliver"); // Duplikat
    mySet.insert("Elijah");
    mySet.insert("Emma");
    mySet.insert("Isabella"); // Duplikat
    mySet.insert("Isabella"); // Duplikat
    mySet.insert("Elijah"); // Duplikat

    cout << "Die Menge enthält " << mySet.size() << " Elemente." << endl; // Gibt die Anzahl der Elemente aus

    set<string>::iterator mySetIterator = mySet.begin(); // Deklariert einen Iterator auf der Menge
    set<string>::reverse_iterator mySetReverseIterator = mySet.rbegin(); // Deklariert einen inversen Iterator auf der Menge

    cout << "Der erste Name der Menge ist: " << *mySetIterator << endl; // Ausgabe auf der Konsole ("Elijah")
    cout << "Der letzte Name der Menge ist: " << *mySetReverseIterator << endl; // Ausgabe auf der Konsole ("Oliver")

    cout << "Elemente in normaler Reihenfolge:";
    for (mySetIterator = mySet.begin(); mySetIterator != mySet.end(); mySetIterator++) // for-Schleife mit Iterator
    {
        cout << " " << *mySetIterator; // Ausgabe auf der Konsole ("Elijah Emma Isabella Noah Oliver")
    }
    cout << endl;

    cout << "Elemente in umgekehrter Reihenfolge:";
    for (mySetReverseIterator = mySet.rbegin(); mySetReverseIterator != mySet.rend(); mySetReverseIterator++) // for-Schleife mit inversem Iterator
    {
        cout << " " << *mySetReverseIterator; // Ausgabe auf der Konsole ("Oliver Noah Isabella Emma Elijah")
    }
    cout << endl;

    // Entfernt Elemente vom Typ string aus der Menge
    mySet.erase("Oliver");
    mySet.erase("Noah");
    mySet.erase("Otto"); // Entfernt kein Element, weil "Otto" nicht in der Menge vorhanden ist

    cout << "Die Menge enthält " << mySet.size() << " Elemente." << endl; // Gibt die Anzahl der Elemente aus

    cout << "Elemente in normaler Reihenfolge:";
    for (mySetIterator = mySet.begin(); mySetIterator != mySet.end(); mySetIterator++) // for-Schleife mit Iterator
    {
        cout << " " << *mySetIterator; // Ausgabe auf der Konsole ("Elijah Emma Isabella")
    }
    cout << endl;

    cout << "Elemente in umgekehrter Reihenfolge:";
    for (mySetReverseIterator = mySet.rbegin(); mySetReverseIterator != mySet.rend(); mySetReverseIterator++) // for-Schleife mit inversem Iterator
    {
        cout << " " << *mySetReverseIterator; // Ausgabe auf der Konsole ("Isabella Emma Elijah")
    }
    cout << endl;
}

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.^[3]

public static void Main(string[] args)
{
	// Deklariert drei HashSets mit dem Elementtyp string
	HashSet<string> cardSet = new HashSet<string>();
	HashSet<string> cardSymbolSet = new HashSet<string>();
	HashSet<string> cardValueSet = new HashSet<string>();
	
	// Fügt der Menge cardSet 6 Elemente vom Typ string hinzu
	cardSet.Add("Herz Bube");
	cardSet.Add("Herz Dame");
	cardSet.Add("Karo König");
	cardSet.Add("Kreuz Ass");
	cardSet.Add("Kreuz 10");
	cardSet.Add("Karo Ass");
	
	foreach (string card in cardSet) // foreach-Schleife, die alle Elemente von cardSet durchläuft
	{
		string[] tokens = card.Split(new char[]{' '}, StringSplitOptions.None); // Zerlegt die Bezeichnung der Spielkarte in Wörter und weist sie einem Array mit dem Elementtyp string zu
		string cardSymbol = tokens[0];
		cardSymbolSet.Add(cardSymbol); // Fügt das erste Wort (Symbol der Spielkarte) der Menge cardSymbolSet hinzu
		string cardValue = tokens[1];
		cardValueSet.Add(cardValue); // Fügt das zweite Wort (Wert der Spielkarte) der Menge cardValueSet hinzu
	}
	
	int n = cardSymbolSet.Count; // Weist die Anzahl der Elemente von cardSymbolSet der Variablen n zu
	Console.WriteLine("Die Anzahl der Symbole ist " + n); // Ausgabe auf der Konsole
	Console.WriteLine(ToString(cardSymbolSet)); // Ausgabe auf der Konsole: (Herz, Karo, Kreuz)
	
	n = cardValueSet.Count; // Weist die Anzahl der Elemente von cardValueSet der Variablen n zu
	Console.WriteLine("Die Anzahl der Werte ist " + n); // Ausgabe auf der Konsole
	Console.WriteLine(ToString(cardValueSet)); // Ausgabe auf der Konsole: (Bube, Dame, König, Ass, 10)
	
	Console.ReadLine();
}

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

// Diese Methode gibt das HashSet in der Form (A, B, C, ...) als Text zurück.
public static string ToString(HashSet<string> aHashSet)
{
	string text = "(";
	foreach (string element in aHashSet) // foreach-Schleife, die alle Elemente durchläuft
	{
		text += element + ", ";
	}
	text = text.Substring(0, text.Length - 2);
	text += ")";
	return text;
}

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

public static void Main(string[] args)
{
	// Deklariert und initialisiert vier HashSets mit dem Elementtyp string
	HashSet<string> scientificProfessions = new HashSet<string>(){"Informatiker", "Physiker", "Biologe", "Ingenieur", "Forschungsminister"};
	HashSet<string> artisticProfessions = new HashSet<string>(){"Musiker", "Autor", "Maler", "Bildhauer", "Kulturminister"};
	HashSet<string> manualOccupations = new HashSet<string>(){"Bauarbeiter", "Installateur", "Ingenieur", "Bildhauer"};
	HashSet<string> politicalProfessions = new HashSet<string>(){"Regierungschef", "Forschungsminister", "Kulturminister", "Abgeordneter"};
	
	HashSet<string> scientificAndPoliticalProfessions = new HashSet<string>(politicalProfessions); // Initialisiert das HashSets mit den Elementen von politicalProfessions
	scientificAndPoliticalProfessions.IntersectWith(scientificProfessions); // Bildet die Schnittmenge mit scientificProfessions
	Console.WriteLine(ToString(scientificAndPoliticalProfessions)); // Ausgabe auf der Konsole: (Forschungsminister)
	
	HashSet<string> nonManualOccupations = new HashSet<string>(scientificProfessions); // Initialisiert das HashSets mit den Elementen von scientificProfessions
	nonManualOccupations.UnionWith(artisticProfessions); // Bildet die Vereinigungsmenge mit artisticProfessions
	nonManualOccupations.UnionWith(politicalProfessions); // Bildet die Vereinigungsmenge mit politicalProfessions
	nonManualOccupations.ExceptWith(manualOccupations); // Bildet die Differenzmenge mit manualOccupations
	Console.WriteLine(ToString(nonManualOccupations)); // Ausgabe auf der Konsole: (Informatiker, Physiker, Biologe, Forschungsminister, Musiker, Autor, Maler, Kulturminister, Regierungschef, Abgeordneter)
	
	HashSet<string> nonPoliticalProfessions = new HashSet<string>(scientificProfessions); // Initialisiert das HashSets mit den Elementen von scientificProfessions
	nonPoliticalProfessions.UnionWith(artisticProfessions); // Bildet die Vereinigungsmenge mit artisticProfessions
	nonPoliticalProfessions.UnionWith(manualOccupations); // Bildet die Vereinigungsmenge mit manualOccupations
	nonPoliticalProfessions.ExceptWith(politicalProfessions); // Bildet die Differenzmenge mit politicalProfessions
	Console.WriteLine(ToString(nonPoliticalProfessions)); // Ausgabe auf der Konsole: (Informatiker, Physiker, Biologe, Ingenieur, Musiker, Autor, Maler, Bildhauer, Bauarbeiter, Installateur)
	
	Console.ReadLine();
}

Siehe auch

Literatur

Guido van Rossum: Python Library Reference. 2006

Weblinks

std::set. In: cplusplus.com. Abgerufen am 29. April 2021 (englisch, Set in C++ Standard Template Library (STL)).
Set in C++ Standard Template Library (STL). GeeksforGeeks, 23. März 2021; abgerufen am 29. April 2021 (englisch).
std::set. In: cppreference.com. 11. August 2020; abgerufen am 29. April 2021 (englisch, Datentyp set in C++).
C# | HashSet Class. GeeksforGeeks, 20. Dezember 2018; abgerufen am 27. April 2021 (englisch).

Einzelnachweise

↑ Gary D Hachtel, Fabio Somenzi: Logic Synthesis and Verification Algorithms. Kluwer Academic, Boston, Mass. / London 1996, ISBN 0-7923-9746-0, S. 219 (englisch).
↑ set Class. In: Microsoft Docs. 9. September 2020, abgerufen am 29. April 2021 (englisch).
↑ HashSet<T> Class. In: Microsoft Docs. Abgerufen am 1. Mai 2021 (englisch).

[1] Gary D Hachtel, Fabio Somenzi: Logic Synthesis and Verification Algorithms. Kluwer Academic, Boston, Mass. / London 1996, ISBN 0-7923-9746-0, S. 219 (englisch).

[2] set Class. In: Microsoft Docs. 9. September 2020, abgerufen am 29. April 2021 (englisch).

[3] HashSet<T> Class. In: Microsoft Docs. Abgerufen am 1. Mai 2021 (englisch).

[1]

[2]

[3]