Comment filtrer les éléments depuis un std :: map?

Question

J'ai à peu près le code suivant. Cela pourrait-il être rendu plus agréable ou plus efficace? Peut-être en utilisant std::remove_if? Pouvez-vous supprimer des éléments de la carte lors de la traversée? Pouvons-nous éviter d'utiliser la carte temporaire?

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

Vous pouvez utiliser erase(), mais je ne sais pas comment BOOST_FOREACH se chargera de la iterator invalidée. Le documentation for map::erase stipule que seul l'itérateur effacé sera invalidé, les autres devraient être OK. Voici comment je restructurer la boucle intérieure:

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 l'idée est de supprimer des éléments périmés, pourquoi ne pas utiliser map::erase? De cette façon, vous n'avez plus qu'à supprimer les éléments dont vous n'avez plus besoin, à ne pas reconstruire une copie entière avec tous les éléments que vous souhaitez conserver.

La façon dont vous le faire est de mettre hors circuit les itérateurs pointant vers les éléments que vous souhaitez effacer, puis les effacer après l'itération est terminée. Ou, vous pouvez enregistrer l'élément que vous avez visité, passer à l'élément suivant, puis effacer le temporaire. Cependant, les limites de la boucle sont corrompues dans votre cas, vous devez donc affiner l'itération vous-même.

Selon la façon dont expired() est implémenté, il peut y avoir d'autres façons. Par exemple si vous gardez la trace d'un horodatage comme clé de la carte (comme l'indique expired(), vous pouvez faire upper_bound sur l'horodatage actuel, et tous les éléments de la plage [begin(), upper_bound()) être traité et effacé.

Answer 3

Quelque chose que personne ne semble jamais savoir est que erase retourne une nouvelle garantie à être valide iterator, lorsqu'il est utilisé sur tout récipient.

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

Stockage actions.end() est probablement pas un bon plan dans ce cas puisque la stabilité iterator est pas garanti, je crois.

Answer 4

Une variante de l'algorithme Mark Ransom mais sans avoir besoin d'un temporaire.

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. 
    } 
}