Requirements for Custom Key Types in std::unordered_map
What are the requirements for using a custom type as the key in std::unordered_map
?
To use a custom type as the key in std::unordered_map
, the type must meet the following requirements:
- Hash Function: The custom type must have a hash function specialization for
std::hash
. This function calculates the hash value for objects of the custom type. If not provided, you need to supply a custom hash function as a template argument tostd::unordered_map
. - Equality Comparison: The custom type must have an equality comparison operator (
operator==
) defined. This operator is used to determine if two keys are equal, especially in case of hash collisions. If not provided, you need to supply a custom equality comparison function as a template argument tostd::unordered_map
.
Here's an example of a custom type meeting these requirements:
#include <iostream>
#include <string>
#include <unordered_map>
struct Player {
std::string name;
int score;
bool operator==(const Player& other) const {
return name == other.name
&& score == other.score;
}
};
namespace std {
template <>
struct hash<Player> {
size_t operator()(const Player& player) const {
size_t nameHash =
std::hash<std::string>{}(player.name);
size_t scoreHash =
std::hash<int>{}(player.score);
return nameHash ^ (scoreHash << 1);
}
};
}
int main() {
std::unordered_map<Player, int> playerMap;
playerMap[Player{"Alice", 100}] = 1;
playerMap[Player{"Bob", 200}] = 2;
for (const auto& [player, id] : playerMap) {
std::cout << "Player: " << player.name
<< ", Score: " << player.score
<< ", ID: " << id << '\n';
}
}
Player: Alice, Score: 100, ID: 1
Player: Bob, Score: 200, ID: 2
In this example, the Player
type has an operator==
for equality comparison and a specialization of std::hash
to calculate the hash value based on the name
and score
members.
If the custom type doesn't provide these functions, you can supply them as additional template arguments to std::unordered_map
:
#include <iostream>
#include <string>
#include <unordered_map>
struct Player {
std::string name;
int score;
};
struct PlayerHash {
size_t operator()(const Player& player) const {
// Custom hash function implementation
}
};
struct PlayerEqual {
bool operator()(
const Player& lhs, const Player& rhs) const {
// Custom equality comparison implementation
}
};
std::unordered_map<
Player, int, PlayerHash, PlayerEqual> playerMap;
By meeting these requirements, you can use custom types as keys in std::unordered_map
, enabling efficient lookup and insertion operations based on the custom type's hash value and equality comparison.
Hash Maps using std::unordered_map
Creating hash maps using the standard library's std::unordered_map
container