KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::unordered_map — hashmap met unieke sleutels

std::unordered_map slaat sleutel-waardeparen op zonder een vaste volgorde te garanderen. Lees hoe je zoekt zonder in te voegen, wat het verschil is tussen operator[] en at en hoe bucketbeheer de geldigheid van iterators beïnvloedt.

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

Syntax

#include <unordered_map>
std::unordered_map<Key, T> map;

std::unordered_map<Key, T> uit <unordered_map> slaat voor elke equivalente sleutel hoogstens één waarde op. De iteratievolgorde is niet gespecificeerd. Zoeken en invoegen kosten gemiddeld O(1) en in het slechtste geval O(n). Equivalente sleutels moeten dezelfde hash hebben; dezelfde hash betekent niet dat sleutels equivalent zijn.

find(key) voegt niets in: de functie retourneert een iterator of end(), de iterator na het laatste element, die je niet mag derefereren. operator[] retourneert een verwijzing naar de waarde en voegt een ontbrekende sleutel in; met de standaardallocator wordt de nieuwe waarde op waarde geïnitialiseerd, dus voor int is dat 0. at(key) voegt niets in en werpt std::out_of_range op als de sleutel ontbreekt. emplace(...) retourneert een paar met een iterator en een invoegindicator; een duplicaat overschrijft de waarde niet.

size() geeft het aantal elementen, bucket_count() het aantal buckets en load_factor() het gemiddelde aantal elementen per bucket. max_load_factor() leest de belastingsdrempel; max_load_factor(z) vereist een positieve z. Stel de drempel in vóór reserve(n), dat ruimte reserveert voor in totaal n elementen, niet voor n extra elementen. Dit is gelijk aan rehash(ceil(n / max_load_factor())). rehash(n) garandeert minstens n buckets en voldoende buckets voor de huidige elementen en de drempel; het exacte aantal hangt af van de implementatie.

Rehashing maakt iterators ongeldig, maar geen pointers of verwijzingen naar elementen. Invoegen, ook via operator[], kan dit veroorzaken. clear() verwijdert alle elementen, maakt size() gelijk aan 0 en maakt verwijzingen naar verwijderde elementen ongeldig; beschouw dit niet als een garantie dat al het geheugen van de container wordt vrijgegeven.

Reikwijdte van dit item: C++23. Een compileroptie in de repository bevestigt niet de productieomgeving. De brontekst is een evoluerend werkdocument, geen bevroren C++23-tekst; dit item steunt niet op de nieuwere uitbreidingen die daar worden getoond.

Referentie-identificatoren die in dit item worden behandeld: std::unordered_map::find, std::unordered_map::end, std::unordered_map::clear, std::unordered_map::operator[], std::unordered_map::max_load_factor, std::unordered_map::reserve, std::unordered_map::rehash, std::unordered_map::size, std::unordered_map::load_factor, std::unordered_map::bucket_count, std::unordered_map::at, std::unordered_map::emplace.

Voorbeelden

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    counts.max_load_factor(0.75f);
    counts.reserve(8);

    counts.emplace("apple", 2);
    ++counts["apple"];
    ++counts["pear"];
    const bool inserted = counts.emplace("apple", 99).second;

    if (auto it = counts.find("apple"); it != counts.end()) {
        std::cout << "apple=" << it->second << '\n';
    }
    std::cout << std::boolalpha << "duplicate inserted=" << inserted << '\n';
    std::cout << "pear=" << counts.at("pear") << '\n';
    std::cout << "size=" << counts.size() << '\n';

    counts.rehash(32);
    std::cout << "buckets>=32=" << (counts.bucket_count() >= 32) << '\n';
    std::cout << "load within limit="
              << (counts.load_factor() <= counts.max_load_factor()) << '\n';

    counts.clear();
    std::cout << "size after clear=" << counts.size() << '\n';
}

Resultaat

apple=3
duplicate inserted=false
pear=1
size=2
buckets>=32=true
load within limit=true
size after clear=0

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