C++中std::unordered_set能否存储vector<pair<int,int>>？问题咨询

问题背景 #

在解决GeeksforGeeks的图论问题《Number of distinct islands》时，尝试用std::vector<std::pair<int, int>>存储岛屿的相对形状，再通过std::unordered_set存储这些形状以统计独特岛屿的数量。但编译时出现错误，将unordered_set替换为std::set后代码可正常运行，需要明确unordered_set对键类型的要求及问题原因。

编译错误信息 #

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::_.................

示例代码 #

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();
    }
};

原因分析 #

std::set能正常运行的原因 #

std::set是基于红黑树的有序容器，仅要求键类型支持小于比较运算符（operator<）。标准库为std::vector和std::pair<int,int>默认实现了operator<（按字典序比较），因此std::set<vector<pair<int,int>>>可以直接使用。

std::unordered_set报错的原因 #

std::unordered_set是哈希表实现的无序容器，对键类型有两个强制要求：

1. 必须提供对应的哈希函数：标准库没有为std::vector<std::pair<int, int>>特化std::hash模板，编译器无法找到该类型的哈希计算方式，这是编译报错的核心原因。
2. 必须提供相等比较运算符（operator==）：这一点std::vector默认支持（逐元素比较），因此不是问题。

解决方案 #

方案1：自定义哈希函数 #

为vector<pair<int,int>>实现自定义哈希函数，并在声明unordered_set时指定哈希类型：

// 自定义哈希结构体
struct VectorPairHash {
    size_t operator()(const vector<pair<int, int>>& v) const {
        size_t hash_val = 0;
        for (const auto& p : v) {
            // 组合pair的哈希值，这里用简单的哈希组合方式，也可以用更可靠的实现
            hash_val ^= std::hash<int>()(p.first) + 0x9e3779b9 + (hash_val << 6) + (hash_val >> 2);
            hash_val ^= std::hash<int>()(p.second) + 0x9e3779b9 + (hash_val << 6) + (hash_val >> 2);
        }
        return hash_val;
    }
};

// 修改unordered_set的声明
unordered_set<vector<pair<int,int>>, VectorPairHash> uset;

注意：简单的哈希组合可能存在碰撞风险，若需要更高的可靠性，可以参考专业的hash_combine实现逻辑。

方案2：继续使用std::set #

如果问题规模不大，std::set的O(log n)时间复杂度完全可以满足需求，且不需要额外编写哈希函数，代码更简洁易维护。

内容的提问来源于stack exchange，提问作者Saurabh Raj