Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::unordered_map — table de hachage à clés uniques

std::unordered_map stocke des paires clé-valeur sans garantir leur ordre. Découvrez la recherche sans insertion, la différence entre operator[] et at, et l’influence de la gestion des compartiments sur la validité des itérateurs.

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

Syntaxe

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

std::unordered_map<Key, T> de <unordered_map> stocke au plus une valeur pour chaque clé équivalente. L’ordre d’itération n’est pas spécifié. La recherche et l’insertion ont un coût moyen de O(1) et un coût de O(n) dans le pire des cas. Les clés équivalentes doivent avoir le même hash ; des hash identiques n’impliquent pas que les clés soient équivalentes.

find(key) n’insère rien : la fonction renvoie un itérateur ou end(), l’itérateur situé après le dernier élément, qu’il ne faut pas déréférencer. operator[] renvoie une référence à la valeur et insère une clé absente ; avec l’allocateur par défaut, la nouvelle valeur est initialisée par valeur, soit 0 pour int. at(key) n’insère rien et lève std::out_of_range si la clé est absente. emplace(...) renvoie une paire composée d’un itérateur et d’un indicateur d’insertion ; un doublon ne remplace pas la valeur.

size() indique le nombre d’éléments, bucket_count() le nombre de compartiments et load_factor() le nombre moyen d’éléments par compartiment. max_load_factor() lit le seuil de charge ; max_load_factor(z) exige un z positif. Définissez le seuil avant reserve(n), qui prévoit de la place pour n éléments au total, et non n éléments supplémentaires. Cette fonction équivaut à rehash(ceil(n / max_load_factor())). rehash(n) garantit au moins n compartiments et un nombre suffisant pour les éléments présents et le seuil ; le nombre exact dépend de l’implémentation.

Le rehachage invalide les itérateurs, mais pas les pointeurs ni les références vers les éléments. Une insertion, y compris via operator[], peut le déclencher. clear() supprime tous les éléments, fait passer size() à 0 et invalide les références aux éléments supprimés ; ne considérez pas cette fonction comme une garantie de libération de toute la mémoire du conteneur.

Portée de l’entrée : C++23. Un indicateur de compilation du dépôt ne certifie pas l’environnement d’exécution de production. La source est un projet de norme en évolution, et non un texte C++23 figé ; cette entrée ne s’appuie pas sur les extensions plus récentes qui y sont présentées.

Identifiants de référence couverts par cette entrée : 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.

Exemples

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

Résultat

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

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources