Effacer des éléments d'un vecteur

Question

Je souhaite supprimer un élément d'un vecteur à l'aide de la méthode erase. Mais le problème ici est qu’il n’est pas garanti que l’élément n’apparaisse qu’une fois dans le vecteur. Il peut être présent plusieurs fois et je dois les effacer toutes. Mon code ressemble à 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 se bloque évidemment parce que je change la fin du vecteur en le parcourant. Quel est le meilleur moyen d'y parvenir? C'est à dire. Est-il possible de le faire sans parcourir le vecteur plusieurs fois ni créer une copie de plus du vecteur?

Answer 1

Utilisez le supprimer / effacer l'idiome :

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 remove compacte les éléments qui diffèrent de la valeur à supprimer ( number_in ) au début du vector et renvoie l'itérateur au premier élément après cette plage. Ensuite, erase supprime ces éléments (la valeur de qui n'est pas spécifiée).

Answer 2

L'appel de la fonction 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;
        }
    }

}

Vous pouvez également utiliser std :: remove_if avec un functor et un std :: vecteur :: effacer:

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 pourriez utiliser std :: remove :

std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());

Answer 3

1. Vous pouvez effectuer une itération à l'aide de l'accès à l'index,

2. Pour éviter la complexité de O (n ^ 2) vous pouvez utiliser deux indices, i - index de test actuel, j - index pour stocker l’article suivant et à la fin du cycle une 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, les itérateurs ne sont pas invalidés, la complexité est O (n), le code est très concis et il n'est pas nécessaire d'écrire des classes d'assistance, bien que dans certains cas, l'utilisation de classes d'assistance puisse bénéficier d'un code plus souple. .

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

En utilisant pure stl, vous pouvez procéder de la manière suivante (cela ressemble à 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());
}

Answer 4

En fonction de la raison, utilisez un std :: set pourrait être une meilleure idée que std :: vector.

Cela permet à chaque élément d’apparaître une seule fois. Si vous l'ajoutez plusieurs fois, il ne restera 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 inférieure à celle du vecteur. Cependant, l’ajout d’éléments est plus lent sur l’ensemble, de sorte que cela n’est pas vraiment un avantage.

Bien entendu, cela ne fonctionnera pas si vous souhaitez savoir combien de fois un élément a été ajouté à votre vecteur ou dans quel ordre les éléments ont été ajoutés.