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

std::map — un conteneur associatif qui stocke des paires "clé-valeur", triées par la clé. Basé sur un arbre rouge-noir. Le temps d'accès, d'insertion et de suppression des éléments est logarithmique (O(log n)).

std::unordered_map — un conteneur associatif qui stocke des paires "clé-valeur" dans une table de hachage. Les éléments ne sont pas triés. En moyenne, le temps d'accès, d'insertion et de suppression des éléments est constant (O(1)), mais dans le pire des cas, il peut être linéaire (O(n)) en raison de collisions. Nécessite une fonction de hachage pour le type de clé et un opérateur de comparaison d'égalité (operator==).

Caractéristique	std::map	std::unordered_map
Base	Arbre rouge-noir	Table de hachage
Tri des éléments	Par clé	Non
Complexité moyenne des opérations (accès, insertion, suppression)	O(log n)	O(1)
Complexité dans le pire des cas (accès, insertion, suppression)	O(log n)	O(n) (en cas de collisions)
Exigences pour la clé	< opérateur	Fonction de hachage, == opérateur
Consommation de mémoire	Plus	Moins (en moyenne, mais peut varier)

Exemple d'utilisation :

#include <map>
#include <unordered_map>
#include <string>

int main() {
    // Utilisation de std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Les éléments sont stockés dans l'ordre trié par clé (apple, banana, orange)

    // Utilisation de std::unordered_map
    std::unordered_map<std::string, int> my_unordered_map;
    my_unordered_map["apple"] = 1;
    my_unordered_map["banana"] = 2;
    my_unordered_map["orange"] = 3;
    // Les éléments sont stockés sans ordre défini
    
    return 0;
}