CKTIS / C++
std::unordered_set — eine Menge eindeutiger Schlüssel
std::unordered_set speichert eindeutige Schlüssel mithilfe von Hashing. Der Container unterstützt Abfragen, Einfügen und Entfernen, ohne eine Iterationsreihenfolge zu garantieren. Übliche Operationen haben durchschnittlich konstante, im ungünstigsten Fall jedoch lineare Komplexität.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <unordered_set>
std::unordered_set<Key, Hash, Pred, Allocator> values;
// Defaults: Hash = std::hash<Key>, Pred = std::equal_to<Key>,
// Allocator = std::allocator<Key>std::unordered_set aus <unordered_set> ist ein ungeordneter assoziativer Container: Jedes Element ist zugleich sein Schlüssel, und die Menge enthält höchstens ein Element aus jeder Äquivalenzklasse. Die Parameter Hash und Pred legen Hashing und Äquivalenz fest; standardmäßig sind dies std::hash<Key> und std::equal_to<Key>. Äquivalente Schlüssel müssen denselben Hashwert haben; gleiche Hashwerte bedeuten jedoch nicht, dass die Schlüssel äquivalent sind.
insert(value).second gibt an, ob ein Element hinzugefügt wurde. contains(value) prüft, ob ein Element vorhanden ist, find(value) liefert einen Iterator oder end(), und erase(value) gibt die Anzahl der entfernten Elemente zurück: hier 0 oder 1. Suchen, das Einfügen eines einzelnen Elements und das Entfernen anhand eines Schlüssels haben durchschnittlich die Komplexität O(1) und im ungünstigsten Fall O(n).
Die Iterationsreihenfolge ist nicht festgelegt. Schlüssel lassen sich nicht über Iteratoren ändern; stattdessen wird der alte Schlüssel entfernt und ein neuer eingefügt. Ein Rehash macht Iteratoren ungültig, nicht aber Zeiger oder Referenzen auf Elemente. Einfügen kann einen Rehash auslösen; reserve(n) stellt bei der aktuellen maximalen Lastfaktor-Einstellung genügend Buckets für n Elemente bereit und kann ebenfalls Iteratoren ungültig machen. Das Entfernen eines Elements macht dessen Iteratoren, Zeiger und Referenzen ungültig.
Das Beispiel gibt keine Elemente durch Iteration aus, daher hängt die erwartete Ausgabe nicht von ihrer Reihenfolge ab. Dieser Eintrag bezieht sich auf C++23; eine Compileroption im Repository bestätigt nicht die Produktionsumgebung. Der angegebene Arbeitsentwurf wird laufend aktualisiert und kann Funktionen enthalten, die erst nach C++23 eingeführt wurden.
Beispiele
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> values{3, 1, 3};
const bool inserted = values.insert(1).second;
std::cout << std::boolalpha;
std::cout << "inserted: " << inserted << '\n';
std::cout << "contains 3: " << values.contains(3) << '\n';
std::cout << "erased: " << values.erase(3) << '\n';
std::cout << "size: " << values.size() << '\n';
}
Ergebnis
inserted: false contains 3: true erased: 1 size: 1
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.