Как предотвратить перефразирование std :: unordered_map при удалении элементов?
У меня есть std :: unordered_map, из которого я буду удалять элементы с помощью итерации.
auto itr = myMap.begin();
while (itr != myMap.end()) {
if (/* removal condition */) {
itr = myMap.erase(itr);
} else {
++itr;
}
}
Я хотел бы запретить карте выполнять любые дорогостоящие операции, пока я не закончу удалять все элементы, которые мне нужно удалить. У меня есть действительная проблема? Я неправильно понимаю, как работает внутреннее хранилище?
Решение
Неупорядоченные контейнеры запрещено перефразировать во время erase:
[Unord.req] / P9:
eraseчлены должны делать недействительными только итераторы и ссылки на
стертые элементы, и сохранить относительный порядок элементов
которые не стерты.
Перефразировка делает недействительными итераторы, изменяет порядок элементов и …
Ваш код в порядке, как есть.
Другие решения
Насколько я могу сказать, std::unordered_map разрешено перефразировать erase(itr):
C ++ 11 Таблица 103 — Неупорядоченные требования к ассоциативным контейнерам
a.erase(q)Стирает указанный элемент
отq, Возвращаемое значение
сразу после итератораq
до стирания.Средний случай
O(1), наихудший
дело
O(a.size())
Поэтому может показаться, что у вас есть действительная проблема. Что касается решения этой проблемы, я могу предложить несколько путей:
- Убедитесь, что это актуальная проблема, а не гипотетическая. Профилируйте приложение, посмотрите исходный код вашей библиотеки C ++ и т. Д.
- Если это реальная проблема, рассмотрите возможность использования другого контейнера или другого алгоритма.
- Попробуйте просто пометить элементы для удаления с помощью логического флага, связанного с каждым элементом, и периодически очищать удаленные элементы, тем самым амортизируя затраты.
- Подумайте над тем, чтобы поэкспериментировать с коэффициентом загрузки, как предложено @amit в комментариях. Хотя контейнер все равно будет разрешено
O(a.size())Время стереть элементы, другой коэффициент загрузки может повлиять на реальную производительность вашего приложения.
Я не уверен, что это сработает, я не нахожу подтверждения для этого в документации — но если unordered_map перефразируется в соответствии с классической структурой данных хеш-таблицы, вы можете установить max_load_factor к очень высокому значению и сбросьте его до нормального, когда вы закончите (что вызовет перефразировку) (или к предсказанному значению, если вы можете предсказать, сколько элементов будет удалено).
С точки зрения классической хэш-таблицы, она должна работать, так как перефразировка при уменьшении таблицы происходит, когда размер меньше, чем 1/max_load_factor,
(не уверен, что это так в C ++, но я предполагаю, что это мешает попыткам, поскольку это действительно легко реализовать).