Einzigartige Elemente mit std::set und std::multiset in C++

In der C++-Standardbibliothek sind set und multiset assoziative Container, die Elemente in sortierter Form speichern und auf baumbasierten Strukturen arbeiten. Der grundlegende Unterschied besteht darin, dass set jedes Element nur einmal speichert, während multiset mehrere Vorkommen desselben Elements zulässt. Beide basieren auf einem Rot-Schwarz-Baum und sorgen für automatische Sortierung.

1) Was ist set?

std::set ist ein Container, der jedes Element genau einmal speichert und diese automatisch in sortierter Reihenfolge hält.

• Elemente werden immer aufsteigend sortiert.
• Keine doppelten Elemente erlaubt.
• Einfügen, Suchen und Löschen: O(log n)
• Kein direkter Indexzugriff → Iteration erforderlich.

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> numbers;

    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // Duplikate werden ignoriert

    for (int n : numbers)
        cout << n << " ";
}

Ausgabe: 10 20 30

2) Eigenschaften von set

• Sortierte Speicherung
• Alle Elemente sind einzigartig
• O(log n) für Einfügen und Suchen
• Unterstützt lower_bound / upper_bound

// Element suchen
set<int> s = {10, 20, 30};

if (s.contains(20))
    cout << "Gefunden!";

3) Was ist multiset?

std::multiset ähnelt set, erlaubt jedoch mehrfache Vorkommen desselben Elements.

• Elemente werden sortiert gespeichert.
• Duplikate sind erlaubt.
• Einfügen, Suchen und Löschen: O(log n)
• Kein direkter Indexzugriff.

#include <set>
#include <iostream>
using namespace std;

int main() {
    multiset<int> nums;

    nums.insert(20);
    nums.insert(10);
    nums.insert(20);  // Duplikat erlaubt
    nums.insert(30);

    for (int n : nums)
        cout << n << " ";
}

Ausgabe: 10 20 20 30

4) Zählen von Elementen in multiset

multiset<int> ms = {10, 20, 20, 30};

cout << "Anzahl von 20: " << ms.count(20) << endl;

Ausgabe: Anzahl von 20: 2

5) Vergleich: set vs multiset

Fazit: Wenn nur einzigartige Elemente benötigt werden → set. Wenn Duplikate gespeichert werden sollen → multiset.

6) Sortierter Zugriff und Bereichsabfragen

set<int> s = {10, 20, 30, 40, 50};

auto it = s.lower_bound(25); // erstes Element >= 25
cout << *it << endl;

it = s.upper_bound(30); // erstes Element > 30
cout << *it << endl;

7) Löschoperationen

set<int> s = {10, 20, 30};

s.erase(20);        // nach Schlüssel löschen
s.erase(s.begin()); // per Iterator löschen

multiset<int> ms = {10, 20, 20, 30};

ms.erase(20); // löscht ALLE Elemente mit dem Wert 20

8) Praxisbeispiel – Worthäufigkeitsanalyse

Wörter mit multiset zählen

#include <set>
#include <iostream>
#include <string>
using namespace std;

int main() {
    multiset<string> words;

    words.insert("hallo");
    words.insert("welt");
    words.insert("hallo");
    words.insert("cpp");

    cout << "Anzahl von 'hallo': " << words.count("hallo") << endl;

    for (auto& w : words)
        cout << w << " ";
}

9) Wann sollte man welches verwenden?

• Einzigartige Elemente erforderlich → set
• Duplikate erlaubt → multiset
• Beide sind geeignet für sortierte Daten
• Beide arbeiten mit O(log n) Komplexität

Zusammenfassung:
set = einzigartige Elemente
multiset = mehrere gleiche Elemente
beide sortieren Elemente automatisch.

10) TL;DR

Ähnliche Artikel