CKTIS / C++
std::unordered_set — zbiór unikalnych kluczy
std::unordered_set przechowuje unikalne klucze, wykorzystując haszowanie. Pozwala sprawdzać obecność, dodawać i usuwać elementy bez gwarancji kolejności iteracji. Typowe operacje mają średnio stałą złożoność, ale w najgorszym przypadku liniową.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#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 nagłówka <unordered_set> jest nieuporządkowanym kontenerem asocjacyjnym: element jest jednocześnie kluczem, a zbiór zawiera najwyżej jeden element z każdej klasy równoważności. Parametry Hash i Pred określają haszowanie i równoważność; domyślnie są to std::hash<Key> i std::equal_to<Key>. Równoważne klucze muszą mieć ten sam hash; jednakowy hash nie oznacza równoważności.
insert(value).second informuje, czy dodano element. contains(value) sprawdza obecność, find(value) zwraca iterator albo end(), a erase(value) zwraca liczbę usuniętych elementów: tutaj 0 lub 1. Wyszukiwanie, wstawienie pojedynczego elementu i usuwanie według klucza mają średnio złożoność O(1), a w najgorszym przypadku O(n).
Kolejność iteracji nie jest określona. Nie można zmieniać kluczy przez iteratory; zamiast tego usuń stary klucz i wstaw nowy. Rehash unieważnia iteratory, ale nie wskaźniki ani referencje do elementów. Wstawianie może wywołać rehash; reserve(n) przygotowuje liczbę kubełków dla n elementów przy bieżącym maksymalnym współczynniku zapełnienia i również może unieważnić iteratory. Usunięcie elementu unieważnia jego iteratory, wskaźniki i referencje.
Przykład nie wypisuje elementów przez iterację, więc oczekiwany wynik nie zależy od ich kolejności. Zakres wpisu to C++23; flaga kompilatora w repozytorium nie potwierdza środowiska produkcyjnego. Podany roboczy projekt standardu jest aktualizowany i może zawierać funkcje późniejsze niż C++23.
Przykłady
#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';
}
Wynik
inserted: false contains 3: true erased: 1 size: 1
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.