Que faut-il faire pour stocker sa structure dans un…

Pour stocker une structure comme clé dans std::unordered_map, il est nécessaire de fournir :

Une fonction de hachage (hash function) : Trouve la valeur de hachage pour une instance de la structure.
L'opérateur de comparaison d'égalité (operator==) : Compare deux instances de la structure pour vérifier si elles sont égales.

Il existe plusieurs façons de fournir ces éléments :

Surcharger operator== dans la structure et spécialiser std::hash pour votre structure. C'est l'approche la plus courante et recommandée.

#include <unordered_map>
#include <string>
#include <functional>

struct MyStruct {
    int id;
    std::string name;

    bool operator==(const MyStruct& other) const {
        return id == other.id && name == other.name;
    }
};

// Spécialisation de std::hash pour MyStruct
namespace std {
    template <>
    struct hash<MyStruct> {
        size_t operator()(const MyStruct& obj) const {
            size_t h1 = hash<int>()(obj.id);
            size_t h2 = hash<std::string>()(obj.name);
            return h1 ^ (h2 << 1);
        }
    };
}

// Exemple d'utilisation dans main
int main() {
    std::unordered_map<MyStruct, int> my_map;
    MyStruct key1 = {1, "Alice"};
    MyStruct key2 = {2, "Bob"};
    MyStruct key3 = {1, "Alice"}; // équivalent à key1

    my_map[key1] = 10;
    my_map[key2] = 20;

    if (my_map.count(key3)) {
        // my_map[key3] renverra 10
    }

    return 0;
}

Fournir des fonctions de hachage et de comparaison comme paramètres séparés lors de la déclaration de unordered_map. Moins pratique si vous utilisez fréquemment la structure comme clé, car vous devez spécifier les types de comparateur et de hachage à chaque déclaration.

#include <unordered_map>
#include <string>
#include <functional>

struct MyStruct {
    int id;
    std::string name;
};

// Fonction de hachage séparée
struct MyStructHash {
    size_t operator()(const MyStruct& obj) const {
        size_t h1 = std::hash<int>()(obj.id);
        size_t h2 = std::hash<std::string>()(obj.name);
        return h1 ^ (h2 << 1);
    }
};

// Fonction de comparaison séparée
struct MyStructEqual {
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const {
        return lhs.id == rhs.id && lhs.name == rhs.name;
    }
};

// Exemple d'utilisation dans main
int main() {
    std::unordered_map<MyStruct, int, MyStructHash, MyStructEqual> my_map;
    MyStruct key1 = {1, "Alice"};
    MyStruct key2 = {2, "Bob"};

    my_map[key1] = 10;
    my_map[key2] = 20;

    return 0;
}

Points importants :

La correction de la fonction de hachage : Pour deux clés a et b, si a == b, alors hash(a) doit être égal à hash(b). La réciproque n'est pas nécessaire (des collisions sont possibles).
La qualité de la fonction de hachage : Une bonne fonction de hachage répartit uniformément les valeurs de hachage pour différentes clés, minimisant les collisions et améliorant la performance (O(1) en moyenne).
Constance : Les opérateurs de comparaison et la fonction de hachage doivent être const, car ils ne doivent pas modifier l'objet clé.

Que faut-il faire pour stocker sa structure dans un unordered_map?