другой результат между c + set и unordered_set - PullRequest
Новая
       34

другой результат между c + set и unordered_set

0 голосов
/ 24 ноября 2018

Я работаю над вопросом Leetcode Frog Jump и нахожу некоторый проводной результат, когда я использую unordered_set вместо set для следующего теста.Оба unordered_set и set имеют размер 4, но похоже, что unordered_set не проходит через все элементы.

[0,1,2,3,4,5,6,7,8,9,10,11] output: set size 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();
}

1 Ответ

0 голосов
/ 24 ноября 2018

Это происходит из-за того, что некоторые из ваших вставок изменяют тот же контейнер, который вы сейчас выполняете, циклом for.Неудивительно, что вставки в set и в unordered_set могут оказаться в разных позициях в линейной последовательности элементов контейнера.В одном контейнере новый элемент заканчивается перед текущей позиции и позже повторяется циклом.В другом контейнере новый элемент заканчивается на позади текущей позиции и никогда не видится циклом.

Как правило, не рекомендуется изменять контейнер, который вы в данный момент перебираете, с помощьюоснованный на диапазоне for цикл.Это может не привести к неопределенному поведению в вашем случае (если вы используете ассоциативные контейнеры со стабильными итераторами), но все же ... на мой взгляд, основанный на диапазоне for должен быть зарезервирован для перебора неизменяемых контейнеров.

В вашем случае вставка нового элемента в std::unordered_set может вызвать перефразирование и сделать недействительными все итераторы этого unordered_set.Это означает, что если в данный момент unordered_set повторяется с помощью for, основанного на диапазоне, то вы получите неопределенное поведение.

...