Borrar elementos de unordered_map en un bucle

4 minutos de lectura

avatar de usuario
cachorro de zorro

Hay varias respuestas en StackOverflow que sugieren que el siguiente ciclo es una buena manera de borrar elementos de un std::unordered_map que satisfacen algún predicado pred:

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

Estoy específicamente interesado en C ++ 11 (a diferencia de C ++ 14) y el siguiente siniestro nota sobre cppreference.com sugiere que el bucle anterior depende de un comportamiento indefinido y, después de todo, es posible que no funcione en C++ 11:

Se conserva el orden de los elementos que no se borran (esto hace posible borrar elementos individuales mientras se itera por el contenedor) (desde C++14)

Ver también Título 2356. Estabilidad del borrado en contenedores asociativos desordenados que contiene un cambio de redacción solicitado para Borrador de trabajo N3797 ítem 14 en la página 754 (la frase adicional comienza con “, y conserva el orden relativo…”).

Esta redacción es relativa a N3797.

Modificar [unord.req]p14 como se indica:

-14- Los miembros insert y emplace no afectarán la validez de las referencias a los elementos del contenedor, pero pueden invalidar todos los iteradores del contenedor. Los miembros de borrado invalidarán solo los iteradores y las referencias a los elementos borrados, y preservará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 ciclo anterior depende de un comportamiento indefinido en C++11, ¿cuál es la forma más eficiente de resolver este problema en C++11?

  • Por lo general, cuando una restricción se fortalece de esa manera, es porque todos los compiladores representados por los miembros del comité ya cumplen. Aunque tienes razón en estar nervioso.

    – Mark Ransom

    19 de julio de 2016 a las 21:41

  • @MarkRansom ¿Hay alguna manera de estar seguro? Es decir, ¿cuál es la forma correcta de hacer esto bajo el estándar C++ 11?

    – cachorro de zorro

    19 de julio de 2016 a las 21:44


  • sospecho que hay no fue una forma de garantizar la seguridad, de ahí el cambio a la norma.

    – Mark Ransom

    19 de julio de 2016 a las 22:31

  • Encontré otro SO Q/A que enlaza con Edición 2356lo que aclara un poco sobre la conformidad de todos los compiladores.

    – cachorro de zorro

    20 de julio de 2016 a las 0:05

  • ¿No puedes simplemente tomar repetidamente mymap.begin() en un bucle y quitarlo mientras no está mymap.end()?

    – CygnusX1

    25 de agosto de 2020 a las 6:31

avatar de usuario
olipro

Desafortunadamente, para cumplir con C++ 11, está un poco limitado en la forma en que puede abordar esto. Sus opciones básicamente se reducen a:

  1. Iterar sobre el unordered_map y cree 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 recomendaría esto para conjuntos de datos pequeños. aquellos de ustedes que sienten que goto es incondicionalmente malo, bueno, esta opción podría decirse que es mala.

    //std::unordered_map<...> mymap;
    reset:
    for (auto&& i : mymap)
        if (/*compare i*/) {
            mymap.erase(i.first);
            goto reset;
        }
    
  3. como algo allí afuera opción, también puede simplemente crear una nueva unordered_map y mueve los elementos que quieras 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);
    

  • Sí, 1 y 3 son las dos opciones que he pensado. Obviamente no me gusta ninguno de los dos, pero no se me ocurre nada mejor.

    – cachorro de zorro

    20 de julio de 2016 a las 0:03

  • requiere C++ 14 para compilar? 😉

    – Olipro

    20 de julio de 2016 a las 0:22

  • Tal vez en tres años. 😉

    – cachorro de zorro

    20 de julio de 2016 a las 0:24

Usar borrar_si (c++20) en lugar de un bucle (ver https://en.cppreference.com/w/cpp/container/unordered_map/erase_if)

Ejemplo para eliminar claves impares de un mapa:

std::unordered_map<int, char> data {{1, 'a'},{2, 'b'},{3, 'c'},{4, 'd'},
                                    {5, 'e'},{4, 'f'},{5, 'g'},{5, 'g'}};

const auto count = std::erase_if(data, [](const auto& item) {
    auto const& [key, value] = item;
    return (key & 1) == 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.

  • Por supuesto. Supongo que estoy tratando de ver si hay una solución más eficiente.

    – cachorro de zorro

    19 de julio de 2016 a las 21:59

avatar de usuario
jonas_toth

Siempre consulte primero los algoritmos stl

Este parece ser el buscado:
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 c++11.

¿Ha sido útil esta solución?