Comment la comparaison des objets utilisés comme clés dans std::unordered_map est-elle effectuée?

Dans les objets std::unordered_map, les clés sont comparées à l'aide d'une fonction d'égalité (Equality), qui par défaut est std::equal_to<Key>.

Lors de l'insertion ou de la recherche d'une clé, le processus est le suivant :

1. Calcul du code de hachage de la clé à l'aide de la fonction de hachage (par défaut std::hash<Key>).
2. Recherche dans la case correspondante (bucket) en comparant les clés avec l'opérateur == ou un prédicat d'égalité défini.

Si les clés sont des types personnalisés, il est nécessaire de :

• Définir une spécialisation de std::hash pour ce type ou de fournir une fonction de hachage personnalisée.
• Définir l'opérateur == ou fournir une fonction de comparaison d'égalité personnalisée.

Exemple :

struct Key {
    int id;
    bool operator==(const Key& other) const {
        return id == other.id;
    }
};

namespace std {
    template<>
    struct hash<Key> {
        size_t operator()(const Key& k) const {
            return std::hash<int>()(k.id);
        }
    };
}

std::unordered_map<Key, std::string> map;