Wann sollte man std::set und wann std::unordered_set in C++ verwenden?

std::set und std::unordered_set werden zum Speichern von eindeutigen Elementen verwendet. Die Wahl zwischen ihnen hängt von den Prioritäten ab: Sortierung oder Leistung bei Zugriff, Einfügen und Löschen.

std::set basiert auf einem balancierten binären Suchbaum (in der Regel ein Rot-Schwarz-Baum).

Eigenschaften von std::set:

• Elemente werden in sortierter Reihenfolge gespeichert.
• Einfügen, Löschen und Suchen von Elementen dauern im Durchschnitt O(log N), wobei N die Anzahl der Elemente ist.
• Geeignet, wenn die sortierte Reihenfolge der Elemente wichtig ist oder wenn Elemente in einem bestimmten Bereich abgerufen werden sollen.

std::unordered_set basiert auf einer Hashtabelle.

Eigenschaften von std::unordered_set:

• Elemente werden nicht in sortierter Reihenfolge gespeichert.
• Einfügen, Löschen und Suchen von Elementen dauern im Durchschnitt O(1), im schlimmsten Fall (bei vielen Kollisionen in der Hash-Funktion) können sie O(N) erreichen.
• Erfordert, dass der Elementtyp eine definierte Hash-Funktion (std::hash) und einen Gleichheitsoperator (operator==) hat.
• Geeignet, wenn maximale Geschwindigkeit beim Einfügen, Löschen und Suchen erforderlich ist und die Reihenfolge der Elemente keine Rolle spielt.

Zusammenfassungstabelle:

Kriterium	std::set	std::unordered_set
Interne Struktur	Balancierter Baum	Hash-Tabelle
Reihenfolge der Elemente	Sortiert	Nicht sortiert
Durchschnittliche Such-/Einfüge-/Löschzeit	O(log N)	O(1)
Schlimmste Such-/Einfüge-/Löschzeit	O(log N)	O(N)
Anforderungen an den Typ	Operator <	std::hash, operator==

Beispiel für die Verwendung von std::set:

#include <iostream>
#include <set>

int main() {
    std::set<int> ordered_set;
    ordered_set.insert(5);
    ordered_set.insert(2);
    ordered_set.insert(8);

    // Elemente werden in sortierter Reihenfolge ausgegeben: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Beispiel für die Verwendung von std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> unordered_set;
    unordered_set.insert(5);
    unordered_set.insert(2);
    unordered_set.insert(8);

    // Die Ausgabe-Reihenfolge kann variieren
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}