C++ set: eindeutige, sortierte Elemente mit std::set

Eine Sammlung eindeutiger, sortierter Werte

Du hast gesehen, wie unordered_map Schlüssel-Wert-Paare mit schneller hashbasierter Suche speichert. Ein std::set ist der einfachere Cousin: Es speichert nur Werte – keine zugehörigen Daten – und erzwingt zwei Regeln automatisch. Jedes Element ist eindeutig (Duplikate werden stillschweigend verworfen) und die Elemente werden stets in sortierter Reihenfolge gehalten.

Damit ist set die natürliche Wahl für Fragen wie „Habe ich das schon einmal gesehen?" oder „Gib mir die verschiedenen Elemente in sortierter Reihenfolge." Du fügst ein, ohne dir Gedanken über Duplikate zu machen, und iterierst, ohne vorher zu sortieren.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // Duplikat - ignoriert

    for (int x : s) cout << x << " ";   // 10 30 40 (sortiert, ohne Wiederholung)
}

Beachte, dass wir 10 zweimal und in falscher Reihenfolge eingefügt haben, und trotzdem ist die Ausgabe sortiert und 10 erscheint nur einmal. Das set hat die Buchführung für dich übernommen.

Einfügen und Entfernen

insert fügt einen Wert hinzu, wenn er noch nicht vorhanden ist. Es gibt ein pair zurück, dessen .second ein bool ist, der dir sagt, ob das Einfügen tatsächlich stattgefunden hat – praktisch, wenn du wissen willst, ob ein Wert neu war:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Um einen Wert zu entfernen, rufe erase mit dem Wert selbst auf – es gibt die Anzahl der entfernten Elemente zurück (0 oder 1 bei einem set). Etwas zu löschen, das nicht vorhanden ist, ist harmlos und kein Fehler:

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // entfernt 3
    s.erase(99);         // tut nichts, gibt 0 zurück

    for (int x : s) cout << x << " ";   // 1 2 4
}

Mitgliedschaft prüfen

Der ganze Sinn eines set sind schnelle „Ist das hier drin?"-Tests. Am klarsten geht das mit count, das 1 oder 0 zurückgibt:

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Seit C++20 gibt es eine noch besser lesbare Option, contains, die direkt einen bool zurückgibt:

if (primes.contains(7)) { /* ... */ }   // C++20

Ein häufiger Fehler ist, zu operator[] zu greifen, wie man es bei einer map täte. Ein set hat kein operator[] – es gibt keinen Wert zum Abrufen, nur das Vorhandensein zum Prüfen. Verwende count oder contains, nicht s[7].

Wenn du die tatsächliche Position brauchst (um sie zu löschen oder die Nachbarn anzusehen), verwende find, das einen Iterator oder end() zurückgibt:

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

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

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // per Iterator löschen - keine zweite Suche
    }
    cout << "size now " << s.size() << "\n";
}

Sortierte Iteration und Bereichsabfragen

Da ein set sortiert ist, liefert die Iteration die Elemente immer vom kleinsten zum größten, und du bekommst die Tricks sortierter Container gratis dazu. lower_bound(x) liefert das erste Element, das nicht kleiner als x ist, und upper_bound(x) das erste Element, das echt größer als x ist – zusammen erlauben sie dir, einen Zahlenbereich zu durchlaufen, ohne jedes Element zu prüfen:

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // alles im Bereich [12, 31] ausgeben
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Eine subtile, aber wichtige Regel: set-Elemente sind unveränderlich. Der Iterator gibt dir eine const-Referenz, du kannst ein Element also nicht an Ort und Stelle ändern – das könnte die Sortierreihenfolge zerstören, auf die sich der Container verlässt. Um einen Wert zu „ändern", lösche den alten und füge den neuen ein.

Standardmäßig ist die Sortierung aufsteigend (std::less). Für eine absteigende Reihenfolge gib einen anderen Vergleichsoperator als zweites Template-Argument an:

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set ist einer von drei engen Verwandten, und die richtige Wahl ist wichtig:

set<int>            // eindeutige Werte, sortiert, O(log n)
multiset<int>       // erlaubt Duplikate, sortiert, O(log n)
unordered_set<int>  // eindeutige Werte, KEINE Reihenfolge, durchschnittlich O(1)

Greife zu unordered_set, wenn du nur Mitgliedschaftstests brauchst und die Reihenfolge egal ist – seine hashbasierten Suchen sind im Durchschnitt schneller als das baumbasierte O(log n) des set. Wähle set, wenn du Elemente in sortierter Reihenfolge, Bereichsabfragen mit lower_bound/upper_bound oder stabiles Iteratorverhalten brauchst. Verwende multiset nur, wenn Duplikate von Bedeutung sind (zum Beispiel ein Histogramm wiederholter Werte): In einem multiset kann count(x) mehr als 1 zurückgeben, und erase(x) entfernt alle Kopien, sofern du nicht über einen einzelnen Iterator löschst.

Ein klassischer Einsatz von set: einen vector in einem Schritt entduplizieren und sortieren.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Das set aus den Iteratoren des vector zu konstruieren, verwirft jedes Duplikat und sortiert den Rest – keine manuelle Schleife, kein std::sort-plus-std::unique-Tanz.

Als Nächstes: pair und tuple

Du hast jetzt gesehen, wie .first und .second auf dem pair auftauchen, das insert zurückgibt, und wie strukturierte Bindungen (auto [it, inserted]) es sauber entpacken. Diese leichtgewichtigen Typen zum „Bündeln einiger Werte" sind überall in der STL. Als Nächstes betrachten wir pair und tuple direkt – wie man sie erstellt, entpackt und mehrere Werte aus einer Funktion zurückgibt, ohne eine ganze struct zu definieren.