Comment effacer et supprimer des pointeurs vers des objets stockés dans un vecteur?

Question

J'ai un vecteur qui stocke des pointeurs vers de nombreux objets instanciés dynamiquement, et je suis en train de parcourir le vecteur et de supprimer certains éléments (retirer du vecteur et de détruire un objet), mais je vais avoir du mal. Voici à quoi il ressemble:

    vector<Entity*> Entities;
    /* Fill vector here */
    vector<Entity*>::iterator it;
    for(it=Entities.begin(); it!=Entities.end(); it++)
        if((*it)->getXPos() > 1.5f)
            Entities.erase(it);

Lorsque l'un des objets d'entité à obtenir xPos> 1.5, le programme se bloque avec une erreur d'assertion ... Tout le monde sait ce que je fais mal?

J'utilise VC ++ 2008.

Answer 1

Vous devez être prudent parce que erase() invalidera itérateurs existants . Cependant, il retournera une nouvelle itérateur valide, vous pouvez utiliser:

for ( it = Entities.begin(); it != Entities.end(); ) {
   if( (*it)->getXPos() > 1.5f ) {
      delete * it;  
      it = Entities.erase(it);
   }
   else {
      ++it;
   }
}

Answer 2

La « bonne » à faire est d'utiliser un algorithme:

#include <algorithm>
#include <functional>

// this is a function object to delete a pointer matching our criteria.
struct entity_deleter
{
    void operator()(Entity*& e) // important to take pointer by reference!
    { 
        if (e->GetXPos() > 1.5f)
        {
            delete e;
            e = NULL;
        }
}

// now, apply entity_deleter to each element, remove the elements that were deleted,
// and erase them from the vector
for_each(Entities.begin(), Entities.end(), entity_deleter());
vector<Entity*>::iterator new_end = remove(Entities.begin(), Entities.end(), static_cast<Entity*>(NULL));
Entities.erase(new_end, Entities.end());

Maintenant, je sais ce que vous pensez. Vous pensez que certaines des autres réponses sont plus courtes. Mais, (1) cette méthode compile généralement à un code plus rapide - essayez la comparer, (2) c'est la « bonne » façon STL, (3) il y a moins de chance pour les erreurs stupides, et (4), il est plus facile à lire une fois que vous pouvez lire le code STL. Il vaut bien apprendre la programmation STL, et je vous suggère de consulter le grand livre de Scott Meyer « STL efficace » qui a des charges de conseils STL sur ce genre de choses.

Un autre point important est que ne pas effacer des éléments jusqu'à la fin de l'opération, les éléments ne doivent pas être bousculés. GMan suggérait d'utiliser une liste pour éviter cela, mais en utilisant cette méthode, l'opération est O (n). le code de Neil ci-dessus, en revanche, est O (n ^ 2), puisque la recherche est O (n) et le retrait est O (n).

Answer 3

if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}

Answer 4

Une fois que vous modifiez le vecteur, tous les itérateurs en cours deviennent invalides. En d'autres termes, vous ne pouvez pas modifier le vecteur pendant que vous itérez à travers elle. Pensez à ce que cela fait à la mémoire et vous verrez pourquoi. Je pense que votre assert est une assertion « itérateur invalide ».

std :: vector :: erase () retourne un itérateur que vous devez utiliser pour remplacer celui que vous utilisez. Voir .

Answer 5

Le principal problème est que la plupart des conteneurs stl itérateurs ne prennent pas en charge l'ajout ou la suppression d'éléments dans le conteneur. Certains annulera tous les itérateurs, certains n'invalider un itérateur qui pointe à un élément qui est supprimé. Jusqu'à ce que vous obtenez une meilleure idée de la façon dont chacun des conteneurs travail, vous devez être prudent de lire la documentation sur ce que vous pouvez et ne pouvez pas le faire à un conteneur.

conteneurs stl ne pas respecter une mise en œuvre particulière, mais un vecteur est généralement mis en œuvre par un tableau sous le capot. Si vous supprimez un élément au début, sont déplacés tous les autres éléments. Si vous aviez un itérateur pointant vers l'un des autres éléments qu'il peut maintenant pointer à l'élément après l'ancien élément. Si vous ajoutez un élément, le tableau peut devoir être redimensionnée, donc un nouveau tableau est fait, les vieux trucs copié, et maintenant votre itérateur pointant vers l'ancienne version du vecteur, ce qui est mauvais.

Pour votre problème, il doit être sûr à itérer le vecteur en arrière et supprimer des éléments que vous allez. Il sera également être un peu plus rapide, puisque vous l'habitude de se déplacer des éléments que vous allez supprimer plus tard.

vector<Entity*> Entities;
/* Fill vector here */
vector<Entity*>::iterator it;
for(it=Entities.end(); it!=Entities.begin(); ){
  --it;
  if(*(*it) > 1.5f){
   delete *it;
   it=Entities.erase(it);
  }
}