Cómo filtrar elementos de un estándar :: mapa?

Question

Tengo aproximadamente el siguiente código. ¿Podría hacerse esto más agradable o más eficiente? Tal vez usando std::remove_if? ¿Puedes eliminar elementos del mapa al atravesarlo? ¿Podemos evitar usar el mapa temporal?

typedef std::map<Action, What> Actions; 
static Actions _actions; 

bool expired(const Actions::value_type &action) 
{ 
    return <something>; 
} 

void bar(const Actions::value_type &action) 
{ 
    // do some stuff 
} 

void foo() 
{ 
    // loop the actions finding expired items 
    Actions actions; 
    BOOST_FOREACH(Actions::value_type &action, _actions) 
    { 
    if (expired(action)) 
     bar(action); 
    else 
     actions[action.first]=action.second; 
    } 
    } 
    actions.swap(_actions); 
} 

Answer 1

Puede usar borrar(), pero no sé cómo BOOST_FOREACH manejará el iterador invalidado. El documentation for map::erase indica que solo el iterador borrado será invalidado, los demás deberían estar bien. Así es como me gustaría reestructurar el bucle interno:

Actions::iterator it = _actions.begin(); 
while (it != _actions.end()) 
{ 
    if (expired(*it)) 
    { 
    bar(*it); 
    Actions::iterator toerase = it; 
    ++it; 
    _actions.erase(toerase); 
    } 
    else 
    ++it; 
} 

Answer 2

Si la idea es eliminar los elementos caducados, por qué no usar map::erase? De esta forma, solo tiene que eliminar elementos que ya no necesita, no reconstruir una copia completa con todos los elementos que desea conservar.

La forma en que haría esto es guardar los iteradores que apuntan a los elementos que desea borrar, luego bórrelos todos después de que termine la iteración.

O bien, puede guardar el elemento que ha visitado, pasar al elemento siguiente y borrar el temporal. Sin embargo, los límites del bucle se estropean en su caso, por lo que debe ajustar la iteración usted mismo.

Dependiendo de cómo expiró() se implemente, puede haber otras formas mejores. Por ejemplo, si realiza un seguimiento de una marca de tiempo como la clave del mapa (como expiró() implica?), Puede hacer upper_bound en la marca de tiempo actual, y todos los elementos en el rango [begin(), upper_bound()) necesitan para ser procesado y borrado

Answer 3

Algo que nadie parece saber que es borrado devuelve una nueva, iterador garantizada-a-ser-válida, cuando se utiliza en cualquier contenedor.

Actions::iterator it = _actions.begin(); 
while (it != _actions.end()) 
{ 
    if (expired(*it)) 
    { 
    bar(*it); 
    it = _actions::erase(it); 
    } 
    else 
    ++it; 
} 

Almacenamiento actions.end() probablemente no es un buen plan en este caso ya que la estabilidad iterador no está garantizada, creo.

Answer 4

Una variación del algoritmo Mark Ransom pero sin la necesidad de un temporal.

for(Actions::iterator it = _actions.begin();it != _actions.end();) 
{ 
    if (expired(*it)) 
    { 
     bar(*it); 
     _actions.erase(it++); // Note the post increment here. 
           // This increments 'it' and returns a copy of 
           // the original 'it' to be used by erase() 
    } 
    else 
    { 
     ++it; // Use Pre-Increment here as it is more effecient 
       // Because no copy of it is required. 
    } 
}