L'effacement de plusieurs objets à partir d'un std::vector?
Voici mon problème, disons que j'ai un std::vector avec ints.
disons qu'il a 50,90,40,90,80,60,80.
Je sais que j'ai besoin de supprimer les deuxième, cinquième et troisième éléments. Je n'ai pas forcément toujours connaître l'ordre des éléments à supprimer, ni combien. La question est par l'effacement d'un élément, ce qui change l'index de l'autre des éléments. Donc, comment pourrais-je effacer ces et de compenser l'indice de changement. (le tri ensuite linéairement effacer avec un décalage n'est pas une option)
Grâce
"le tri ensuite linéairement effacer avec un décalage n'est pas une option": Pourquoi?
OriginalL'auteur jmasterx | 2010-08-15
Vous devez vous connecter pour publier un commentaire.
Je vous propose plusieurs méthodes:
1. Une méthode rapide qui ne conserve pas l'ordre original des éléments:
Affecter l'actuel dernier élément du vecteur à l'élément à supprimer, puis effacer le dernier élément. Cela permettra d'éviter les grands mouvements et tous les indices sauf le dernier reste constant. Si vous commencer l'effacement de l'arrière, tous les précalculées index sera correct.
Je vois c'est essentiellement une main-version codée de l'effacement de supprimer l'idiome souligné par Klaim ...
2. Une méthode plus lente que conserve l'original de l'ordre des éléments:
Étape 1: Marquer tous les éléments du vecteur d'être supprimé, c'est à dire avec une valeur particulière. Cela a O(|index| supprimer).
Étape 2: suppression de tous les éléments marqués à l'aide de
v.erase( remove (v.begin(), v.end(), special_value), v.end() );
. Cela a O(|vecteur v|).Le temps d'exécution est donc O(|vecteur v|), en supposant que la liste d'index est plus court que le vecteur.
3. Une autre méthode plus lente que conserve l'original de l'ordre des éléments:
Utilisation d'un prédicat et d'enlever, comme décrit dans https://stackoverflow.com/a/3487742/280314 . Pour faire de ce efficace et respectant l'exigence de
pas de "tri ensuite linéairement effacer avec un décalage", mon idée est de mettre en œuvre le prédicat à l'aide d'une table de hachage et d'ajuster les indices stockées dans la table de hachage, comme la suppression d'un produit sur le retour de vrai, comme Klaim a suggéré.
pop_back
encore fait la bonne chose.L'ordre des indices n'est pas connue d'après l'OP
Cela permettra de réorganiser le vecteur, ce qui pourrait ne pas être ce que vous voulez.
HEIN? Dire qu'étant donné un vecteur de 10 articles, et je veux supprimer la fente 5: je vais maintenant Céder la fente 5 avec la valeur de la fente 10, et de supprimer la fente de 10? Comment est-ce censé être la bonne réponse? Il n'est pas.
Johnson: c'est la bonne réponse si l'ordre des éléments n'a pas d'importance. Si elle n'est pas anodin, alors vous avez besoin de plus de travail pour conserver l'ordre.
OriginalL'auteur Peter G.
À l'aide d'un prédicat et de l'algorithme remove_if vous pouvez obtenir ce que vous voulez : voir http://www.cplusplus.com/reference/algorithm/remove_if/
N'oubliez pas d'effacer l'élément (voir supprimer-pour supprimer l'idiome).
Votre prédicat tiendront simplement idx de chaque valeur à supprimer et diminuer tous les indices qu'il conserve à chaque fois qu'il retourne vrai.
Cela dit si vous pouvez vous permettre de simplement enlever de chaque objet à l'aide de la supprimer-pour supprimer l'idiome, juste vous rendre la vie simple en le faisant.
OriginalL'auteur Klaim
Effacer les éléments en arrière. En d'autres termes effacer l'indice le plus élevé en premier, puis ensuite plus etc. Vous n'aurez pas d'invalider toute précédente itérateurs ou des index de sorte que vous pouvez simplement utiliser l'approche évidente de plusieurs effacer les appels.
sauf si il y a une bonne raison de rejeter arbitrairement l'une des meilleures solutions, alors il est certainement une option. Pourquoi ne pouvez-vous pas trier les indices?
OriginalL'auteur Mark B
Je voudrais déplacer les éléments qui vous ne pas souhaitez effacer un vecteur temporaire, puis de remplacer le vecteur d'origine avec ce.
OriginalL'auteur Andreas Brinck
Serait-ce de travailler:
C'est un O(n) opérations, peu importe la façon dont beaucoup d'éléments que vous supprimez. Vous pourriez obtenir une efficacité par la réorganisation du vecteur en ligne (mais je pense que de cette façon c'est plus lisible).
OriginalL'auteur Niki