Ի՞նչ պետք է անել, որպեսզի պահեք ձեր կառուցվածքը 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`-ի համար
  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) միջինում):
• Կոնստանտություն: Օպերատորները operator== և hash պետք է լինեն const, քանի որ նրանք չպետք է փոխեն բանալի օբյեկտը: