itérer sur std :: multimap et supprimer certaines entrées

Question

Je veux itérer sur tous les éléments dans un std::multimap (toutes les valeurs de toutes les clés), et supprimer toutes les entrées qui satisfont une condition:

#include <map> 

typedef int KEY_TYPE; 
typedef int VAL_TYPE; 

bool shouldRemove(const KEY_TYPE&, const VAL_TYPE&); 

void removeFromMap(std::multimap<KEY_TYPE,VAL_TYPE>& map){ 
    for (auto it = map.begin(); it != map.end(); it++){ 
     if (shouldRemove(it->first,it->second)) 
      map.erase(it); 
    } 
} 

Les travaux d'itération à moins que le premier élément est supprimé, et l'erreur suivante est lancée alors:

carte/set iterator pas Incrementable

Comment le removeFromMap fonction être réécrit afin de fonctionner correctement? Le code devrait fonctionner pour tous les types de clés et de valeurs de la carte.

J'utilise C++ 11 et Visual Studio 2013.

Answer 1

Vous devez augmenter votre iterator avant que vous faites l'effacement. Lorsque vous faites map.erase(it); l'itérateur it devient invalide. Cependant, les autres itérateurs de la carte seront toujours valides. Par conséquent, vous pouvez résoudre ce problème en effectuant un post-augmentation de la iterator ...

auto it = map.begin(); 
const auto end = map.end(); 

while (it != end) 
{ 
    if (shouldRemove(it->first,it->second)) 
    { 
     map.erase(it++); 
       // ^^ Note the increment here. 
    } 
    else 
    { 
     ++it; 
    } 
} 

Le post-incrément appliqué à it à l'intérieur des paramètres map.erase() veillera à ce que it reste valable après l'article est effacé par incrémenter l'itérateur pour pointer vers l'élément suivant sur la carte juste avant d'effacer.

map.erase(it++); 

... est fonctionnellement équivalent à ...

auto toEraseIterator = it; // Remember the iterator to the item we want to erase. 
++it;       // Move to the next item in the map. 
map.erase(toEraseIterator); // Erase the item. 

Comme @imbtfab souligne dans les commentaires, vous pouvez également utiliser it = map.erase(it) pour faire la même chose en C++ 11 sans besoin de post-incrémentation.

Notez également que la boucle for a maintenant été remplacée par une boucle while car nous contrôlons l'itérateur manuellement. De plus, si vous cherchez à rendre votre fonction removeFromMap aussi générique que possible, vous devriez envisager d'utiliser des paramètres de modèle et de transmettre vos itérateurs directement, plutôt que de passer une référence à la multi-carte. Cela vous permettra d'utiliser n'importe quel type de conteneur de type carte, plutôt que de forcer l'insertion d'un multimap.

par exemple.

template <typename Iterator> 
void removeFromMap(Iterator it, const Iterator &end){ 
    ... 
} 

Voici comment les fonctions standard C++ <algorithm> faire aussi (par exemple std::sort(...)).