რა უნდა გავაკეთოთ, რათა ჩვენი სტრუქტურა შევინახოთ unordered_map-ში?

სასურველია, რომ std::unordered_map-ში სტრუქტურის გამოყენებისას, როგორც გასაღებს, მიაწოდოთ:

1. ჰეშირების ფუნქცია (hash function): იპოვის სტრუქტურის მაგალითისთვის ჰეშ-ღირებულებას.
2. შესადარებელი ოპერაცია (operator==): შედარებს ორი სტრუქტურის მაგალითს თანასწორობისთვის.

არსებობს რამდენიმე გზა ამ ელემენტების მიწოდებისთვის:

• გადაწერეთ operator== სტრუქტურაში და სპეციალიზირეთ std::hash თქვენი სტრუქტურისთვის. ეს ყველაზე გავრცელებული და რეკომენდებული მეთოდია.

  #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;
      }
  };
  
  // `std::hash`-ის სპეციალიზაცია 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);
          }
      };
  }
  
  // გამოყენების მაგალითი main-ში
  int main() {
      std::unordered_map<MyStruct, int> my_map;
      MyStruct key1 = {1, "Alice"};
      MyStruct key2 = {2, "Bob"};
      MyStruct key3 = {1, "Alice"}; // ტოლია key1-ის
  
      my_map[key1] = 10;
      my_map[key2] = 20;
  
      if (my_map.count(key3)) {
          // my_map[key3] დააბრუნებს 10-ს
      }
  
      return 0;
  }
  

• მიწოდეთ ჰეშირების და შედარების ფუნქციები როგორც ცალკეული პარამეტრები unordered_map-ის გამოძახებისას. ეს ნაკლებად მოსახერხებელია, თუ ხშირად იყენებთ სტრუქტურას როგორც გასაღებს, რადგან ყოველ ჯერზე უნდა მიუთითოთ კომპარატორის და ჰეშერის ტიპები.

  #include <unordered_map>
  #include <string>
  #include <functional>
  
  struct MyStruct {
      int id;
      std::string name;
  };
  
  // ცალკე ჰეშირების ფუნქცია
  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);
      }
  };
  
  // ცალკე შედარების ფუნქცია (ან ფუნკტორი)
  struct MyStructEqual {
      bool operator()(const MyStruct& lhs, const MyStruct& rhs) const {
          return lhs.id == rhs.id && lhs.name == rhs.name;
      }
  };
  
  // გამოყენების მაგალითი 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;
  }
  

მნიშვნელოვანი წერტილები:

• ჰეშ-ფუნქციის სისწორე: ნებისმიერი ორი გასაღებისთვის a და b, თუ a == b, მაშინ hash(a) უნდა იყოს თანაბარი hash(b)-სთან. საპირისპირო არ არის აუცილებელი (მრავალფეროვანი ჰეშ-კოლიზიები შესაძლებელია).
• ჰეშ-ფუნქციის ხარისხი: კარგი ჰეშ-ფუნქცია თანაბრად განაწილებს ჰეშ-ღირებულებებს სხვადასხვა გასაღებისთვის, მინიმუმამდე დაიყვანს კოლიზიებს და გაზრდის შესრულებას (O(1) საშუალოდ).
• კონსტანტურობა: ოპერაციები შედარებისა და ჰეშირების უნდა იყოს const, რადგან ისინი არ უნდა ცვლიდეს გასაღების ობიექტს.