Nsryjdtyk

I am working on leetcode Frog Jump question and find some wired result when I use unordered_set instead of set for the following test case. unordered_set and set both have size 4, but looks like unordered_set doesn't loop through all elements.

[0,1,2,3,4,5,6,7,8,9,10,11]
output :
set size 4
1

2

3

4

unordered set size: 4
1

Struggleing for hours but can't find out any reason. Any tips would be really appeciated.

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();

}

It happens because some of your insertions modify the same container that you are currently iterating over by a for cycle. Not surprisingly, insertions into setand into unordered_set might end up in different positions in the linear sequence of container elements. In one container the new element ends up in front of the current position and is later iterated over by the cycle. In other container the new element ends up behind the current position and is never seen by the cycle.

It is generally not a good idea to modify container that you are currently iterating over by a range-based for cycle. It might not produce any undefined behavior in your case (if you are using associative containers with stable iterators), but still... in my opinion range-based for should be reserved for iterating over non-changing containers.

In your case insertion of a new element into an std::unordered_set may trigger rehashing and invalidate all iterators of that unordered_set. It means that if that unordered_set is currently being iterated over by a range-based for, you end up with undefined behavior.