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

Question

Есть несколько ответов на 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; 
} 

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

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

Смотрите также Title 2356. Stability of erasure in unordered associative containers, который содержит запрошенное изменение формулировки Working Draft N3797 пункта 14 на странице 754 (дополнительная фраза начала ", и сохранить относительный порядок ...").

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

Изменить [unord.req], P14, как показано:

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

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

Answer 1

Всегда консультируйтесь с СТЛ-алгоритмы первого

Это один, кажется, хотел: http://www.cplusplus.com/reference/algorithm/remove_if/

Для обзора: http://www.cplusplus.com/reference/algorithm/

EDIT cppreference имеет аналогичный пример в в нижней части сайта. Он работает с компилятором C++ 11.

Answer 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); 

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

Answer 3

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

1. итерацию по 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); 
   

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

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

3. как несколько там вариант, вы также можете просто создать новый 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);