Docs C++ exécutables : unordered_map

Q: Quelle est la différence entre map et unordered_map en C++ ?

std::map est un arbre binaire équilibré : les clés restent triées et les opérations sont en O(log n). std::unorderedmap est une table de hachage : les clés ne suivent aucun ordre particulier, mais l'insertion et la recherche sont en moyenne en O(1). Utilise unorderedmap quand tu as seulement besoin d'une recherche rapide par clé et que l'ordre t'est égal ; utilise map quand tu as besoin d'une itération triée ou de requêtes par plage.

Q: unordered_map[] insère-t-il une clé si elle n'existe pas ?

Oui. m[key] construit par défaut et insère la clé si elle est absente, puis renvoie une référence vers elle. Cela signifie que même un if (m[key] == ...) qui ressemble à une lecture fait grossir le map en silence. Pour tester l'appartenance sans insérer, utilise plutôt m.count(key) ou m.find(key).

Q: unordered_map est-il toujours plus rapide que map en C++ ?

Non. Il est en O(1) en moyenne, mais le hachage a un coût et un mauvais hachage (ou des clés adverses) peut dégrader les recherches en O(n). Pour de petits maps, les facteurs constants et un moins bon comportement de cache peuvent rendre un map trié tout aussi rapide, voire plus. Mesure si c'est important, mais opte par défaut pour unordered_map quand tu as seulement besoin d'une recherche par clé.

Quand l'ordre n'a pas d'importance

Tu viens de voir std::map, qui garde ses clés triées grâce à un arbre équilibré et t'offre des opérations en O(log n). Mais le tri a un coût, et bien souvent tu te moques de l'ordre dans lequel les clés ressortent - tu veux seulement demander « cette clé est-elle là, et quelle est sa valeur ? » aussi vite que possible.

C'est à cela que sert std::unordered_map. C'est une table de hachage : elle fait passer chaque clé par une fonction de hachage pour décider où la ranger, ce qui rend l'insertion, la recherche et la suppression en O(1) en moyenne au lieu de O(log n). Le compromis, c'est que l'ordre d'itération n'est pas spécifié - les clés ressortent dans l'ordre où les buckets les contiennent.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

L'interface est presque identique à celle de map, et c'est volontaire - tu peux souvent remplacer l'un par l'autre en changeant simplement le type. Inclus <unordered_map> (et non <map>), et les clés ressortent non triées.

Insérer et mettre à jour

Il existe plusieurs façons d'ajouter des entrées, et elles ne se comportent pas toutes de la même manière. Les deux que tu utiliseras le plus sont operator[] et insert :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // créer ou écraser
    votes["alice"] = 5;              // écrase -> 5
    votes.insert({"bob", 2});        // insère uniquement si "bob" est absent
    votes.insert({"bob", 99});       // ignoré, "bob" existe déjà

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, pas 99
}

La différence clé : operator[] écrase une valeur existante, tandis qu'insert laisse intacte une clé déjà présente. Si tu es en C++17, insert_or_assign(key, value) te donne la sémantique « affecte ceci quoi qu'il arrive », et try_emplace(key, args...) construit la valeur sur place uniquement lorsque la clé est nouvelle - pratique pour des valeurs coûteuses à construire.

Le piège de operator[] : il insère à la lecture

C'est le bug le plus courant avec unordered_map, il a donc droit à sa propre section. m[key] n'est pas une lecture pure. Si la clé est absente, il la construit par défaut et l'insère (un int devient 0, un string devient ""), puis renvoie une référence. Ainsi, du code qui ressemble à une recherche fait grossir le map en douce :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // On voulait seulement VÉRIFIER "y", mais [] l'a inséré :
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, pas 1 !
}

seen["y"] a créé une entrée "y" -> 0 rien que par sa mention. Pour tester l'appartenance sans modifier le map, utilise count (renvoie 0 ou 1) ou find :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20 : contains() se lit mieux que count()
    if (seen.contains("x")) cout << "x is here\n";
}

Règle générale : n'utilise [] que lorsque tu comptes créer ou mettre à jour. Pour les lectures pures, utilise count, contains (C++20) ou find.

find et at : des recherches sûres

find renvoie un itérateur vers l'entrée, ou end() si la clé est absente. Il n'insère jamais, et te permet d'atteindre à la fois la clé et la valeur via it->first et it->second en une seule recherche :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Quand tu sais que la clé devrait exister et veux un échec franc si ce n'est pas le cas, utilise at. Contrairement à [], at n'insère pas - il lève std::out_of_range pour une clé manquante :

int p = prices.at("pen");   // ok
int q = prices.at("hat");   // lève std::out_of_range - clé absente

Tu disposes donc de trois styles de recherche : [] (insère), at (lève) et find/count (signalent la présence sans toucher au map). Choisis celui dont le mode d'échec correspond à ton intention.

Itérer et supprimer

Une boucle for basée sur une plage avec structured bindings est la façon propre de parcourir chaque entrée. Souviens-toi que l'ordre est arbitraire - ne t'y fie jamais :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // l'ordre n'est pas spécifié
    }
}

Pour retirer une entrée, erase prend directement une clé et renvoie le nombre d'éléments supprimés (0 ou 1). Un piège important : dans un unordered_map, supprimer pendant l'itération n'invalide que l'itérateur de l'élément supprimé, alors utilise la valeur de retour de erase(it) pour avancer en toute sécurité :

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Retire toute équipe dont le score est inférieur à 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase renvoie l'itérateur valide suivant
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

Écrire wins.erase(it++) ou faire ++it après un simple erase(it) est le piège classique de l'itérateur invalidé - l'itérateur supprimé est mort, alors prends toujours l'itérateur renvoyé par erase.

map ou unordered_map ?

Les deux stockent des paires clé-valeur avec une API similaire, donc le choix se résume à ce dont tu as besoin :

// std::map            -> clés triées, O(log n), requêtes par plage (lower_bound)
// std::unordered_map  -> sans ordre,  O(1) moy., recherche simple la plus rapide

Opte pour unordered_map quand tu as seulement besoin d'une recherche rapide par clé et que l'ordre est sans importance (compter des fréquences de mots, mise en cache, déduplication). Choisis map quand tu as besoin des clés dans l'ordre trié, que tu veux itérer dans l'ordre ou faire des requêtes par plage. Deux réserves pour unordered_map : son O(1) est une moyenne - un mauvais hachage peut le dégrader - et un type de clé personnalisé nécessite une spécialisation de hachage ou un foncteur de hachage, alors que map ne réclame qu'un operator<.

Ensuite : Set

Tu as maintenant vu les deux variantes de conteneur clé-valeur. Pourtant, parfois, tu n'as pas du tout besoin d'une valeur - seule t'importe la présence ou non d'un élément, comme une collection de tags uniques ou d'identifiants visités. Ensuite, nous verrons std::set (et son cousin basé sur le hachage unordered_set), qui ne stockent que des clés et les gardent automatiquement uniques.

Questions fréquentes

Quelle est la différence entre map et unordered_map en C++ ?

std::map est un arbre binaire équilibré : les clés restent triées et les opérations sont en O(log n). std::unordered_map est une table de hachage : les clés ne suivent aucun ordre particulier, mais l'insertion et la recherche sont en moyenne en O(1). Utilise unordered_map quand tu as seulement besoin d'une recherche rapide par clé et que l'ordre t'est égal ; utilise map quand tu as besoin d'une itération triée ou de requêtes par plage.

unordered_map[] insère-t-il une clé si elle n'existe pas ?

Oui. m[key] construit par défaut et insère la clé si elle est absente, puis renvoie une référence vers elle. Cela signifie que même un if (m[key] == ...) qui ressemble à une lecture fait grossir le map en silence. Pour tester l'appartenance sans insérer, utilise plutôt m.count(key) ou m.find(key).

unordered_map est-il toujours plus rapide que map en C++ ?

Non. Il est en O(1) en moyenne, mais le hachage a un coût et un mauvais hachage (ou des clés adverses) peut dégrader les recherches en O(n). Pour de petits maps, les facteurs constants et un moins bon comportement de cache peuvent rendre un map trié tout aussi rapide, voire plus. Mesure si c'est important, mais opte par défaut pour unordered_map quand tu as seulement besoin d'une recherche par clé.

Concepts liés