Est-ce que pop_back () invalide vraiment * tous * les itérateurs sur un std :: vector?

StackOverflow https://stackoverflow.com/questions/62340

  •  09-06-2019
  •  | 
  •  

Question 

std::vector<int> ints;

// ... fill ints with random values

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}

Ce code ne fonctionne pas car, lorsque pop_back () est appelé, it est invalidé. Mais je ne trouve aucun document parlant d'invalidation d'itérateurs dans std :: vector :: pop_back () .

Avez-vous des liens à ce sujet?

Était-ce utile?

La solution

L'appel à pop_back () supprime le dernier élément du vecteur et l'itérateur de cet élément est invalidé. L'appel pop_back () n'inclue pas les itérateurs des éléments avant le dernier élément, seule la réallocation permet de le faire. D'après "Référence de la bibliothèque standard C ++" de Josuttis:

  

Insertion ou suppression d'éléments   invalide les références, les pointeurs et   itérateurs qui font référence à ce qui suit   élément. Si une insertion cause   réallocation, elle invalide tout   références, itérateurs et pointeurs.

Autres conseils

Voici votre réponse, directement de The Holy Standard:

23.2.4.2 Un vecteur satisfait à toutes les exigences d'un conteneur et d'un conteneur réversible (données dans deux tableaux en 23.1) et d'une séquence, y compris la plupart des spécifications de séquence optionnelles (23.1.1).
23.1.1.12 Tableau 68 expressiona.pop_back () retourne aucun type sémantique opérationnelle a.erase (- a.end ()) ContainerVector, liste, deque

Notez que a.pop_back est équivalent à a.erase (- a.end ()). En regardant les détails du vecteur sur l'effacement:

23.2.4.3.3 - Effacement de l’itérateur (position de l’itérateur) - Effets - Invalide tous les itérateurs et les références après le point de l’effacement .

Par conséquent, une fois que vous avez appelé pop_back, tous les itérateurs de l'élément final (qui n'existe plus à présent) sont invalidés.

Si vous examinez votre code, le problème est que, lorsque vous supprimez le dernier élément et que la liste devient vide, vous l'incrémentez toujours et vous sortez de la fin de la liste.

(J'utilise le schéma de numérotation utilisé dans le brouillon C ++ 0x, disponible ici

Le tableau 94 à la page 732 indique que pop_back (s'il existe dans un conteneur de séquence) a l'effet suivant: 

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); }

23.1.1, le point 12 indique que:

  

Sauf spécification contraire (explicitement ou en définissant une fonction en termes d'autres fonctions), invocation d'un conteneur   Une fonction membre ou le passage d’un conteneur en tant qu’argument à une fonction de bibliothèque ne doit pas invalider les itérateurs, ni changer   les valeurs de, objets dans ce conteneur.

Les deux utilisateurs accédant à end () en tant que préfixe d'application - n'ont pas cet effet, erase () cependant:

23.2.6.4 (concernant vector.erase () point 4):

  

Effets: Invalide les itérateurs et les références à ou après le point de l’effacement.

Donc, en conclusion: pop_back () n'invalidera qu'un itérateur du dernier élément, conformément à la norme.

Voici une citation de la documentation STL de SGI ( http: //www.sgi. com / tech / stl / Vector.html ):

[5] Les itérateurs d'un vecteur sont invalidés lorsque sa mémoire est réaffectée. De plus, l'insertion ou la suppression d'un élément au milieu d'un vecteur invalide tous les itérateurs qui pointent sur des éléments après le point d'insertion ou de suppression. Il s'ensuit que vous pouvez empêcher l'invalidation des itérateurs d'un vecteur si vous utilisez reserve () pour préallouer autant de mémoire que le vecteur n'utilisera jamais, et si toutes les insertions et les suppressions se trouvent à la fin du vecteur.

Je pense qu'il s'ensuit que pop_back n'invalide que l'itérateur pointant sur le dernier élément et l'itérateur end (). Nous avons vraiment besoin de voir les données pour lesquelles le code échoue, ainsi que la manière dont il ne parvient pas à décider de ce qui se passe. Autant que je sache, le code devrait fonctionner - le problème habituel dans ce code est que la suppression des éléments et ++ sur l'itérateur se produit dans la même itération, comme le fait remarquer @mikhaild. Cependant, dans ce code, ce n'est pas le cas: ++ ne se produit pas lorsque pop_back est appelé.

Quelque chose de mauvais peut encore arriver quand il pointe sur le dernier élément, et que le dernier élément est inférieur à 10. Nous comparons maintenant un invalidé et une fin (). Cela peut toujours fonctionner, mais aucune garantie ne peut être donnée.

Les itérateurs ne sont invalidés que lors de la réallocation de stockage. Google est votre ami: voir la note 5 de bas de page .

Votre code ne fonctionne pas pour d'autres raisons.

pop_back () invalide uniquement les itérateurs qui pointent vers le dernier élément. Depuis la référence de la bibliothèque standard C ++:

  

Insertion ou suppression d'éléments   invalide les références, les pointeurs et   itérateurs qui font référence à ce qui suit   élément. Si une insertion cause   réallocation, elle invalide tout   références, itérateurs et pointeurs.

Donc, pour répondre à votre question, non, cela n’annule pas tous les itérateurs.

Toutefois, dans votre exemple de code, il peut invalider it lorsqu'il pointe vers le dernier élément et que la valeur est inférieure à 10. Dans ce cas, STL de débogage Visual Studio marquera l'itérateur comme invalidé, et une vérification supplémentaire pour que ce ne soit pas égal à end () affichera une assertion.

Si les itérateurs sont implémentés en tant que pointeurs purs (comme ils le seraient probablement dans tous les cas de vecteur STL non débogués), votre code devrait simplement fonctionner. Si les itérateurs sont plus que des pointeurs, votre code ne gère pas ce cas de suppression correcte du dernier élément.

L’erreur est que, quand "il" pointe sur le dernier élément du vecteur et si cet élément est inférieur à 10, ce dernier élément est supprimé. Et maintenant & it; it " pointe vers ints.end (), à côté de "it ++" déplace le pointeur sur ints.end () + 1, et maintenant "it" " fuyant ints.end (), et vous obtenez une boucle infinie qui parcourt toute votre mémoire:).

La "spécification officielle" " est la norme C ++. Si vous n'avez pas accès à une copie de C ++ 03, vous pouvez obtenir le dernier brouillon de C ++ 0x sur le site Web du Comité: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

La "sémantique opérationnelle" une section des exigences du conteneur spécifie que pop_back () est équivalent à {iterator i = end (); --je; effacer (i); }. la section [vector.modifiers] pour effacer indique "Effets: invalide les itérateurs et les références au ou après le point de l’effacement".

Si vous voulez l'argument intuition, pop_back est no-fail (puisque la destruction de value_types dans les conteneurs standard n'est pas autorisée à lancer des exceptions), elle ne peut donc effectuer aucune copie ni aucune affectation (puisqu'ils peuvent le faire). peut deviner que l'itérateur de l'élément effacé et l'itérateur de fin sont invalidés, mais que les autres ne le sont pas.

pop_back () n'invalidera que , si cette pointe vers le dernier élément du vecteur. Votre code échouera donc chaque fois que le dernier entier du vecteur est inférieur à 10, comme suit:

* it = ints.back (); // Définissez * la valeur qu'il a déjà

   ints.pop_back (); // Invalide l'itérateur
   continuer; // Boucle en boucle et accéder à l'itérateur non valide

Vous pouvez envisager d'utiliser la valeur de retour de erase au lieu de permuter l'élément de retour à la position supprimée et de revenir. Pour les séquences, effacer renvoie un itérateur pointant l'élément au-delà de l'élément à supprimer. Notez que cette méthode peut entraîner plus de copies que votre algorithme d'origine. 

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std :: remove_if pourrait également être une solution alternative. 

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std :: remove_if est (comme mon premier algorithme) stable, donc ce n'est peut-être pas le moyen le plus efficace de le faire, mais c'est succinct.

Consultez les informations ici (cplusplus.com) :

  

Supprimer le dernier élément

     

Supprime le dernier élément du vecteur, ce qui réduit la taille du vecteur de un et invalide tous les itérateurs et leurs références.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top