Как предотвратить повторное использование std:: unordered_map при удалении элементов?

У меня есть std:: unordered_map, что я буду удалять элементы с помощью итерации.

auto itr = myMap.begin();
while (itr != myMap.end()) {
    if (/* removal condition */) {
        itr = myMap.erase(itr);
    } else {
        ++itr;
    }
}

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

Ответ 1

Неупорядоченные контейнеры запрещены для повторного использования во время erase:

[unord.req]/р14:

Члены erase должны аннулировать только итераторы и ссылки на стираемые элементы и сохранить относительный порядок элементов которые не стираются.

[unord.req]/P9:

Rehashing отменяет итераторы, изменяет порядок между элементами и...

Ваш код в порядке, как есть.

Ответ 2

Насколько я могу судить, std::unordered_map разрешено перефразировать на erase(itr):

С++ 11 Таблица 103 - Требования к непринятым ассоциативным контейнерам

a.erase(q)

Стирает элемент, на который указывает на q. Возвращаемое значение - это итератор сразу после qдо стирания.

Средний случай O(1), худший дело O(a.size())

Таким образом, казалось бы, у вас есть серьезная проблема. Что касается адресации, я могу предложить несколько способов:

Удостоверьтесь, что это настоящая проблема, а не гипотетическая. Профилируйте приложение, посмотрите исходный код для вашей библиотеки С++ и т.д.
Если это актуальная проблема, рассмотрите возможность использования другого контейнера или другого алгоритма.
Рассмотрим просто маркировку элементов для удаления через булевский флаг, связанный с каждым элементом, и время от времени подметая удаленные элементы, тем самым амортизируя затраты.
Рассмотрим эксперименты с коэффициентом загрузки, как это было предложено в комментариях @amit. Несмотря на то, что контейнеру по-прежнему будет разрешено использовать O(a.size()) время для стирания элементов, другой коэффициент загрузки может повлиять на производительность вашего приложения в реальном времени.

Ответ 3

Я не уверен, что это сработает, я не нашел подтверждения в документации, но если unordered_map переигрывает в соответствии с классической структурой данных хэш-таблицы, вы можете установите max_load_factor на очень высокое значение и reset вернется в нормальное состояние, когда вы закончите (что вызовет повторную пересылку) (или к прогнозируемому значению, если вы может предсказать, сколько элементов будет удалено).

В терминах классической хеш-таблицы он должен работать после перефразирования, когда уменьшение таблицы происходит, когда размер меньше, чем 1/max_load_factor.

(не уверен, что это имеет место в С++, но я предполагаю, что он пытается уничтожить попытку, так как это очень просто реализовать).