# STL map/`unordered_map`

with a Vector for the Key

--

# 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 `hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i)`

are all valid until of course, your hash doesn't overflow.

Finally to use this hash function with your `unordered_map`

, initialize it as follows:

`unordered_map<vector<int>,string,VectorHasher> hashMap;`

# A problem to practice 1

957. Prison Cells After N Days

/**

* jimmy shen

* time complexity O(2^6 log(2^6) *6)

* space complexity O(2^6)

*/class Solution {

public:

vector<int> prisonAfterNDays(vector<int>& cells, int N) {

map<vector<int>, int> m;

vector<vector<int>> history;

vector<int> new_cells(cells.size(), 0);

for (int i=0;i<N;++i){

for (int j=1;j<cells.size()-1;++j){

new_cells[j] = 1-(cells[j-1]^cells[j+1]);

}

cells = new_cells;

if (m.find(cells)!=m.end()){

int prev = m[cells];

int ret = (N-1-prev)%(i-prev) +prev;

return history[ret];

}

m[cells] = i;

history.push_back(cells);

}

return cells;

}

};

Not surprisingly, if we change the map into unordered_map, we will get an error.

We can make it work by changing the vector into an integer since that we only have 8 elements in the vector and each element is 0 or 1.

/**

* jimmy shen

* time complexity O(2^6 *6)

* space complexity O(2^6)

*/class Solution {

public:

vector<int> prisonAfterNDays(vector<int>& cells, int N) {

unordered_map<int, int> m;

vector<vector<int>> history;

vector<int> new_cells(cells.size(), 0);

for (int i=0;i<N;++i){

for (int j=1;j<cells.size()-1;++j){

new_cells[j] = 1-(cells[j-1]^cells[j+1]);

}

cells = new_cells;

int cells_int = 0;

for (int k=0;k<cells.size();++k){

cells_int |= (cells[k]<<(cells.size()-1-k));

}

if (m.find(cells_int)!=m.end()){

int prev = m[cells_int];

int ret = (N-1-prev)%(i-prev) +prev;

return history[ret];

}

m[cells_int] = i;

history.push_back(cells);

}

return cells;

}

};

# A problem to practice 2: LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts

## LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts

Very interesting, Huahua did a similar approach when trying to solve a pretty hard biweekly contest problem from Leetcode. The following code is from his blog here.

## map approach

`// Author: Huahua, 888 ms, 61.9 MB`

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

map<vector<int>, int> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

for (int i = 1; i < b; ++i) {

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

## hashmap approach

`// Author: Huahua 380 ms, 59.2 MB`

struct VectorHasher {

size_t operator()(const vector<int>& V) const {

size_t hash = V.size();

for (auto i : V)

hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);

return hash;

}

};

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

unordered_map<vector<int>, int, VectorHasher> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

for (int i = 1; i < b; ++i) {

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + b - i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

# Reference

[1]STL Map with a Vector for the Key

[2]https://stackoverflow.com/questions/10405030/c-unordered-map-fail-when-used-with-a-vector-as-key