Effacer des éléments d'un vecteur

101

Je souhaite 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 de se produire une seule fois dans le vecteur. Il peut être présent plusieurs fois et je dois tous les effacer. Mon code est quelque chose comme ceci:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    std::vector<int>::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<int> myNmbers;
    for(int i = 0; i < 2; ++i)
    {
        myNmbers.push_back(i);
        myNmbers.push_back(i);
    }

    erase(myNmbers, 1);

    return 0;
}

Ce code plante évidemment parce que je change la fin du vecteur en l'itérant. Quelle est la meilleure façon d'y parvenir? Existe-t-il un moyen de le faire sans itérer plusieurs fois dans le vecteur ou sans créer une copie supplémentaire du vecteur?

Naveen
la source

Réponses:

167

Utilisez l' idiome Remove / Erase :

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

Ce qui se passe, c'est que removecompacte les éléments qui diffèrent de la valeur à supprimer ( number_in) au début de vectoret renvoie l'itérateur au premier élément après cette plage. eraseSupprime ensuite ces éléments (dont la valeur n'est pas spécifiée).

Motti
la source
2
std::remove()décale les éléments de sorte que les éléments à supprimer soient écrasés. L'algorithme ne change pas la taille du conteneur, et si des néléments sont supprimés, alors il est indéfini quels sont les derniers néléments.
wilhelmtell
20
L'idiome effacer-supprimer est décrit dans le point 32 du livre «Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library» de Scott Meyers.
Alessandro Jacopson
1
@Benjin aucune mise à jour n'est nécessaire, il appellera les destructeurs des objets s'ils existent.
Motti
54
Les «idiomes» de STL comme celui-ci me font utiliser Python pour de petits projets.
Johannes Overmann
1
@LouisDionne qui fait référence à la surcharge à un itérateur, j'utilise la surcharge à deux itérateurs
Motti
53

L'appel d'effacement invalidera les itérateurs, vous pouvez utiliser:

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::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<int> 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<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());

En C ++ 11, vous pouvez utiliser un lambda au lieu d'un foncteur:

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());

En C ++ 17, std :: experimental :: erase et std :: experimental :: erase_if sont également disponibles, en C ++ 20 ils sont (finalement) renommés en std :: erase et std :: erase_if :

std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda

ou:

std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
Dalle
la source
2
Pourquoi utiliser votre propre foncteur alors que vous pouvez utiliser equal_to? :-P sgi.com/tech/stl/equal_to.html
Chris Jester-Young
3
Soit dit en passant, appeler eraseavec removeest le moyen canonique de le faire.
Konrad Rudolph
1
je pense qu'il fait exactement cela. mais il devrait utiliser remove_if s'il utilise son propre foncteur iirc. ou utilisez simplement remove sans le foncteur
Johannes Schaub - litb
3
+1 Le code épelé m'a juste aidé dans un concours de programmation, alors que "utilisez simplement l'idiome supprimer-effacer" ne l'a pas fait.
13
  1. Vous pouvez itérer en utilisant l'accès à l'index,

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

code:

void erase(std::vector<int>& 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 d'invalidation des itérateurs, la complexité est O (n) et le code est très concis et vous n'avez pas besoin d'écrire certaines classes d'assistance, bien que dans certains cas, l'utilisation de classes d'assistance peut bénéficier d'un code plus flexible.

Ce code n'utilise pas de eraseméthode, mais résout votre tâche.

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

#include <algorithm>

void erase(std::vector<int>& v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}
sergtk
la source
4

Selon la raison pour laquelle vous faites cela, utiliser un std :: set peut être une meilleure idée que std :: vector.

Il permet à chaque élément de se produire une seule fois. Si vous l'ajoutez plusieurs fois, il n'y aura de toute façon qu'une seule instance à effacer. Cela rendra l'opération d'effacement triviale. L'opération d'effacement aura également une complexité temporelle plus faible que sur le vecteur, cependant, l'ajout d'éléments est plus lent sur l'ensemble, donc cela pourrait ne pas être un grand avantage.

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 par l'ordre dans lequel les éléments ont été ajoutés.

Laserallan
la source
-1

Pour effacer le 1er élément, vous pouvez utiliser:

vector<int> mV{ 1, 2, 3, 4, 5 }; 
vector<int>::iterator it; 

it = mV.begin(); 
mV.erase(it); 
Amit Vujic
la source
1
Ce n'était pas la question. Votre réponse de 11 ans plus tard ne semble pas pertinente, Amit!
Asteroids With Wings