0

Recently I was trying to solve a graph based problem Number of distinct islands on gfg. Where I want to store the shape of the island as vector of pairs, std::vector<pair<int, int>>, so that at the end I can store all the shapes using dfs in an unordered_set to get the total unique islands.

But I was getting error if I use unordered_set to store vector<pair<int, int>>. But if I use std::set then solution is accepted. I think there are some specific type of keys an unordered_set can store, please clarify me. Or if there is any other problem please tell me.

Error:

In file included from /usr/include/c++/5/bits/hashtable.h:35:0,
                from /usr/include/c++/5/unordered_map:47,
                from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:115,
                from prog.cpp:3:
/usr/include/c++/5/bits/hashtable_policy.h: In instantiation of struct std::__detail::__is_noexcept_hash<std::vector<std::pair<int, int> >, std::hash<std::vector<std::pair<int, int> > > >:
/usr/include/c++/5/type_traits:137:12:   required from struct std::_.................

c++ code:

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
class Solution {
  private:
    void dfs(int row, int col, vvi &grid, vvi &vis, vector<pair<int, int>> &shape, pair<int, int> &ref){
        int m = grid.size();
        int n = grid[0].size();
        vis[row][col] = 1;
        
        shape.push_back({row - ref.first, col - ref.second});
        
        int delrow[] = {0, +1, 0, -1};
        int delcol[] = {+1, 0, -1, 0};
        
        for(int i=0; i<4; i++){
            int nrow = row + delrow[i];
            int ncol = col + delcol[i];
            if(nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && grid[nrow][ncol] == 1 && vis[nrow][ncol] == 0){
                dfs(nrow, ncol, grid, vis, shape, ref);
            }
        }
    }
  public:
    int countDistinctIslands(vvi & grid) {
        int m = grid.size(), n = grid[0].size();
        vvi vis(m, vi(n, 0));
        
        unordered_set<vector<pair<int,int>>> uset;
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 1 && vis[i][j] == 0){
                    vector<pair<int, int>> shape;
                    pair<int, int> ref = {i, j};
                    dfs(i, j, grid, vis, shape, ref);
                    uset.insert(shape);
                }
            }
        }
        
        return uset.size();
    }
};

Note: If i use set instead of unordered_set, error is gone and solution is accepted.

Chris
  • 26,361
  • 5
  • 21
  • 42
Saurabh Raj
  • 65
  • 6
  • You need to provide a specialisation of [std::hash](https://en.cppreference.com/w/cpp/utility/hash) – Alan Birtles Sep 06 '22 at 07:00
  • @AlanBirtles AFAIK, you are not allowed to specialize std::hash for library types. – Daniel Langr Sep 06 '22 at 07:02
  • Short answer: You need to provide a hasher for a vector of pairs. The standard library doesn't have one. With set, you are fine since you just need comparison operators. And these are provided by the library. – Daniel Langr Sep 06 '22 at 07:09

0 Answers0