Effacement par itérateur sur une carte STL C++

Question

Je suis curieux de connaître le raisonnement qui sous-tend le code suivant. Pour une carte donnée, je peux supprimer une plage allant jusqu'à, mais non incluse, end() (évidemment) en utilisant le code suivant :

map<string, int> myMap;
myMap["one"] = 1;
myMap["two"] = 2;
myMap["three"] = 3;

map<string, int>::iterator it = myMap.find("two");

myMap.erase( it, myMap.end() );

Cette opération permet d'effacer les deux derniers éléments de la plage. Cependant, si j'utilisais la version d'erase avec un seul itérateur, je m'attendais à passer myMap.end() n'aboutit à aucune action puisque l'itérateur se trouve clairement à la fin de la collection. Cette situation est différente de celle d'un itérateur corrompu ou invalide, qui entraînerait clairement un comportement indéfini.

Cependant, lorsque je fais cela :

myMap.erase( myMap.end() );

J'obtiens simplement une erreur de segmentation. Je n'aurais pas pensé qu'il était difficile pour map de vérifier si l'itérateur était égal à end() et ne pas prendre de mesures dans ce cas. Y a-t-il une raison subtile à cela qui m'échappe ? J'ai remarqué que même cela fonctionne :

myMap.erase( myMap.end(), myMap.end() );

(c'est-à-dire qu'il ne fait rien)

La raison pour laquelle je pose cette question est que j'ai un code qui reçoit un itérateur valide de la collection (mais qui pourrait être end() ) et je voulais simplement passer cela dans erase plutôt que d'avoir à vérifier d'abord comme ceci :

if ( it != myMap.end() )
    myMap.erase( it );

ce qui me semble un peu lourd. L'alternative est de recoder pour pouvoir utiliser la surcharge d'effacement de type by-key mais je préfère ne pas trop réécrire si je peux m'en empêcher.

Answer 1

La clé est que, dans la bibliothèque standard, les plages déterminées par deux itérateurs sont des plages semi-ouvertes. En notation mathématique [a,b) Ils incluent le premier mais pas le dernier itérateur (si les deux sont identiques, la plage est vide). En même temps, end() renvoie un itérateur qui est un au-delà du dernier ce qui correspond parfaitement à la notation de l'intervalle semi-ouvert.

Lorsque vous utilisez la version de gamme de erase il n'essaiera jamais de supprimer l'élément référencé par le dernier itérateur. Considérons un exemple modifié :

map<int,int> m;
for (int i = 0; i < 5; ++i)
   m[i] = i;
m.erase( m.find(1), m.find(4) );

À la fin de l'exécution, la carte contiendra deux clés 0 y 4 . Notez que l'élément référencé par le second itérateur était no effacé du conteneur.

En revanche, l'opération avec un seul itérateur effacera l'élément référencé par l'itérateur. Si le code ci-dessus était modifié en :

for (int i = 1; i <= 4; ++i ) 
   m.erase( m.find(i) );

L'élément avec clé 4 sera supprimée. Dans votre cas, vous tenterez de supprimer l'itérateur final qui ne fait pas référence à un objet valide.

Je n'aurais pas pensé qu'il était difficile pour map de vérifier si l'itérateur était égal à end() et de ne pas agir dans ce cas.

Non, ce n'est pas difficile à faire, mais la fonction a été conçue avec un contrat différent à l'esprit : l'appelant doit passer un itérateur dans un élément du conteneur. Cela s'explique en partie par le fait qu'en C++, la plupart des fonctionnalités sont conçues de manière à engendrer le coût le plus faible possible, ce qui permet à l'utilisateur d'équilibrer la sécurité et les performances de son côté. L'utilisateur peut tester l'itérateur avant d'appeler erase mais si ce test se trouvait dans la bibliothèque, l'utilisateur ne pourrait pas refuser le test alors qu'il sait que l'itérateur est valide.

Answer 2

N3337 23.2.4 Tableau 102

a.erase( q1, q2)

efface tous les éléments du intervalle [q1,q2) . Retourne q2.

Ainsi, iterator revenant de map::end() n'est pas dans la plage en cas de myMap.erase(myMap.end(), myMap.end()) ;

a.erase(q)

efface l'élément pointé par q. Renvoie un itérateur pointant vers l'élément suivant immédiatement q avant l'élément effacé. Si un tel élément n'existe pas, il renvoie a.end().

Je n'aurais pas pensé qu'il était difficile pour map de était égal à end() et de ne pas agir dans ce cas. Est-ce qu'il y a une raison subtile que je n'ai pas perçue ?

La raison est la même, à savoir que std::vector::operator[] peut ne pas vérifier que l'index est dans la plage, bien sûr.

Answer 3

Lorsque vous utilisez deux itérateurs pour spécifier une plage, celle-ci est constituée des éléments allant de l'élément pointé par le premier itérateur jusqu'à l'élément pointé par le second itérateur, sans toutefois l'inclure. En d'autres termes erase(it, myMap.end()) dit d'effacer tout de it jusqu'à, mais sans inclure end() . Vous pourriez tout aussi bien passer un itérateur qui pointe vers un "vrai" élément comme second élément, et l'élément vers lequel pointe cet itérateur ne serait pas effacé.

Lorsque vous utilisez erase(it) il est indiqué d'effacer l'élément qui it pointe vers. Les end() ne pointe pas vers un élément valide, donc erase(end()) ne fait rien de raisonnable. Il serait possible pour la bibliothèque de diagnostiquer cette situation, et une bibliothèque de débogage le fera, mais cela impose un coût à chaque appel à erase pour vérifier ce vers quoi pointe l'itérateur. La bibliothèque standard n'impose pas ce coût aux utilisateurs. Vous devez vous débrouiller tout seul. <g>