La suppression de l'élément de vecteur, alors qu'en C++11 de la gamme "pour" boucle?
J'ai un vecteur de IInventory*, et je suis en parcourant la liste à l'aide de C++11 gamme pour, faire des choses avec chacun d'eux.
Après avoir fait quelques trucs avec un, je souhaiterez peut-être supprimer de la liste et supprimer l'objet. Je sais que je peux appeler delete
sur le pointeur de tout temps à la nettoyer, mais quelle est la bonne façon de le supprimer à partir du vecteur, tandis que dans la gamme for
boucle? Et si je le supprime de la liste de mes boucle d'être invalidée?
std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());
for (IInventory* index : inv)
{
//Do some stuff
//OK, I decided I need to remove this object from 'inv'...
}
- Si vous voulez obtenir la fantaisie, vous pouvez utiliser
std::remove_if
avec un prédicat qui fait les choses" et retourne true si vous souhaitez que l'élément supprimé. - Est-il une raison pourquoi vous ne pouvez pas ajouter un index de compteur et ensuite utiliser quelque chose comme inv.effacer(index)?
- Qui serait encore vis de l'itération.
- et ce serait une performance killer - sur tous les effacer, vous aurez à déplacer tous les éléments après le effacée).
i--
après le supprimer. Ou effectuer une itération vers l'arrière avec l'entier des indices.- Qui a encore O(N^2) complexité.
- J'ai recommandé le passage à
std::list
ci-dessous
Vous devez vous connecter pour publier un commentaire.
Non, vous ne pouvez pas. Gamme à base de
for
est pour quand vous avez besoin pour accéder à chaque élément d'un conteneur une fois.Vous devez utiliser la normale
for
boucle ou l'un de ses cousins si vous avez besoin de modifier le conteneur comme vous allez le long, accéder à un élément plus d'une fois, ou autrement effectuer une itération dans un mode non-linéaire à travers le récipient.Par exemple:
true
, AFAIU, et il semble mieux de cette façon à ne pas mélanger itération logique avec le prédicat.remove_if
est mieux.remove_if
est souvent plus claire. Peut-être que vous pensiez de l'enlèvement de la clé?vector
,deque
). Par conséquent, la suppression de plusieurs éléments est supposé O(N^2).remove_if
, peut être O(N)erase
renvoie un nouveau valide itérateur. il pourrait ne pas être efficace, mais il est garanti pour fonctionner.Chaque fois qu'un élément est supprimé à partir du vecteur, vous devez assumer les itérateurs à ou après la effacées élément ne sont plus valides, parce que chacun des éléments de réussir les "effacés" de l'élément à déplacer.
Une gamme à base de boucle est juste sucre syntaxique pour "normal" de la boucle à l'aide des itérateurs, de sorte que le ci-dessus s'applique.
Cela étant dit, vous pouvez tout simplement:
vector
ne sera jamais réaffecter en raison d'un appel àerase
. La raison pour laquelle les itérateurs sont invalidés est parce que chacun des éléments de réussir les "effacés" de l'élément à déplacer.[&]
serait approprié, pour lui permettre de "faire des trucs" avec des variables locales.remove_if
avec.erase
, sinon rien ne se passe.std::remove_if
est O(n).remove_if
doit faire en interne). Toutefois, si vous avez unvector
de 5 éléments et vous ne.erase()
1 à un moment, il n'y a pas d'impact sur les performances pour l'utilisation des itérateurs vsremove_if
. Si la liste est plus grande, vous devriez vraiment passer àstd::list
où il y a beaucoup de moyen de la liste de suppression.Idéalement, vous ne devriez pas modifier le vecteur lors de l'itération sur elle. Utiliser le erase-remove idiome. Si vous le faites, vous êtes susceptible de rencontrer quelques problèmes. Car, dans un
vector
unerase
invalide tous les itérateurs de début avec l'élément à effacer jusqu'à laend()
vous aurez besoin pour vous assurer que votre itérateurs restent valables à l'aide de:Note, que vous avez besoin de la
b != v.end()
test-est. Si vous essayer de l'optimiser comme suit:vous allez courir dans UB depuis votre
e
est invalidée après la premièreerase
appel.std::remove
, et il est O(N^2) non O(N).Est-il une exigence stricte pour supprimer des éléments, tandis que dans cette boucle? Sinon, vous pouvez définir des pointeurs que vous souhaitez supprimer à NULL et faire un autre passage sur le vecteur de supprimer tous les pointeurs NULL.
désolé pour necroposting et aussi désolé si mon expertise c++ est dans la manière de ma réponse, mais si vous essayez d'itérer sur chaque point et de faire des changements possibles (telles que l'effacement d'un index), essayez d'utiliser un backwords pour la boucle.
lors de l'effacement de l'indice de x, la boucle suivante sera pour l'élément "en face de" la dernière itération. j'espère vraiment que cela a aidé quelqu'un
OK, je suis en retard, mais de toute façon: Désolé, pas correct ce que j'ai lu jusqu'à présent - il est possible, vous avez juste besoin de deux itérateurs:
Seulement la modification de la valeur d'un itérateur, les points à ne pas invalider toute autre itérateur, de sorte que nous pouvons le faire sans avoir à se soucier. En fait,
std::remove_if
(gcc mise en œuvre au moins) fait quelque chose de très similaire (à l'aide d'un classique de la boucle de la...), il suffit de ne pas supprimer n'importe quoi et n'efface pas.Être conscient, cependant, que ce n'est pas thread-safe(!) - cependant, cela s'applique aussi, pour certains, de l'autre des solutions ci-dessus...
erase
(à condition de supprimer plus d'un seul élément, bien sûr)?Je vais montrer l'exemple, l'exemple ci-dessous enlever impair d'éléments de vecteur:
sortie aw ci-dessous:
Gardez à l'esprit, la méthode
erase
sera de retour la prochaine itérateur de l'itérateur.De ici , nous pouvons utiliser une méthode de génération:
Voir ici pour voir comment utiliser
std::remove_if
.https://en.cppreference.com/w/cpp/algorithm/remove
En opposition à ce fils le titre, je voudrais utiliser deux forfaits:
Beaucoup plus élégante solution serait de passer à
std::list
(en supposant que vous n'avez pas besoin d'accès aléatoire rapide).Vous pouvez ensuite les supprimer avec
.remove_if
et C++ foncteur en une seule ligne:Donc ici, je suis en train d'écrire un foncteur qui accepte un argument (le
Widget*
). La valeur de retour est la condition de supprimer unWidget*
à partir de la liste.Je trouve cette syntaxe acceptable. Je ne pense pas que je pourrais jamais utiliser
remove_if
pour std::vecteurs -- il y a tellementinv.begin()
etinv.end()
bruit de là, vous êtes probablement mieux d'utiliser un entier fondé sur l'indice supprimer ou juste un simple vieux régulières itérateur à base de supprimer (comme illustré ci-dessous). Mais vous ne devrait pas vraiment être enlever du milieu d'unstd::vector
beaucoup de toute façon, le fait de passer à unlist
pour ce cas de fréquentes moyen de la liste de suppression est conseillé.Remarque cependant, je n'ai pas de possibilité d'appeler
delete
sur leWidget*
's qui ont été supprimés. Pour ce faire, il devrait ressembler à ceci:Vous pouvez également utiliser un itérateur à base de boucle comme ceci:
Si vous n'aimez pas la longueur de
for( list<Widget*>::iterator iter = widgets.begin() ; ...
, vous pouvez utiliserremove_if
sur unstd::vector
fonctionne, et comment il maintient la complexité à O(N).std::vector
va toujours faites glisser chaque élément après celui que vous avez supprimé un, faire unstd::list
un bien meilleur choix.remove_if
va glisser chaque élément par le nombre d'espaces libérés. Au moment où vous compte pour l'utilisation du cache,remove_if
sur unstd::vector
probablement surpasse la suppression d'unstd::list
. Et préserveO(1)
d'accès aléatoire.std::vector
est encoreO(N)
(mémoire de glissement coût) de toute manière vous la coupez, tandis qu'unstd::list
aO(1)
de suppression pour chaque cas (changement de 2 pointeurs).remove_if
par certains internes de la magie en fait évite déplacer quoi que ce soit jusqu'à ce qu'il a identifié tous, les balises de détresse à être enlevées ont été identifiés et marqués. Intéressant.Je pense que je ferais la suite...
vous ne pouvez pas supprimer l'itérateur au cours de l'itération de boucle, car itérateur comte obtenir des mésappariements et après une itération, vous auriez invalide itérateur.
Solution:
1) prendre la copie de l'original de vecteur
2) itérer l'itérateur à l'aide de cette copie
2) faire quelques trucs et supprimer à partir du vecteur d'origine.
Effacement de l'élément un par un conduit facilement à N^2 performance.
Mieux pour marquer les éléments qui doivent être effacées et les effacer à la fois après la boucle.
Si je peut présumer nullptr dans pas élément valide dans votre vecteur, puis
devrait fonctionner.
Dans le cas où votre "Faire des trucs" n'est pas la modification de certains éléments du vecteur et seulement utilisé pour prendre la décision de le supprimer ou de conserver l'élément, vous pouvez le convertir en lambda (comme il a été suggéré à quelqu'un précédent post) et l'utilisation