Comment filtrer les éléments d'un std :: map? [dupliquer]

Question

    

Cette question a déjà une réponse ici:

    

        
•              Que se passera-t-il si vous appeler erase () sur un élément de carte en effectuant une itération du début à la fin?                                      3 réponses                          
    

    

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 en la parcourant? Peut-on é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 gérera l’itérateur invalidé. La documentation sur map :: erase indique que seul l'itérateur effacé sera invalidé, les autres devraient être OK. Voici comment je restructurerais 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

Une variante de l’algorithme Mark Ransom, mais n’a pas besoin de 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.
    }
}

Answer 3

Quelque chose que personne ne semble jamais savoir, c’est que erase renvoie un nouvel itérateur dont la validité est garantie, lorsqu'il est utilisé sur n’importe quel conteneur.

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

Stocker actions.end () n’est probablement pas un bon plan dans ce cas car la stabilité des itérateurs n’est pas garantie, je crois.

Answer 4

Si l’idée est de supprimer les éléments expirés, pourquoi ne pas utiliser map :: effacer ? De cette façon, vous ne devez supprimer que les éléments dont vous n’avez plus besoin et non pas reconstruire une copie complète avec tous les éléments que vous souhaitez conserver.

Pour ce faire, vous devez éviter les itérateurs pointant sur les éléments que vous souhaitez effacer, puis les effacer tous à la fin de l'itération.

Vous pouvez également enregistrer l'élément que vous avez visité, passer à l'élément suivant, puis effacer l'élément temporaire. Les limites de la boucle se brouillent cependant dans votre cas, vous devez donc ajuster l’itération vous-même.

En fonction de la manière dont expired () est implémenté, il peut exister d'autres méthodes plus efficaces. Par exemple, si vous gardez la trace d'un horodatage comme la clé de la carte (comme expired () le suppose?), Vous pouvez utiliser upper_bound sur l'horodatage actuel, ainsi que tous les éléments de la plage [begin (), upper_bound ()). à traiter et à effacer.