用unordered_map实现网格A*算法遇哈希错误，求解决与替代方案

嘿，我来帮你搞定这个问题！

首先说报错的核心原因：你用unordered_map的时候把自定义的locatie类型作为键了，但C++标准库并没有为这种自定义结构体提供默认的哈希函数，所以编译器才会抛出那个错误。

接下来分两部分解答你的问题：

一、可以用来实现A*的其他数据结构 #

其实有不少选择，根据你的场景灵活挑选就行：

• 标准库优先队列：你已经自己实现了优先队列，其实std::priority_queue也完全能用，不过要注意它默认是大顶堆（优先弹出最大元素），而A*需要的是小顶堆（优先弹出f值最小的节点），所以你得自定义一个比较器，比如基于节点的f值（g+h）从小到大排序。
• std::map：如果不想折腾哈希的话，std::map是个不错的替代。它基于红黑树实现，不需要哈希函数，只要你给locatie重载了<运算符就能用。虽然平均性能不如unordered_map，但在大多数网格A*的场景下完全够用。
• 二维数组/vector：如果你的网格大小固定且不算太大，直接用二维容器（比如std::vector<std::vector<NodeInfo>>）来存储每个节点的信息（g值、f值、父节点等）是最省心的，访问速度还快，不用处理任何哈希或者排序的问题。

二、修复unordered_map的哈希错误 #

要让unordered_map支持locatie作为键，你需要给这个类型提供哈希函数，同时还要重载==运算符（用来判断两个键是否相等），这里有两种常用方法：

方法1：自定义哈希结构体 #

先给locatie重载==运算符：

struct locatie {
    int x;
    int y;

    // 重载==，用于unordered_map判断键是否相等
    bool operator==(const locatie& other) const {
        return x == other.x && y == other.y;
    }
};

然后写一个哈希结构体：

struct LocatieHash {
    size_t operator()(const locatie& l) const {
        // 把x和y的哈希值组合起来，这里用移位+异或的方式，你也可以用其他更稳妥的组合逻辑
        size_t hashX = std::hash<int>()(l.x);
        size_t hashY = std::hash<int>()(l.y);
        return hashX ^ (hashY << 1);
    }
};

最后声明unordered_map的时候指定这个哈希函数：

// 假设NodeData是你存储节点信息的类型
std::unordered_map<locatie, NodeData, LocatieHash> openMap;

方法2：特化std::hash模板（不推荐但可行） #

你也可以在std命名空间里特化hash模板，这样就不用每次声明unordered_map都指定哈希函数了：

namespace std {
    template<> struct hash<locatie> {
        size_t operator()(const locatie& l) const {
            size_t hashX = std::hash<int>()(l.x);
            size_t hashY = std::hash<int>()(l.y);
            return hashX ^ (hashY << 1);
        }
    };
}

不过要注意，这种方式只适合locatie是全局命名空间下的自定义类型，否则可能会有未定义行为，所以更推荐第一种方法。

另外，如果你转用std::map的话，只需要给locatie重载<运算符就行：

bool operator<(const locatie& other) const {
    // 先比较x，x相等再比较y
    return x < other.x || (x == other.x && y < other.y);
}

这样std::map<locatie, NodeData>就能正常工作了。

内容的提问来源于stack exchange，提问作者Mareș Ștefan