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.