remove_if equivalente para std :: map

Question

Estaba tratando de borrar una gama 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 ya que remove_if no funciona para el contenedor asociativo.

¿Hay alguna " remove_if " algoritmo equivalente que funciona para el mapa?

Como una opción simple, pensé en recorrer el mapa y borrar. ¿Pero está recorriendo el mapa y borrando una opción segura? (Ya que los iteradores se vuelven inválidos después de borrar)

Usé 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;
}

Answer 1

Casi.

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

Lo que tenía originalmente incrementaría el iterador dos veces si borrara un elemento de él; potencialmente podría omitir elementos que debían borrarse.

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

[EDITAR] 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, otros iteradores siguen siendo válidos. Por lo tanto, usar iter ++ en la llamada erase ().

Answer 2

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 mapa std ::.

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

Answer 3

Recibí esta documentación de la excelente referencia SGI STL :

  

El mapa tiene la propiedad importante que   insertar un nuevo elemento en un mapa   no invalida los iteradores que   Señalar elementos existentes. Borrando un   elemento de un mapa tampoco   invalidar cualquier iterador, excepto, de   Por supuesto, para iteradores que realmente   señalar el elemento que está siendo   borrado.

Por lo tanto, el iterador que tiene que apunta al elemento que se va a borrar, por supuesto, se invalidará. Haga algo como esto:

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

Answer 4

El código original solo tiene un problema:

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

Aquí el iter se incrementa una vez en el ciclo for y otro en el borrado, lo que probablemente terminará en un ciclo infinito.

Answer 5

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

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

Answer 6

De las notas inferiores de:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

un contenedor asociativo de par no puede proporcionar iteradores mutables (como se define en los requisitos del iterador trivial), porque el tipo de valor de un iterador mutable debe ser asignable y el par no es asignable. Sin embargo, un Contenedor Asociativo de Par puede proporcionar iteradores que no son completamente constantes: iteradores de modo que la expresión (* i) .second = d sea válida.

Answer 7

Primero

  

El mapa tiene la propiedad importante 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 realmente apuntan al elemento que se está borrando.

Segundo, el siguiente código es bueno

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

Cuando se llama a una función, los parámetros se evalúan antes de la llamada a esa función.

Entonces, cuando iter ++ se evalúa antes de la llamada a borrar, el operador ++ del iterador devolverá el elemento actual y apuntará al siguiente elemento después de la llamada.

Answer 8

En mi humilde opinión no hay remove_if() equivalente.
No puede reordenar un mapa.
Por lo tanto, erase() no puede poner sus pares de intereses al final al cual puede llamar <=>.

Answer 9

Basado en Respuesta de Iron Savior Para aquellos que deseen proporcionar un rango más similar al de los iteradores de toma funcional std .

template< typename ContainerT, class _FwdIt, class _Pr >
void erase_if(ContainerT& items, _FwdIt it, _FwdIt _Last, _Pr _Pred) {
    for (; it != _Last; ) {
        if (_Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

Curioso si hay alguna forma de perder los elementos ContainerT y obtenerlos del iterador.

Answer 10

Respuesta de Steve Folly Siento que es más eficiente.

Aquí hay otra solución fácil pero menos eficiente :

La solución usa remove_copy_if para copiar los valores que queremos en un nuevo contenedor, luego intercambia el contenido del contenedor original con los del nuevo:

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

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);

Answer 11

Si desea borrar todos los elementos con una clave mayor que 2, entonces la mejor manera es

map.erase(map.upper_bound(2), map.end());

Sin embargo, solo funciona para rangos, no para ningún predicado.

Answer 12

Yo uso así

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }