Mida tuleb teha, et hoida oma struktuur…

Kui kasutada struktuuri std::unordered_map võtmena, tuleb esitada:

Hash-funktsioon: leiab struktuuri eksemplari hash-väärtuse.
Võrdlusoperaator (operator==): võrdleb kahte struktuuri eksemplari võrdluseks.

On mitu viisi neid elemente esitada:

Overload operator== struktuuris ja spetsialiseeri std::hash oma struktuurile. See on kõige levinum ja soovitatav lähenemine.

#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;
    }
};

// Spetsialiseerimine std::hash MyStruct jaoks
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);
        }
    };
}

// Näide kasutamisest main()
int main() {
    std::unordered_map<MyStruct, int> my_map;
    MyStruct key1 = {1, "Alice"};
    MyStruct key2 = {2, "Bob"};
    MyStruct key3 = {1, "Alice"}; // ekvivalent key1-ga

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

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

    return 0;
}

Esita hash-funktsioon ja võrdlusfunktsioon eraldi parameetritena unordered_map deklaratsioonis. See on vähem mugav, kui kasutate sageli struktuuri võtmena, kuna iga kord tuleb määrata võrdlus- ja hash-funktsioonid.

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

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

// Eraldi hash-funktsioon
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);
    }
};

// Eraldi võrdlusfunktsioon (või funktor)
struct MyStructEqual {
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const {
        return lhs.id == rhs.id && lhs.name == rhs.name;
    }
};

// Näide kasutamisest 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;
}

Tähtsad punktid:

Hesh-funktsiooni korrektus: Iga kahe võtme a ja b puhul, kui a == b, siis hash(a) peab olema võrdne hash(b)-ga. Tagurpidi ei ole nõutav (kolüsi võib esineda).
Hesh-funktsiooni kvaliteet: Hea hesh-funktsioon jaotab hesh-väärtused ühtlaselt erinevate võtmete vahel, minimeerides kolüsi ja parandades jõudlust (O(1) keskmiselt).
Konstantne: Võrdlus- ja hesh-operatsioonid peavad olema const, kuna need ei tohi muuta võtme objekti.

Mida tuleb teha, et hoida oma struktuur unordered_map'is?