CKTIS / C++
std::unordered_set — множество от уникални ключове
std::unordered_set съхранява уникални ключове чрез хеширане. Позволява проверка за наличие, добавяне и премахване на елементи, без да гарантира ред на обхождане. Обичайните операции имат средно константна сложност, но в най-лошия случай — линейна.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#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 от <unordered_set> е неподреден асоциативен контейнер: всеки елемент е и негов ключ, а множеството съдържа най-много един елемент от всеки клас на еквивалентност. Параметрите Hash и Pred определят хеширането и еквивалентността; стойностите по подразбиране са std::hash<Key> и std::equal_to<Key>. Еквивалентните ключове трябва да имат еднакъв хеш; еднаквите хешове обаче не означават, че ключовете са еквивалентни.
insert(value).second показва дали е добавен елемент. contains(value) проверява за наличие, find(value) връща итератор или end(), а erase(value) връща броя на премахнатите елементи: тук 0 или 1. Търсенето, добавянето на един елемент и премахването по ключ имат средна сложност O(1), а в най-лошия случай — O(n).
Редът на обхождане не е зададен. Ключовете не могат да се променят чрез итератори; вместо това премахнете стария ключ и добавете нов. Повторното хеширане прави итераторите невалидни, но не и указателите или препратките към елементите. Добавянето може да предизвика повторно хеширане; reserve(n) подготвя достатъчно кофи за n елемента при текущия максимален коефициент на запълване и също може да направи итераторите невалидни. Премахването на елемент прави невалидни неговите итератори, указатели и препратки.
Примерът не извежда елементите чрез обхождане, затова очакваният изход не зависи от реда им. Този запис е предназначен за C++23; флагът на компилатора в хранилището не удостоверява производствената среда. Предоставеният работен проект се обновява с времето и може да съдържа функции от версии след C++23.
Примери
#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';
}
Резултат
inserted: false contains 3: true erased: 1 size: 1
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.