CKTIS / C++
std::unordered_set — množina jedinečných kľúčov
std::unordered_set ukladá jedinečné kľúče pomocou hashovania. Umožňuje overiť prítomnosť, vkladať a odoberať prvky, no nezaručuje poradie iterácie. Bežné operácie majú priemernú konštantnú zložitosť, v najhoršom prípade však lineárnu.
Verzia: 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 z hlavičky <unordered_set> je neusporiadaný asociatívny kontajner: každý prvok je zároveň svojím kľúčom a množina obsahuje najviac jeden prvok z každej triedy ekvivalencie. Parametre Hash a Pred určujú hashovanie a ekvivalenciu; predvolené hodnoty sú std::hash<Key> a std::equal_to<Key>. Ekvivalentné kľúče musia mať rovnaký hash; rovnaký hash však neznamená, že kľúče sú ekvivalentné.
insert(value).second udáva, či sa prvok pridal. contains(value) overuje prítomnosť, find(value) vracia iterátor alebo end() a erase(value) vracia počet odstránených prvkov: tu 0 alebo 1. Vyhľadávanie, vloženie jedného prvku a odstránenie podľa kľúča majú priemernú zložitosť O(1) a v najhoršom prípade O(n).
Poradie iterácie nie je určené. Kľúče nemožno meniť pomocou iterátorov; namiesto toho odstráňte starý kľúč a vložte nový. Rehashovanie zneplatňuje iterátory, nie však ukazovatele ani referencie na prvky. Vkladanie môže spustiť rehashovanie; reserve(n) pripraví dostatok bucketov pre n prvkov pri aktuálnom maximálnom faktore zaplnenia a môže tiež zneplatniť iterátory. Odstránenie prvku zneplatní jeho iterátory, ukazovatele a referencie.
Príklad nevypisuje prvky prechádzaním, takže očakávaný výstup nezávisí od ich poradia. Tento záznam sa týka C++23; príznak kompilátora v repozitári nepotvrdzuje produkčné prostredie. Dodaný pracovný návrh sa priebežne aktualizuje a môže obsahovať funkcie z neskorších verzií než C++23.
Príklady
#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';
}
Výsledok
inserted: false contains 3: true erased: 1 size: 1
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.