使用std::unordered_map实现有向图边操作时遇编译错误求助

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

你想实现O(1)时间的边操作，选std::unordered_map完全是正确的思路——但编译报错十有八九是因为你用作键的类型（大概率是顶点对，比如std::pair<Vertex, Vertex>）没有对应的哈希函数，毕竟unordered_map默认只支持基础类型和部分STL类型的哈希，自定义类型或者std::pair这类组合类型需要你手动提供哈希逻辑。

下面给你几个靠谱的解决方案，按需选择：

方案1：给顶点对自定义哈希函数 #

如果你的边是用std::pair<FromVertex, ToVertex>作为键（比如顶点是int类型），可以写一个哈希结构体，然后在声明unordered_map的时候指定它：

#include <unordered_map>
#include <utility>

// 针对pair<int, int>的自定义哈希
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2>& p) const {
        // 混合两个哈希值，避免碰撞（也可以用更复杂的算法，比如boost的哈希组合逻辑）
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

class DirectedGraph {
private:
    // 键：起点-终点对，值：边的成本
    std::unordered_map<std::pair<int, int>, int, PairHash> edgeCosts;
public:
    // O(1) 获取边成本：用find而不是[]，避免const容器下的编译错误
    int getEdgeCost(int from, int to) const {
        auto it = edgeCosts.find({from, to});
        return it != edgeCosts.end() ? it->second : -1; // 用-1表示边不存在，可按需调整
    }

    // O(1) 插入/修改边成本：[]操作符完美适配，不存在则插入，存在则覆盖
    void setEdgeCost(int from, int to, int cost) {
        edgeCosts[{from, to}] = cost;
        // C++17及以上也可以用insert_or_assign，语义更清晰：
        // edgeCosts.insert_or_assign({from, to}, cost);
    }
};

方案2：把顶点对转成基础类型作为键 #

如果不想写自定义哈希，也可以把顶点对转换成uint64_t这类能被默认哈希处理的类型（适合顶点是32位整数的场景）：

#include <unordered_map>
#include <cstdint>

class DirectedGraph {
private:
    std::unordered_map<uint64_t, int> edgeCosts;

    // 辅助函数：把两个int顶点转成64位键
    uint64_t getKey(int from, int to) const {
        return (static_cast<uint64_t>(from) << 32) | static_cast<uint32_t>(to);
    }
public:
    int getEdgeCost(int from, int to) const {
        auto it = edgeCosts.find(getKey(from, to));
        return it != edgeCosts.end() ? it->second : -1;
    }

    void setEdgeCost(int from, int to, int cost) {
        edgeCosts[getKey(from, to)] = cost;
    }
};

方案3：自定义顶点类的处理 #

如果你的顶点是自定义类（比如struct Vertex { int id; }），除了哈希函数，还需要提供相等比较逻辑（要么重载==，要么自定义相等比较器）：

#include <unordered_map>
#include <utility>

struct Vertex {
    int id;
    // 重载==，让unordered_map能判断两个顶点是否相等
    bool operator==(const Vertex& other) const {
        return id == other.id;
    }
};

// 针对Vertex的哈希函数
struct VertexHash {
    std::size_t operator()(const Vertex& v) const {
        return std::hash<int>{}(v.id);
    }
};

// 针对pair<Vertex, Vertex>的哈希函数
struct VertexPairHash {
    std::size_t operator()(const std::pair<Vertex, Vertex>& p) const {
        auto hash1 = VertexHash{}(p.first);
        auto hash2 = VertexHash{}(p.second);
        return hash1 ^ (hash2 << 1);
    }
};

class DirectedGraph {
private:
    std::unordered_map<std::pair<Vertex, Vertex>, int, VertexPairHash> edgeCosts;
public:
    // ... 后续的get/set方法和前面类似
};

额外注意的坑 #

如果你在const成员函数里用[]访问unordered_map会编译失败！因为[]会在键不存在时插入新元素，而const容器不允许修改——所以获取边成本一定要用find方法，这是很多人踩过的坑。

内容的提问来源于stack exchange，提问作者Razvan Axinie