KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::unordered_set — een verzameling unieke sleutels

std::unordered_set slaat unieke sleutels op met hashing. De container ondersteunt aanwezigheidstests, invoegen en verwijderen, zonder een iteratievolgorde te garanderen. Veelgebruikte bewerkingen hebben gemiddeld constante complexiteit, maar in het slechtste geval lineaire complexiteit.

Versie: C++23; repository compiler flag, production runtime not attested

Syntax

#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 uit <unordered_set> is een ongeordende associatieve container: elk element is ook zijn eigen sleutel en de verzameling bevat hoogstens één element uit elke equivalentieklasse. De parameters Hash en Pred bepalen hashing en equivalentie; standaard zijn dit std::hash<Key> en std::equal_to<Key>. Equivalente sleutels moeten dezelfde hash hebben; dezelfde hash betekent echter niet dat sleutels equivalent zijn.

insert(value).second geeft aan of een element is toegevoegd. contains(value) controleert of een element aanwezig is, find(value) levert een iterator of end(), en erase(value) geeft het aantal verwijderde elementen terug: hier 0 of 1. Zoeken, één element invoegen en verwijderen op sleutel hebben gemiddeld complexiteit O(1) en in het slechtste geval O(n).

De iteratievolgorde is niet gespecificeerd. Sleutels kunnen niet via iterators worden gewijzigd; verwijder in plaats daarvan de oude sleutel en voeg een nieuwe in. Een rehash maakt iterators ongeldig, maar niet de pointers of verwijzingen naar elementen. Invoegen kan een rehash veroorzaken; reserve(n) bereidt voldoende buckets voor n elementen voor bij de huidige maximale belastingsfactor en kan ook iterators ongeldig maken. Het verwijderen van een element maakt de bijbehorende iterators, pointers en verwijzingen ongeldig.

Het voorbeeld drukt geen elementen af door ze te doorlopen, dus de verwachte uitvoer hangt niet af van hun volgorde. Dit item is bedoeld voor C++23; een compileroptie in de repository bevestigt niet de productieomgeving. Het meegeleverde werkdocument wordt bijgewerkt en kan functies bevatten die van na C++23 zijn.

Voorbeelden

#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';
}

Resultaat

inserted: false
contains 3: true
erased: 1
size: 1

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen