C ++ - оператор unordered_map [], непредвиденное поведение - PullRequest
Новая
       8

C ++ - оператор unordered_map [], непредвиденное поведение

2 голосов
/ 01 апреля 2020

Это простой скрипт, над которым я работал, но я не смог понять, почему он вел себя неожиданно.

По сути, у меня был массив целых чисел с дубликатами, и я хотел сохранить количество раз, когда элемент встречался в массиве, вместе со значением элемента в unordered_map,

Затем для каждая запись на карте { k , v }, мне нужно было определить, существует ли k + 1 в массиве, и если да, что-то с ним сделать , Ниже вы можете увидеть код. 

vector<int> A = {1, 1, 3, 2, 5, 3};

for (int i = 0; i < A.size(); ++i) m[A[i]]++;

int ans = 0;

for (const auto& e: m) {
    if (m[e.first + 1] > 0) ans = max(ans, e.second + m[e.first + 1]);
}

Казалось, все работает. Однако, когда k + 1 не существует в unordered_map, l oop просто завершается, и я не понимаю, почему.

Согласно документации на c ++, оператор [] вставляет новый элемент, если он не существует. Но это ничего не говорит мне о том, что l oop просто не работает.

Я подозреваю, что это как-то связано с тем, что я изменяю unordered_map внутри l oop. Если это так, не могли бы вы, ребята, подробнее рассказать об этом?

Я очень ценю вашу помощь.

1 Ответ

6 голосов
/ 01 апреля 2020

Использование m[e.first + 1] внутри вашего l oop вставит новый элемент в m, если он не существует, что вызовет проблемы для самого l oop, поскольку на основе диапазона for l oop использует итераторы для внутреннего использования, и изменение std::unordered_map во время итерации по нему с помощью итераторов неопределенное поведение , так как вставка может сделать недействительной итераторы :

Если вставка происходит и приводит к перефразированию контейнера, все итераторы становятся недействительными . В противном случае итераторы не будут затронуты. Ссылки не являются недействительными. Перефразировка происходит только в том случае, если новое число элементов превышает max_load_factor()*bucket_count().

Чтобы избежать этого, вместо этого используйте метод find() карты для проверки существования ключа без вставив его: 

for (const auto& e: m) {
    auto iter = m.find(e.first + 1);
    if (iter != m.end()) ans = max(ans, e.second + iter->second);
}
...