Стирание элементов из unordered_map в цикле

Есть несколько ответов на StackOverflow, которые предполагают, что следующий цикл - прекрасный способ стереть элементы из std::unordered_map, которые удовлетворяют некоторому предикату pred:

std::unordered_map<...> m;
auto it = m.begin();
while (it != m.end())
{
    if (pred(*it))
        it = m.erase(it);
    else
        ++it;
}

Меня особенно интересует С++ 11 (в отличие от С++ 14) и следующая зловещая note на cppreference.com предполагает, что указанный выше цикл зависит от поведения undefined и может не работать в С++ 11:

Порядок элементов, которые не стираются, сохраняется (это позволяет стирать отдельные элементы во время итерации через контейнер) (поскольку С++ 14)

См. также Заголовок 2356. Стабильность стирания в неупорядоченных ассоциативных контейнерах, которая содержит запрошенную формулировку, измените на Рабочий проект N3797, пункт 14 на стр. 754 (добавление дополнительной фразы "и сохранение относительного порядка..." ).

Эта формулировка относится к N3797.

Измените [unord.req], p14, как указано:

-14- Элементы insert и emplace не влияют на действительность ссылок на элементы контейнера, но могут аннулировать все итераторы на контейнер. Члены стирания аннулируют только итераторы и ссылки на стертые элементы и сохранить относительный порядок элементы, которые не стираются.

Если моя интерпретация примечания cppreference.com верна, и указанный выше цикл зависит от поведения undefined в С++ 11, то какой наиболее эффективный способ решить эту проблему в С++ 11?

Ответы

Ответ 1

Чтобы соответствовать С++ 11, вы, к сожалению, немного ограничены в том, как вы можете это решить. Ваши варианты в основном сводятся к:

  • Итерации по unordered_map и создание списка ключей для удаления следующим образом:

    //std::unordered_map<...> mymap;
std::vector<decltype(mymap)::key_type> vec;
for (auto&& i : mymap)
    if (/*compare i*/)
        vec.emplace_back(i.first);
for (auto&& key : vec)
    mymap.erase(key);

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

    //std::unordered_map<...> mymap;
reset:
for (auto&& i : mymap)
    if (/*compare i*/) {
        mymap.erase(i.first);
        goto reset;
    }

  • Как вариант, вы можете просто создать новый unordered_map и переместить элементы, которые вы хотите сохранить. Это, вероятно, хороший вариант, когда у вас есть больше, чем удалить.

    //std::unordered_map<...> mymap;
decltype(mymap) newmap;
for (auto&& i : mymap)
    if (/*i is an element we want*/)
        newmap.emplace(std::move(i));
mymap.swap(newmap);

Ответ 2

Ну, вы всегда можете это сделать:

std::unordered_map<...> m;
std::vector<key_type> needs_removing;
for(auto&& pair : m)
{
    if (pred(pair))
        needs_removing.push_back(pair.first);
}
for(auto&& key : needs_removing)
    m.erase(key);

Это медленнее, но сложность такая же.