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