CKTIS / C++
std::unordered_set — množica enoličnih ključev
std::unordered_set shranjuje enolične ključe s pomočjo zgoščevanja. Omogoča preverjanje prisotnosti, vstavljanje in odstranjevanje elementov, ne zagotavlja pa vrstnega reda iteriranja. Običajne operacije imajo povprečno konstantno, v najslabšem primeru pa linearno časovno zahtevnost.
Različica: 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 glave <unordered_set> je neurejen asociativni vsebnik: vsak element je hkrati svoj ključ, množica pa vsebuje največ en element iz vsakega ekvivalenčnega razreda. Parametra Hash in Pred določata zgoščevanje in ekvivalenco; privzeti vrednosti sta std::hash<Key> in std::equal_to<Key>. Ekvivalentni ključi morajo imeti enak hash; enak hash pa ne pomeni, da so ključi ekvivalentni.
insert(value).second pove, ali je bil element dodan. contains(value) preveri prisotnost, find(value) vrne iterator ali end(), erase(value) pa vrne število odstranjenih elementov: tukaj 0 ali 1. Iskanje, vstavljanje posameznega elementa in odstranjevanje po ključu imajo povprečno zahtevnost O(1), v najslabšem primeru pa O(n).
Vrstni red iteriranja ni določen. Ključev ni mogoče spreminjati prek iteratorjev; namesto tega odstranite stari ključ in vstavite novega. Ponovno zgoščevanje razveljavi iteratorje, ne pa kazalcev ali referenc na elemente. Vstavljanje lahko sproži ponovno zgoščevanje; reserve(n) pripravi dovolj vedri za n elementov pri trenutnem največjem faktorju obremenitve in lahko prav tako razveljavi iteratorje. Odstranitev elementa razveljavi njegove iteratorje, kazalce in reference.
Primer elementov ne izpisuje z iteriranjem, zato pričakovani izpis ni odvisen od njihovega vrstnega reda. Ta zapis je namenjen C++23; zastavica prevajalnika v repozitoriju ne potrjuje produkcijskega okolja. Priloženi delovni osnutek se posodablja in lahko vsebuje funkcije iz različic po C++23.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.