Structures clé-valeur avec std::map et std::unordered_map en C++

En C++, map et unordered_map sont les deux principaux conteneurs associatifs permettant de stocker des données sous forme de paires clé–valeur. Leur objectif est similaire — associer une clé à une valeur de manière efficace — mais leurs structures internes, leurs performances et leur comportement diffèrent fortement. Cet article présente ces deux conteneurs en détail avec des exemples pratiques.

1) Qu’est-ce que map ?

std::map est un conteneur associatif ordonné basé sur un arbre rouge-noir (red-black tree), c’est-à-dire un arbre binaire de recherche auto-équilibré.

• Les éléments sont stockés de manière triée selon la clé.
• Recherche, insertion, suppression : O(log n)
• Les clés sont uniques.
• L’itération se fait toujours dans l’ordre croissant des clés.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Remarque : Les éléments sont affichés par ordre alphabétique.

2) Qu’est-ce que unordered_map ?

std::unordered_map est un conteneur associatif basé sur une table de hachage. Il ne garantit aucun ordre mais offre des recherches extrêmement rapides en moyenne.

• Clés non triées (classées selon un hash).
• Recherche, insertion, suppression : O(1) en moyenne (pire cas O(n)).
• L’ordre d’itération est imprévisible et peut changer d’un exécutable à l’autre.
• Particulièrement performant sur de grands ensembles de données.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Note : L’ordre affiché est aléatoire et peut varier d’une exécution à l’autre.

3) Comparaison entre map et unordered_map

Résumé : Si vous avez besoin d’un ordre → utilisez map. Si vous avez besoin de rapidité → utilisez unordered_map.

4) Opérations de base

a) Insertion

map<int,string> m;
m.insert({1, "One"});
m[2] = "Two";   // insère ou met à jour

b) Recherche

auto it = m.find(1);
if (it != m.end())
    cout << "Trouvé : " << it->second;

c) Suppression

m.erase(2);          // suppression par clé
m.erase(m.begin());  // suppression via itérateur

d) Taille & vérification d’existence

cout << m.size();
cout << m.count(1);   // retourne 0 ou 1

5) Fonctions de hachage personnalisées pour unordered_map

Les types fondamentaux (int, string, double, etc.) ont déjà un hash intégré. Pour des types personnalisés, il faut définir manuellement une fonction de hachage ainsi qu’un prédicat d’égalité.

#include <unordered_map>
#include <string>

struct User {
    string name;
    int id;
};

struct UserHash {
    size_t operator()(User const& u) const noexcept {
        return hash<string>{}(u.name) ^ hash<int>{}(u.id);
    }
};

struct UserEq {
    bool operator()(User const& a, User const& b) const noexcept {
        return a.id == b.id && a.name == b.name;
    }
};

int main() {
    unordered_map<User, int, UserHash, UserEq> users;
}

6) Buckets et load factor dans unordered_map

Dans un unordered_map, les données sont stockées dans des buckets. Les clés produisant le même hash vont dans le même bucket (collision).

unordered_map<int,string> um;

cout << um.bucket_count() << endl;
cout << um.load_factor() << endl;

Lorsque le facteur de charge augmente, les performances diminuent. Utilisez rehash(n) pour augmenter le nombre de buckets et restaurer les performances.

7) Exemple pratique – Système de notes d’étudiants

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

int main() {
    unordered_map<string, double> grades;

    grades["Camille"] = 85.5;
    grades["Julien"] = 92.0;
    grades["Sophie"] = 78.0;

    if (grades.contains("Julien"))
        cout << "Note de Julien : " << grades["Julien"] << endl;

    grades.erase("Sophie");

    for (auto& g : grades)
        cout << g.first << " : " << g.second << endl;
}

8) Quel conteneur utiliser ?

• map → si un ordre est requis, ou pour de petites/moyennes quantités de données.
• unordered_map → si la vitesse maximale est la priorité.
• Pour les recherches par intervalle (lower_bound, upper_bound) → seul map convient.
• Pour de très grands volumes → unordered_map est généralement bien plus rapide.

Recommandation générale : Si vous n'avez pas besoin d’ordre → utilisez unordered_map. Si vous souhaitez un parcours trié → utilisez map.

9) TL;DR

Articles connexes