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

La principale différence réside dans la façon dont les éléments sont stockés et récupérés :

• std::map : Stocke les éléments dans un ordre trié par clé. Il est généralement implémenté à l'aide d'un arbre rouge-noir. La recherche, l'insertion et la suppression ont une complexité logarithmique O(log N), où N est le nombre d'éléments.
• std::unordered_map : Stocke les éléments dans une table de hachage. L'ordre des éléments est arbitraire. En moyenne, la recherche, l'insertion et la suppression ont une complexité constante O(1). En cas de collisions, la complexité peut atteindre O(N).

Caractéristique	std::map	std::unordered_map
Ordre	Par clé (croissant)	Non
Structure de base	Arbre rouge-noir	Table de hachage
Complexité moyenne	O(log N)	O(1)
Cas pire	O(log N)	O(N)
Exigences de clé	Opérateur <	Fonction de hachage et ==

Exemple d'utilisation :

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

int main() {
    // std::map : éléments triés par clé
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Affichage : apple 1, banana 3, cherry 2 (l'ordre est important)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map : ordre des éléments non garanti
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // La sortie peut varier (par exemple, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}