c++ - usar - modificar tag git

Borrar elementos de unordered_map en un bucle

Question

Hay varias respuestas en StackOverflow que sugieren que el siguiente bucle es una buena forma de borrar elementos de un std::unordered_map que satisface algunos pred predicados:

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

Estoy especialmente interesado en C ++ 11 (a diferencia de C ++ 14), y la siguiente nota siniestra en cppreference.com sugiere que el bucle anterior depende de un comportamiento indefinido y puede que no funcione en C ++ 11 después de todo:

El orden de los elementos que no se borran se conserva (esto permite borrar elementos individuales mientras se recorre el contenedor) (desde C ++ 14)

Consulte también el Título 2356. Estabilidad del borrado en contenedores asociativos no ordenados que contiene un cambio de redacción solicitado al ítem 14 del Proyecto de trabajo N3797 en la página 754 (la frase adicional comienza con "y conserva el orden relativo ...").

Esta redacción es relativa a N3797.

Modifique [unord.req], p14 como se indica:

-14- Los miembros de inserción y emplazamiento no afectarán la validez de las referencias a los elementos del contenedor, pero pueden invalidar todos los iteradores del contenedor. Los miembros borrados invalidarán solo los iteradores y las referencias a los elementos borrados, y conservarán el orden relativo de los elementos que no se borran.

Si mi interpretación de la nota de cppreference.com es correcta y el bucle anterior depende de un comportamiento indefinido en C ++ 11, ¿cuál es la forma más eficiente de resolver este problema en C ++ 11?

Answer 1

Bueno, siempre puedes hacer esto:

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

Es más lento, pero la complejidad es la misma.

Answer 2

Para cumplir con C ++ 11, lamentablemente, está un poco limitado en la forma de abordar esto. Sus opciones básicamente se reducen a:

1. Iterate sobre unordered_map y crea una lista de claves para eliminar así:

   //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. Iterar sobre el objeto y restablecer si encontramos algo para eliminar, realmente solo lo recomendaría para conjuntos de datos pequeños. Aquellos de ustedes que sienten que goto es incondicionalmente malo, bueno, esta opción es discutiblemente mala.

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

3. Como una opción un poco hacia fuera , también podría crear un nuevo unordered_map y mover los elementos que desea conservar. Podría decirse que esta es una buena opción cuando tiene más que eliminar que conservar.

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

Answer 3

Siempre consulte primero los algoritmos stl.

Este parece ser el deseado: http://www.cplusplus.com/reference/algorithm/remove_if/

Para una descripción general: http://www.cplusplus.com/reference/algorithm/

EDITAR cppreference tiene un ejemplo similar en la parte inferior del sitio. Funciona con un compilador de c ++ 11.