Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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.

Zdroje