C++ std::map : clés, valeurs, recherche et insertion

Rechercher par clé

Un vector est parfait quand vous indexez par position : l'élément 0, l'élément 1, et ainsi de suite. Mais souvent vous n'avez pas de position ; vous avez un nom et vous voulez ce qui y est attaché : un utilisateur et son score, un mot et son nombre d'occurrences, un code pays et sa capitale. Parcourir un vector pour trouver une correspondance est en O(n) et devient vite lent.

std::map résout cela. Il stocke des paires clé-valeur, les garde triées par clé et vous permet de rechercher une valeur par sa clé en temps O(log n). Incluez <map> pour l'utiliser :

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> se lit comme « un map de clés string vers des valeurs int ». Les clés sont uniques : si vous affectez deux fois la même clé, la seconde valeur l'emporte. En interne, un map est un arbre binaire de recherche équilibré, ce qui explique pourquoi tout reste trié et pourquoi les recherches sont logarithmiques plutôt que constantes.

Insérer des éléments

Il existe plusieurs façons d'ajouter des entrées, et la différence entre elles compte. La plus courante est operator[], qui crée la clé si elle n'existe pas et renvoie une référence à laquelle vous pouvez affecter :

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // créer + affecter
    inventory["apples"] += 3;     // lire-modifier-écrire, maintenant 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Si vous voulez une insertion qui refuse d'écraser une clé existante, utilisez insert ou emplace. Toutes deux renvoient une pair dont .second est un bool indiquant si l'insertion a réellement eu lieu :

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada existe déjà
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, inchangé
}

Utilisez [] quand « la dernière écriture l'emporte » est ce que vous voulez, et insert/emplace quand une clé existante doit être laissée intacte.

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

C'est le bug map le plus courant. operator[] n'est pas une lecture pure : si la clé est absente, il l'insère silencieusement avec une valeur construite par défaut (0 pour int, "" pour string, etc.) et renvoie une référence vers celle-ci. Donc le simple fait de vérifier une clé avec [] modifie le map :

map<string, int> m;
if (m["maybe"] == 0) {   // BUG : cela vient de créer "maybe" -> 0
    // ...
}
cout << m.size();        // 1, pas 0 - vous avez inséré une clé par accident

Cela vous mord aussi avec un const map, où operator[] ne compile même pas car il pourrait avoir besoin d'insérer. Pour lire sans insérer, utilisez find, count/contains ou at :

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find : renvoie un itérateur, == end() si absent
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) ou count (toute version)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at : lève std::out_of_range si absent - n'insère jamais
    cout << "a = " << m.at("a") << "\n";
}

Règle générale : si votre intention est de lire, ne recourez jamais à []. Utilisez at quand la clé doit exister, et find/contains quand elle pourrait ne pas exister.

Parcourir dans l'ordre trié

Comme un map repose sur un arbre, le parcourir visite les clés dans l'ordre croissant — toujours, et gratuitement. Chaque élément est une pair<const Key, Value>, alors utilisez une liaison structurée pour décomposer proprement la clé et la valeur :

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // les clés absentes commencent à 0, puis ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Remarquez que la clé dans la liaison est const : vous pouvez modifier une valeur dans la boucle avec auto&, mais vous ne pouvez jamais modifier une clé sur place (cela casserait l'ordre de tri). La sortie sort dans l'ordre alphabétique (blue, sea, sky) sans aucune étape de tri, ce qui est précisément la raison pour laquelle on choisit map plutôt qu'une table de hachage quand le parcours ordonné compte.

Cet idiome wordCount[w]++ est aussi l'usage canonique du comportement d'insertion à l'accès : ici vous voulez qu'une clé absente commence à 0, donc [] est le bon outil.

Supprimer des éléments et mesurer la taille

Supprimez par clé avec erase, qui renvoie le nombre d'éléments supprimés (0 ou 1 pour un map). Vous pouvez aussi supprimer via un itérateur issu de find. Vérifiez l'état du conteneur avec size() et empty() :

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (n'y était pas)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Un piège lors de la suppression dans une boucle : m.erase(it) invalide it, donc vous ne pouvez pas faire ++it ensuite. Le motif sûr depuis C++11 est it = m.erase(it), qui renvoie un itérateur vers l'élément suivant. Pour une suppression conditionnelle en une passe sur tout le map, std::erase_if(m, predicate) (C++20) est plus propre.

Suite : unordered_map

std::map vous donne des clés triées et des opérations en O(log n) prévisibles, mais vous payez cet ordre à chaque recherche. Quand l'ordre des clés vous est égal et que vous voulez simplement les recherches les plus rapides possibles, unordered_map échange l'arbre trié contre une table de hachage : accès en O(1) en moyenne. Nous verrons ensuite comment il fonctionne, quand son temps constant moyen bat le logarithme du map, et les pièges du hachage (types de clés personnalisés, collisions dans le pire des cas) qui l'accompagnent.