remove_if equivalente para std::map

6 minutos de lectura

Estaba tratando de borrar una variedad de elementos del mapa en función de una condición particular. ¿Cómo lo hago usando algoritmos STL?

Inicialmente pensé en usar remove_if pero no es posible porque remove_if no funciona para el contenedor asociativo.

¿Hay algún algoritmo equivalente a “remove_if” que funcione para el mapa?

Como una opción simple, pensé en recorrer el mapa y borrar. Pero, ¿recorrer el mapa y borrar es una opción segura? (ya que los iteradores se vuelven inválidos después del borrado)

Utilicé el siguiente ejemplo:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

  • ¿Qué quieres decir con que remove_if no funciona?

    – dirkgently

    29 de abril de 2009 a las 5:22

  • No puedo usar remove_if para encontrar un elemento en el mapa, ¿verdad? Dio un error de tiempo de compilación. ¿Me estoy perdiendo de algo?

    – aJ.

    29 de abril de 2009 a las 6:10

  • No, no funciona, ya que remove_if funciona reordenando una secuencia, moviendo elementos que fallan la condición hacia el final. Por lo tanto, funciona en una T[n]pero no un mapa.

    – MSalters

    29 de abril de 2009 a las 7:00

  • Con C+11, puedes usar for(auto iter=aMap.begin(); iter!=aMap.end(); ){ ....} para reducir el desorden. El resto es como dijeron otros. Esta pregunta me ahorró algunos pelos de punta justo ahora 😉

    – Atul Kumar

    21 de marzo de 2015 a las 0:01


  • Veo que C++ 20 tiene std::erase_if por std::map … si tan solo pudiera transportar mi código al futuro.

    – wcochran

    25 de julio de 2021 a las 13:30

remove if equivalente para stdmap
steve locura

Casi.

for(; iter != endIter; ) {
     if (Some Condition) {
          iter = aMap.erase(iter);
     } else {
          ++iter;
     }
}

Lo que tenías originalmente incrementaría el iterador dos veces si borraste un elemento de él; potencialmente podría omitir elementos que necesitaban ser borrados.

Este es un algoritmo común que he visto usado y documentado en muchos lugares.

[EDIT] Tiene razón en que los iteradores se invalidan después de un borrado, pero solo los iteradores que hacen referencia al elemento que se borra, los demás iteradores siguen siendo válidos. Por lo tanto usando iter++ en el erase() llamada.

  • Estoy confundido; ¿Por qué usarías for(; … 😉 en lugar de while(…)? Además, aunque esto probablemente funcione, ¿no devuelve .erase un iterador del siguiente? Por lo tanto, parece que el blog if (Some Condition) debería ser iter = aMap.erase(iter) para ser el más compatible. ¿Quizás me estoy perdiendo algo? Me falta la experiencia que algunos de ustedes tienen.

    – taxiliano

    20 de febrero de 2011 a las 3:38


  • Tenga en cuenta que en C++ 11 todos los contenedores asociativos, incluidos mapdevuelve el siguiente iterador de erase(iter). es mucho mas limpio de hacer iter = erase( iter ).

    – Patatas

    21 de junio de 2012 a las 15:53

  • @taxilian (años tarde) while() o for() funcionarían, pero semánticamente, la gente a menudo usa for() para iterar sobre un rango conocido, y while() para un número desconocido de bucles. Dado que el rango es conocido en este caso (desde el principio, hasta endIter), for() no sería una opción inusual y probablemente sería más común. Pero, de nuevo, ambos serían aceptables.

    – Jamin Grey

    15 de junio de 2013 a las 22:45

  • @taxilian Más importante aún: con ‘for’, puede tener su definición de iterador DENTRO del alcance del ciclo, para que no interfiera con el resto de su programa.

    – Sanchises

    18 de junio de 2014 a las 7:34

  • @athos La pregunta está formulada en voz pasiva, “se recomienda”. No hay una recomendación universal. Creo que mi último comentario es la forma más directa. Implica dos copias de la variable del iterador, que pierde un poco de eficiencia como alguien señaló aquí. Es su llamada lo que es apropiado para usted.

    – Patatas

    6 de junio de 2017 a las 12:24

1646760010 783 remove if equivalente para stdmap
Salvador de hierro

erase_if para std::map (y otros contenedores)

Utilizo la siguiente plantilla para esto mismo.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

Esto no devolverá nada, pero eliminará los elementos del std::map.

Ejemplo de uso:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Segundo ejemplo (le permite pasar un valor de prueba):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

  • @CodeAngry Gracias, siempre me pareció extraño que esto no existiera en std. Entiendo por qué no es miembro de std::mappero creo que algo así debería estar en la biblioteca estándar.

    – Salvador de Hierro

    17 de diciembre de 2013 a las 16:15


  • Se agregará en C++20 para std::map y otros.

    – Roi Dantón

    15 de agosto de 2019 a las 13:43

1646760010 76 remove if equivalente para stdmap
usuario1633272

Ahora, std::experimental::erase_if está disponible en el encabezado <experimental/map>.

Ver: http://en.cppreference.com/w/cpp/experimental/map/erase_if

  • Ahora está en C++20

    – LF

    4 sep 2019 a las 9:50

Obtuve esta documentación de la excelente referencia SGI STL:

Map tiene la importante propiedad de que insertar un nuevo elemento en un mapa no invalida los iteradores que apuntan a elementos existentes. Borrar un elemento de un mapa tampoco invalida ningún iterador, excepto, por supuesto, los iteradores que en realidad apuntan al elemento que se está borrando.

Entonces, el iterador que tiene que apunta al elemento que se va a borrar, por supuesto, será invalidado. Haz algo como esto:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Aquí hay una solución elegante.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

remove if equivalente para stdmap
kate gregorio

El código original tiene un solo problema:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Aquí el iter se incrementa una vez en el bucle for y otra vez en erase, lo que probablemente terminará en algún bucle infinito.

1646760012 789 remove if equivalente para stdmap
MartínBG

para aquellos en C++20 hay incorporado std::erase_if funciones para mapa y mapa_desordenado:

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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad