基于范围的for循环遍历unordered_map时因dfs提前终止问题排查

问题描述 #

解法代码预期输出为10，但findLongestPath()函数出现异常：

• 遍历unordered_map<int, vector<int>>时，不管用基于范围的for循环还是普通迭代器循环，调用dfs()函数后循环仅执行一次迭代就退出，没法遍历所有元素计算最长路径。
• 把dfs()调用替换成固定值dfss=1后，循环能正常走完所有迭代，该问题已通过VS Code调试确认。

核心原因 #

大概率是dfs()函数内部对正在遍历的unordered_map<int, vector<int>>做了增/删元素操作。unordered_map在增删元素时可能触发rehash，导致当前迭代器失效，直接让循环提前终止。

解决办法 #

办法1：遍历临时副本，避免原容器修改影响遍历 #

先把unordered_map的键（或所有元素）复制到临时容器（比如vector），再遍历临时容器调用dfs()，这样就算原map被修改，也不会中断遍历流程：

void findLongestPath(...) {
    // 先把map的键存入临时vector
    vector<int> lengthList;
    for (auto& entry : lenToIndices) {
        lengthList.push_back(entry.first);
    }

    int maxLen = 0;
    // 遍历临时vector
    for (int len : lengthList) {
        for (int idx : lenToIndices[len]) {
            int current = dfs(idx, lenToIndices, words, memo);
            maxLen = max(maxLen, current);
        }
    }
    // ...后续逻辑
}

办法2：修改dfs()，禁止操作遍历中的map #

检查dfs()函数代码，删掉其中对unordered_map<int, vector<int>>的增删操作，确保遍历过程中容器结构稳定。比如如果是动态添加元素到map的逻辑，改成提前预处理所有元素再启动遍历。

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