unordered_map не перебирает все ключи - PullRequest
Новая
       5

unordered_map не перебирает все ключи

0 голосов
/ 11 февраля 2019

У меня есть следующий код для перебора всех ключей в unordered_map, в то время как при переборе я передаю карту какой-то другой функции.По какой-то причине итератор не может перебирать все ключи.Я не могу понять, почему и как это исправить.Если я передаю карту как значение вместо ссылки, тогда она работает как ожидалось, но я хочу передать по ссылке, чтобы сохранить копию.

Код: 

void DFS(char curr, unordered_map<char, unordered_set<char>>& G) {
    cout << "Traversing: " << curr << endl;
    for(const char& ch: G[curr]) {
        DFS(ch, G);
    }
}

int main() {
    unordered_map<char, unordered_set<char>> G;

    G['c'].emplace('b');
    G['b'].emplace('a');

    for(auto it : G) {
        cout << "Starting with: " << it.first << endl;
        DFS(it.first, G);
    }
}

Вывод, который я получаю:: 

Starting with: b
Traversing: b
Traversing: a

Обратите внимание, что это не обходной ключ c.

ОБНОВЛЕНИЕ: Изменение функции DFS для обеспечения соответствия карты, как показано ниже, также не помогает: 

void DFS(const char curr, const unordered_map<char, unordered_set<char>>& G) {
    cout << "Traversing: " << curr << endl;
    for(auto ch: G.at(curr)) {
        DFS(ch, G);
    }
}

И это тоже исключение: 

terminate called after throwing an instance of 'std::out_of_range'
  what():  _Map_base::at

Ответы [ 2 ]

0 голосов
/ 11 февраля 2019

Первоначальной попыткой было изменить карту, добавив запись для a.Вторая попытка вызвала исключение, так как не удалось найти запись для a.

Звучит так, как будто вы хотите завершить поиск, когда значение отсутствует на карте. 

void DFS(const char curr, const unordered_map<char, unordered_set<char>>& G) {
    cout << "Traversing: " << curr << endl;
    auto it = G.find(curr);
    if (it != G.end()) {
        for(auto ch: it->second) {
            DFS(ch, G);
        }
    }
}

В качестве альтернативы, вы можете инициализировать запись a на карте, и любой из этих трех вариантов будет работать (хотя не-const версия наименее безопасна, в этом случае поведение не определено, когда вы не можете найти) 

int main() {
    std::unordered_map<char, std::unordered_set<char>> G;

    G['c'].emplace('b');
    G['b'].emplace('a');
    G['a'];

    for(auto it : G) {
        cout << "Starting with: " << it.first << endl;
        DFS(it.first, G);
    }
}
0 голосов
/ 11 февраля 2019

Это потому, что вы меняете карту, по которой вы перебираете.При этом следует соблюдать осторожность, так как если во время emplace происходит перефразировка, все итераторы становятся недействительными.

...