Effacement d’éléments d’un vecteur

Je veux effacer un élément d’un vecteur en utilisant la méthode d’effacement. Mais le problème ici est que l’élément n’est pas garanti pour ne se produire qu’une fois dans le vecteur. Il peut être présent plusieurs fois et je dois les effacer tous. Mon code est quelque chose comme ça:

void erase(std::vector& myNumbers_in, int number_in) { std::vector::iterator iter = myNumbers_in.begin(); std::vector::iterator endIter = myNumbers_in.end(); for(; iter != endIter; ++iter) { if(*iter == number_in) { myNumbers_in.erase(iter); } } } int main(int argc, char* argv[]) { std::vector myNmbers; for(int i = 0; i < 2; ++i) { myNmbers.push_back(i); myNmbers.push_back(i); } erase(myNmbers, 1); return 0; } 

Ce code se bloque évidemment car je change la fin du vecteur en le parcourant. Quelle est la meilleure façon d’y parvenir? Est-ce qu’il y a un moyen de faire cela sans parcourir le vecteur plusieurs fois ou créer une copie supplémentaire du vecteur?

Utilisez l’ idiome supprimer / effacer :

 std::vector& vec = myNumbers; // use shorter name vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end()); 

Ce qui se passe est que remove compacte les éléments qui diffèrent de la valeur à supprimer ( number_in ) au début du vector et renvoie l’iterator au premier élément après cette plage. Ensuite, erase ces éléments (qui n’est pas spécifié).

L’appel à l’effacement invalidera les iterators, vous pouvez utiliser:

 void erase(std::vector& myNumbers_in, int number_in) { std::vector::iterator iter = myNumbers_in.begin(); while (iter != myNumbers_in.end()) { if (*iter == number_in) { iter = myNumbers_in.erase(iter); } else { ++iter; } } } 

Ou vous pouvez utiliser std :: remove_if avec un foncteur et std :: vector :: erase:

 struct Eraser { Eraser(int number_in) : number_in(number_in) {} int number_in; bool operator()(int i) const { return i == number_in; } }; std::vector myNumbers; myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end()); 

Au lieu d’écrire votre propre foncteur dans ce cas, vous pouvez utiliser std :: remove :

 std::vector myNumbers; myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end()); 
  1. Vous pouvez itérer en utilisant l’access à l’index,

  2. Pour éviter la complexité de O (n ^ 2), vous pouvez utiliser deux indices, i – index de test courant, j-index pour stocker l’élément suivant et à la fin du cycle, nouvelle taille du vecteur.

code:

 void erase(std::vector& v, int num) { size_t j = 0; for (size_t i = 0; i < v.size(); ++i) { if (v[i] != num) v[j++] = v[i]; } // trim vector to new size v.resize(j); } 

Dans ce cas, vous n'avez pas à invalider les iterators, la complexité est O (n) et le code est très concis et vous n'avez pas besoin d'écrire certaines classes d'aide, bien que l'utilisation de classes d'assistance puisse bénéficier d'un code plus flexible.

Ce code n'utilise pas la méthode d' erase , mais résout votre tâche.

En utilisant stl pure, vous pouvez le faire de la manière suivante (ceci est similaire à la réponse de Motti):

 #include  void erase(std::vector& v, int num) { vector::iterator it = remove(v.begin(), v.end(), num); v.erase(it, v.end()); } 

Selon la raison pour laquelle vous faites cela, l’utilisation de std :: set pourrait être une meilleure idée que std :: vector.

Cela permet à chaque élément de se produire une seule fois. Si vous l’ajoutez plusieurs fois, il n’y aura qu’une seule instance à effacer de toute façon. Cela rendra l’opération d’effacement sortingviale. L’opération d’effacement aura également une complexité temporelle inférieure à celle du vecteur, cependant, l’ajout d’éléments est plus lent sur l’ensemble, ce qui peut ne pas être très avantageux.

Cela ne fonctionnera bien sûr pas si vous êtes intéressé par le nombre de fois qu’un élément a été ajouté à votre vecteur ou à l’ordre dans lequel les éléments ont été ajoutés.