CKTIS / C++
std::unordered_set — množina jedinečných klíčů
std::unordered_set ukládá jedinečné klíče pomocí hashování. Umožňuje ověřit přítomnost, vkládat a odebírat prvky, ale nezaručuje pořadí iterace. Běžné operace mají průměrně konstantní složitost, v nejhorším případě však lineární.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#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 neuspořádaný asociativní kontejner: každý prvek je zároveň svým klíčem a množina obsahuje nejvýše jeden prvek z každé třídy ekvivalence. Parametry Hash a Pred určují hashování a ekvivalenci; výchozími hodnotami jsou std::hash<Key> a std::equal_to<Key>. Ekvivalentní klíče musí mít stejný hash; stejný hash však neznamená, že jsou klíče ekvivalentní.
insert(value).second udává, zda byl prvek přidán. contains(value) ověřuje přítomnost, find(value) vrací iterátor nebo end() a erase(value) vrací počet odebraných prvků: zde 0 nebo 1. Vyhledávání, vložení jednoho prvku a odebrání podle klíče mají průměrnou složitost O(1) a v nejhorším případě O(n).
Pořadí iterace není určeno. Klíče nelze měnit prostřednictvím iterátorů; místo toho odeberte starý klíč a vložte nový. Rehashování zneplatňuje iterátory, nikoli však ukazatele ani reference na prvky. Vložení může rehashování vyvolat; reserve(n) připraví dostatek bucketů pro n prvků při aktuálním maximálním faktoru zaplnění a může také zneplatnit iterátory. Odebrání prvku zneplatní jeho iterátory, ukazatele a reference.
Příklad nevypisuje prvky procházením, takže očekávaný výstup nezávisí na jejich pořadí. Tento záznam se vztahuje k C++23; příznak kompilátoru v repozitáři nepotvrzuje produkční prostředí. Dodaný pracovní návrh se průběžně aktualizuje a může obsahovat funkce z pozdějších verzí než C++23.
Pří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ýsledek
inserted: false contains 3: true erased: 1 size: 1
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.