C++ unordered_map insert报错求助：邻接表实现图遇重载不匹配

错误原因分析 #

• 类型不匹配：你的adjacencyList定义为unordered_map<string, vector<neighbor>>，每个键对应一个邻居向量，但调用insert时传入的是单个neighbor对象，而非vector<neighbor>，这直接导致编译报错。
• 参数类型错误：addEdge的value参数声明为int，但实际需要处理浮点数（如2.0、0.5），类型不匹配会导致精度丢失或编译问题。
• 逻辑缺失：注释中提到要添加反向边（如a→b权重2.0时，b→a权重0.5），但原代码未实现这部分逻辑。

修正后的完整代码 #

#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Graph
{
private:
    typedef pair<string, double> neighbor; // [邻居顶点, 边权重]
    unordered_map<string, vector<neighbor>> adjacencyList;

public:
    void addEdge(const vector<string> &equation, double value)
    {
        // 添加正向边：equation[0] -> equation[1]，权重value
        adjacencyList[equation[0]].emplace_back(equation[1], value);
        // 添加反向边：equation[1] -> equation[0]，权重1/value
        adjacencyList[equation[1]].emplace_back(equation[0], 1.0 / value);
    }

    // 带访问标记的DFS，避免循环遍历
    double dfs(const string &start, const string &end, unordered_set<string> &visited, double product)
    {
        if (start == end)
        {
            return product;
        }
        visited.insert(start);
        for (const neighbor &n : adjacencyList[start])
        {
            if (visited.find(n.first) == visited.end())
            {
                double result = dfs(n.first, end, visited, product * n.second);
                if (result != -1.0) // 找到有效路径
                {
                    return result;
                }
            }
        }
        return -1.0; // 无有效路径
    }

    // 对外暴露的DFS接口，初始化访问集合
    double findPath(const string &start, const string &end)
    {
        // 若顶点不存在，直接返回-1
        if (adjacencyList.find(start) == adjacencyList.end() || adjacencyList.find(end) == adjacencyList.end())
        {
            return -1.0;
        }
        unordered_set<string> visited;
        return dfs(start, end, visited, 1.0);
    }
};

vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries)
{
    vector<double> results;
    Graph G;

    // 构建图
    for (int i = 0; i < equations.size(); i++)
    {
        G.addEdge(equations[i], values[i]);
    }

    // 处理每个查询
    for (const auto &query : queries)
    {
        double res = G.findPath(query[0], query[1]);
        results.push_back(res);
    }
    return results;
}

// 测试示例
int main()
{
    vector<vector<string>> equations = {{"a", "b"}, {"b", "c"}};
    vector<double> values = {2.0, 3.0};
    vector<vector<string>> queries = {{"a", "c"}, {"b", "a"}, {"c", "a"}};
    
    vector<double> res = calcEquation(equations, values, queries);
    for (double num : res)
    {
        cout << num << " ";
    }
    // 输出：6 0.5 0.166667
    return 0;
}

关键修正点说明 #

• 添加边的方式：不再使用insert，而是直接通过adjacencyList[equation[0]]获取对应向量，再用emplace_back添加单个邻居元素。这种方式会自动处理键不存在的情况（自动创建空向量）。
• 修正参数类型：将addEdge的value参数改为double，匹配浮点数需求。
• 完善DFS逻辑：添加unordered_set记录访问过的顶点，避免循环；返回double类型，支持浮点数结果；增加顶点存在性检查，处理查询中顶点不存在的情况。
• 实现反向边：按照注释要求添加了反向边，满足双向权重的需求。

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