Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::unordered_map — mappa hash con chiavi univoche

std::unordered_map memorizza coppie chiave-valore senza garantirne l’ordine. Scopri come cercare senza inserire, la differenza tra operator[] e at e come la gestione dei bucket influisce sulla validità degli iteratori.

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

Sintassi

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

std::unordered_map<Key, T> di <unordered_map> memorizza al massimo un valore per ogni chiave equivalente. L’ordine di iterazione non è specificato. Ricerca e inserimento hanno costo medio O(1) e costo O(n) nel caso peggiore. Le chiavi equivalenti devono avere lo stesso hash; hash uguali non implicano che le chiavi siano equivalenti.

find(key) non inserisce: restituisce un iteratore oppure end(), l’iteratore che segue l’ultimo elemento e che non deve essere dereferenziato. operator[] restituisce un riferimento al valore e inserisce una chiave mancante; con l’allocatore predefinito, il nuovo valore viene inizializzato per valore, quindi per int è 0. at(key) non inserisce e lancia std::out_of_range se la chiave manca. emplace(...) restituisce una coppia formata da un iteratore e da un indicatore di inserimento; un duplicato non sovrascrive il valore.

size() indica il numero di elementi, bucket_count() il numero di bucket e load_factor() il numero medio di elementi per bucket. max_load_factor() legge la soglia di carico; max_load_factor(z) richiede un z positivo. Imposta la soglia prima di reserve(n), che prepara spazio per n elementi complessivi, non per n elementi aggiuntivi. Equivale a rehash(ceil(n / max_load_factor())). rehash(n) assicura almeno n bucket e un numero sufficiente per gli elementi attuali e la soglia; il numero esatto dipende dall’implementazione.

Il rehashing invalida gli iteratori, ma non i puntatori né i riferimenti agli elementi. Può essere provocato da un inserimento, anche tramite operator[]. clear() rimuove tutti gli elementi, porta size() a 0 e invalida i riferimenti agli elementi rimossi; non considerarlo una garanzia che venga liberata tutta la memoria del contenitore.

Ambito della voce: C++23. Un’opzione del compilatore nel repository non attesta l’ambiente di esecuzione di produzione. Il sorgente è una bozza in evoluzione, non un testo C++23 congelato; questa voce non si basa sulle estensioni più recenti mostrate lì.

Identificatori di riferimento trattati in questa voce: 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.

Esempi

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

Risultato

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

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti