C++ unordered_map fail when used with a vector as key
I found R. Martinho Fernandes's answer unsuitable for competitive programming since most of the times you have to deal with a provided IDE and cannot use an external library such as boost
. You can use the following method if you'd like to make the best of STL.
As already stated above, you just need to write a hash function. And it should specialize for the kind of data stored in your vector. The following hash function assumes int
type data:
struct VectorHasher {
int operator()(const vector<int> &V) const {
int hash = V.size();
for(auto &i : V) {
hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);
}
return hash;
}
};
Note that you can use any kind of operation to generate a hash. You just need to be creative so that collisions are minimized. For example, hash^=V[i]
, hash|=V[i]
, hash+=V[i]*V[i]
or even hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i)
are all valid until of course, your hash doesn't overflows.
Finally to use this hash function with your unordered_map
, initialize it as follows:
unordered_map<vector<int>,string,VectorHasher> hashMap;
§23.2.5, paragraph 3, says:
Each unordered associative container is parameterized by
Key
, by a function object typeHash
that meets the Hash requirements (17.6.3.4) and acts as a hash function for argument values of typeKey
, and by a binary predicatePred
that induces an equivalence relation on values of typeKey
.
Using vector<float>
as Key
and not providing explicit hash and equivalence predicate types means the default std::hash<vector<float>>
and std::equal_to<vector<float>>
will be used.
The std::equal_to
for the equivalence relation is fine, because there is an operator ==
for vectors, and that's what std::equal_to
uses.
There is however, no std::hash<vector<float>>
specialization, and that's probably what the linker error you didn't show us says. You need to provide your own hasher for this to work.
An easy way of writing such an hasher is to use boost::hash_range
:
template <typename Container> // we can make this generic for any container [1]
struct container_hash {
std::size_t operator()(Container const& c) const {
return boost::hash_range(c.begin(), c.end());
}
};
Then you can use:
std::unordered_map<floatVector, int, container_hash<floaVector>> map;
Of course, if you need different equality semantics in the map you need to define the hash and equivalence relation appropriately.
1. However, avoid this for hashing unordered containers, as different orders will produce different hashes, and the order in unordered container is not guaranteed.