c+ 集和 unordered_set 之间的不同结果

Question

我正在研究 leetcode Frog Jump 问题，当我为以下测试用例使用 unordered_set 而不是 set 时，发现了一些连线结果。 unordered_set 和 set 的大小都是 4，但看起来 unordered_set 并没有遍历所有元素。

[0,1,2,3,4,5,6,7,8,9,10,11] 输出：设置大小 4 1
2
3
4
无序集大小：4 1

挣扎了好几个小时也找不到任何原因。如果有任何提示，我们将不胜感激。

bool canCross(vector<int>& stones) {
    unordered_map<int, set<int>> dp;
    unordered_map<int, unordered_set<int>> dp1;
    unordered_set<int> s(stones.begin(), stones.end());
    dp[0].insert(0);
    dp1[0].insert(0);

    for (int i = 0; i < stones.size(); ++i) {
        if (i == 10) cout << "set size " << dp[stones[i]].size() << endl;
        for (auto a: dp[stones[i]]) {
            if (i == 10) cout << a << "\t" << endl;
            int b = stones[i];
            if (s.count(b + a - 1)) {
                dp[b + a - 1].insert(a - 1);   
            }
            if (s.count(b + a)) {
                dp[b + a].insert(a);  
            } 
            if (s.count(b + a + 1)) {
                dp[b + a + 1].insert(a + 1);  
            } 
        }

        if (i == 10) cout << "unordered set size: " << dp1[stones[i]].size() << endl;
        for (auto a: dp1[stones[i]]) {
            if (i == 10) cout << a << "\t" << endl;
            int b = stones[i];
            if (s.count(b + a - 1)) {
                dp1[b + a - 1].insert(a - 1);   
            }
            if (s.count(b + a)) {
                dp1[b + a].insert(a);  
            } 
            if (s.count(b + a + 1)) {
                dp1[b + a + 1].insert(a + 1);  
            } 
        }
    }

    return !dp[stones.back()].empty();
}

Answer 1

发生这种情况是因为您的一些插入修改了您当前正在通过 for 循环迭代的同一个容器。毫不奇怪，插入 set 和 unordered_set 可能会在容器元素的线性序列中的不同位置结束。在一个容器中，新元素最终 在当前位置的前面 ，然后由循环迭代。在其他容器中，新元素最终在后面当前位置并且永远不会被循环看到。

修改您当前正在通过基于范围的 for 循环迭代的容器通常不是一个好主意。它可能不会在您的情况下产生任何未定义的行为（如果您使用具有稳定迭代器的关联容器），但仍然......在我看来基于范围的 for 应该保留用于迭代不变的容器。

在您的情况下，将新元素插入 std::unordered_set 可能会触发 rehashing 并使该 unordered_set 的所有迭代器无效。这意味着如果 unordered_set 当前正在被基于范围的 for 迭代，你最终会出现未定义的行为。

c+ 集和 unordered_set 之间的不同结果

different result between c+ set and unordered_set

c++

set

unordered