Jak jest wykonywane porównanie obiektów używanych jako klucze w std::unordered_map?

W obiektach std::unordered_map klucze są porównywane za pomocą funkcji równości (Equality), która domyślnie jest std::equal_to<Key>.

Podczas wstawiania lub wyszukiwania klucza, proces wygląda następująco:

1. Obliczenie kodu hash klucza za pomocą funkcji hash (domyślnie std::hash<Key>).
2. Wyszukiwanie w odpowiednim koszu (bucket) za pomocą porównania kluczy przez operator == lub zdefiniowany predykat równości.

Jeśli klucze są typami niestandardowymi, konieczne jest:

• Zdefiniowanie specjalizacji std::hash dla tego typu lub dostarczenie własnej funkcji hash.
• Zdefiniowanie operatora == lub dostarczenie własnej funkcji porównania równości.

Przykład:

struct Key {
    int id;
    bool operator==(const Key& other) const {
        return id == other.id;
    }
};

namespace std {
    template<>
    struct hash<Key> {
        size_t operator()(const Key& k) const {
            return std::hash<int>()(k.id);
        }
    };
}

std::unordered_map<Key, std::string> map;