STL map/unordered_map with a Vector for the Key

Jimmy (xiaoke) Shen
3 min readJul 3, 2020

map uses vector as the key

Map in c++ is implemented by a Red Black tree, which is an essential balanced binary search tree. It is not a hash table, so it doesn't need that the key is hashable. However, it requires that the key support <, >, or == operations.

So for the map in c++, we can use a vector as key. [1]

unordered_map uses vector as the key

What about unordered_map?

It fails. However, we can find some way to address this issue.[2]

“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 in 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…