Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::unordered_set — skup jedinstvenih ključeva

std::unordered_set pohranjuje jedinstvene ključeve uz pomoć hashiranja. Omogućuje provjeru prisutnosti, umetanje i uklanjanje elemenata, ali ne jamči redoslijed iteriranja. Uobičajene operacije imaju prosječnu konstantnu složenost, a u najgorem slučaju linearnu.

Verzija: C++23; repository compiler flag, production runtime not attested

Sintaksa

#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 iz zaglavlja <unordered_set> neuređeni je asocijativni spremnik: svaki je element ujedno i svoj ključ, a skup sadrži najviše jedan element iz svakog razreda ekvivalencije. Parametri Hash i Pred određuju hashiranje i ekvivalenciju; zadane su vrijednosti std::hash<Key> i std::equal_to<Key>. Ekvivalentni ključevi moraju imati isti hash; isti hash ne znači da su ključevi ekvivalentni.

insert(value).second pokazuje je li element dodan. contains(value) provjerava prisutnost, find(value) vraća iterator ili end(), a erase(value) vraća broj uklonjenih elemenata: ovdje 0 ili 1. Pretraživanje, umetanje jednog elementa i uklanjanje prema ključu imaju prosječnu složenost O(1), a u najgorem slučaju O(n).

Redoslijed iteriranja nije određen. Ključeve nije moguće mijenjati putem iteratora; umjesto toga uklonite stari ključ i umetnite novi. Ponovno hashiranje poništava iteratore, ali ne i pokazivače ni reference na elemente. Umetanje može pokrenuti ponovno hashiranje; reserve(n) priprema dovoljno pretinaca za n elemenata uz trenutačni najveći faktor popunjenosti i također može poništiti iteratore. Uklanjanje elementa poništava njegove iteratore, pokazivače i reference.

Primjer ne ispisuje elemente iteriranjem, pa očekivani izlaz ne ovisi o njihovu redoslijedu. Ovaj je unos namijenjen za C++23; zastavica prevoditelja u repozitoriju ne potvrđuje produkcijsko okruženje. Priloženi radni nacrt ažurira se tijekom vremena i može sadržavati značajke novije od C++23.

Primjeri

#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';
}

Rezultat

inserted: false
contains 3: true
erased: 1
size: 1

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori