O'z tuzilmasini unordered_mapda saqlash uchun nima…

std::unordered_map ich uchun strukturani kalit sifatida saqlash uchun quyidagilarni taqdim etish kerak:

Hash funksiyasi: Strukturadagi nusxa uchun hash qiymatini topadi.
Tenglikni solishtirish operatori (operator==): Ikki nusxani tengligini solishtiradi.

Ushbu elementlarni taqdim etishning bir necha usullari mavjud:

operator==ni strukturada qayta yozish va std::hashni sizning strukturangiz uchun maxsuslashtirish. Bu eng keng tarqalgan va tavsiya etilgan yondashuv.

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

// MyStruct uchun std::hashni maxsuslashtirish
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);
        }
    };
}

// mainda foydalanish misoli
int main() {
    std::unordered_map<MyStruct, int> my_map;
    MyStruct key1 = {1, "Alice"};
    MyStruct key2 = {2, "Bob"};
    MyStruct key3 = {1, "Alice"}; // ekvivalent key1

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

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

    return 0;
}

Hash funksiyasi va solishtirish funksiyasini unordered_map deklaratsiyasida alohida parametrlar sifatida taqdim etish. Bu, strukturani kalit sifatida ko'p ishlatsangiz kamroq qulay, chunki har safar konteynerni e'lon qilishda turini ko'rsatishingiz kerak.

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

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

// Alohida hash funksiyasi
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);
    }
};

// Alohida solishtirish funksiyasi
struct MyStructEqual {
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const {
        return lhs.id == rhs.id && lhs.name == rhs.name;
    }
};

// mainda foydalanish misoli
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;
}

Muhim nuqtalar:

Hash funksiyasining to'g'riligi: Har qanday ikkita kalit a va b uchun, agar a == b bo'lsa, hash(a) bilan hash(b) teng bo'lishi kerak. Aks holda, (collisionlar mumkin) bo'lishi mumkin.
Hash funksiyasining sifatli bo'lishi: Yaxshi hash funksiyasi turli kalitlar uchun hash qiymatlarini teng taqsimlaydi, collisionlarni minimallashtiradi va ishlashni yaxshilaydi (O(1) o'rtacha).
Konstantlik: Solishtirish va hash operatorlari const bo'lishi kerak, chunki ular kalit ob'ektini o'zgartirmasligi kerak.

O'z tuzilmasini unordered_mapda saqlash uchun nima qilish kerak?