Manière la plus efficace d'effacer / supprimer plusieurs éléments std :: vector tout en conservant l'ordre d'origine?
j'ai un std::vector<int>
et un deuxième récipient contenant les itérateurs ou d'index (pas de touches, je veux un accès constant à de l'élément) de ce vecteur pour la suppression des fins.
Supposons que j'ai un vecteur de 1000 éléments et que vous souhaitez effacer de 200 d'entre eux. L'ordre de la non-suppression des éléments doit être la même après la suppression des opérations comme avant.
Une chose que j'ai raté dans la première version de ma question: la les valeurs sont uniques. Ils sont les identités.
Comment voudriez-vous faire cela dans un coffre-fort (concernant le tsl règles) et de manière efficace (la décision pour un vecteur est définitive)?
Possibilités ou Méthodes j'ai pensé:
- la erase-remove idiome (http://en.wikipedia.org/wiki/Erase-remove_idiom): à l'origine pour la suppression des éléments qui répondent à une condition (y compris la recherche linéaire) mais je pense qu'avec les gammes de taille 1, cette méthode pourrait être utilisée pour avec déjà donné des itérateurs et un mannequin condition. Question: est de l'ordre d'origine des éléments conservés et est-il plus performant que la dernière méthode?
- en boucle sur les indices et effacer les éléments avec l'utilisation de
vector.erase(vector.begin()+index+offset)
tout en gardant l'index retiré dans un conteneur pour le calcul de l'offset. Ce décalage peut être déterminé pour chaque suppression de l'itération avec l'utilisation d'unstd::lower_bound
n le conteneur des éléments supprimés. Le problème: beaucoup de binary_searches pour obtenir le décalage et beaucoup d'opérations de déplacement à cause de hasard-l'emplacement-la suppression. - Pour le moment, je suis en train de faire les opérations suivantes: tous les itérateurs pour les éléments à supprimer. Les trier dans l'ordre décroissant en fonction de l'emplacement dans le vecteur et d'une boucle pour la suppression définitive avec
vector.erase
. Maintenant, je ne suis pas invalider tout itérateur et il n'y a pas de vecteur de réorganiser les opérations, sauf pour la suppression elle-même. Le problème: beaucoup de tri
Alors, comment voulez-vous remédier à cette situation? Toutes les nouvelles idées? Toutes les recommandations?
Merci pour vos commentaires.
Sascha
Modifier /mettre à Jour /résultats: j'ai mis en place le erase-remove idiomequi a également été mentionné par KennyTM, avec un prédicat basé sur la recherche dans un boost::dynamic_bitset et c'est incroyablement rapide. En outre, j'ai essayé PigBen du mouvement-et-méthode tronquer (également mentionnée par Steve Jessop), qui est également accès à la bitset dans c'est en boucle. Les deux semblent être tout aussi rapide avec mon type de données. J'ai essayé de supprimer 100 de 1000 Éléments (unsigned ints), est-ce à 100 supprime 1M de fois et il n'y avait pas de différence significative. Parce que je pense que la stl, en fonction erase-remove idiome est un peu plus "naturel, je suis le choix de cette méthode (argument a également été mentionné par KennyTM).
source d'informationauteur sascha
Vous devez vous connecter pour publier un commentaire.
Dans
<algorithm>
il y a unremove_if
function qui fait ressortir toutes les valeurs qui ne sont pas enlevées à l'avant du maintien de l'ordre. Cela fonctionne si ces 200 éléments peuvent être purement déterminé par les valeurs, pas d'index.C'est essentiellement le Erase-remove idiome.
remove_if
est garanti à effectuer O(N) comparaisons (et au plus O(N) copyings), ce qui serait plus efficace que le tri en O(N log N)), bien que votre dernière option ne nécessite pas réellement de tri si les indices sont déterminés à partir des valeurs (il suffit de le scanner dans l'inversion de l'orientation lors de la copie).Néanmoins, l'utilisation des
remove_if
(si vous pouvez) est mieux que les 2 autres options que l'application a déjà été écrit pour vous, il y a donc moins de chance d'erreur de logique, et transmet mieux ce (pas comment) de le faire.Comment sur une boucle dans le vecteur, et pour chaque élément doit être supprimé, copiez le prochain élément qui n'a pas besoin d'être enlevé dans cette position. Puis, quand vous arrivez à la fin, de le tronquer.
Première chose est, ne l'appelez pas
erase
fois de plus que vous avez, parce que pour un vecteur, il mélange les éléments vers le bas, donnant à l'ensemble une opération Ω(n*m) le cas le pire moment de l'exécution (n la taille du vecteur, m la taille de la liste des index à supprimer).Je pense que la première chose que je voudrais essayer serait similaire à la votre code actuel:
indexes[0]
éléments, en sautant d'un élément, puis de copierindexes[1] - indexes[0] - 1
éléments, de sauter un élément, et ainsi de suite.swap
le vecteur d'origine avec le nouveau.Vous pourriez être en mesure de faire la troisième étape avec
remove_copy_if
et d'un prédicat qui contient de l'état (le calcul du nombre d'éléments qu'il a copié et dans quelle mesure il est par le biais de la liste triée des indices), mais extrêmement fastidieux et d'obscures raisons, ce n'est pas garanti de fonctionner (algorithme des prédicats avec mutable état sont problématiques, il semble être un consensus que la norme ne garantit pas que la même copie du prédicat est utilisé tout au long de l'algorithme). Donc, je ne conseille pas de l'essayer, mais il peut aider à garder à l'esprit que ce que vous écrivez est essentiellement une version modifiée deremove_copy_if
.Vous pourriez éviter de la deuxième étape, à l'aide d'un
back_inserter
plutôt que presizing le vecteur, bien que vous auriez probablement encore réserver de l'espace à l'avance.[Edit: à bien y penser, pourquoi suis-je copier quoi que ce soit? Plutôt que de mettre en place une modification de la
remove_copy_if
de mettre en œuvre une modification deremove_if
et il suffit de copier à un point antérieur dans le vecteur. Puiserase
/resize
à la fin. Je ne voudrais pas vous soucier de laO(m log m)
sorte de l'index jusqu'à preuve du problème, parce que c'est rare d'être beaucoup plus lent que Ω(m) opération de lire toutes les valeurs à supprimer, et de les stocker dans une sorte de récipient. Puis, à l'aide de ce conteneur dans le prédicatremove_if
peut ou peut ne pas êtreO(1)
. Le tri peut tourner plus vite pour des valeurs plausibles dem
.]Vous pouvez copier tous les éléments d'un vecteur à une liste, à moins que l'indice dans votre deuxième récipient, puis le retour à un vecteur. Même avec un algorithme de passe à partir de la fin du vecteur à l'avant, il y a beaucoup de travail à faire dans les coulisses de votre vecteur.
Faire de votre deuxième récipient d'une carte, donc il garde les indices triés automatiquement pour vous.
edit:
Pour répondre au commentaire
Le coût du maintien d'une carte est le pire des cas le même que le maintien d'une autre structure (liste ou un vecteur) et ensuite faire le tri. Si vous êtes déjà ce que vous pourriez aussi bien le garder comme une carte. Il n'est pas logique de se plaindre de la surcharge d'une carte contre la surcharge de tri d'une liste.
Que pour la performance de mon algorithme suggéré, si m est le nombre d'éléments à supprimer, et n est le nombre total d'éléments, puis il résultats en O(n - m).
Bien sûr, c'est surtout juste humoring votre tentative d'optimisation avec un vecteur.
1 - Vous ne devriez pas être l'aide d'un vecteur si vous voulez faire du random access supprime. Ce n'est pas ce qu'ils sont bons, l'utilisation d'une liste si possible. Et puisque vous semblez être beaucoup plus intéressés dans un ordre relatif plutôt qu'absolu de l'index, je me demande pourquoi un vecteur est nécessaire à tous. Si vous avez donné à l'ensemble du problème, il y a probablement une solution commune pour permettre l'utilisation la plus efficace de la structure de données pour le résoudre.
2 - au Lieu de maintenir une deuxième structure de données, marquer les éléments qui doivent être supprimés directement dans leur conteneur. Un moyen trivial est plutôt à l'aide d'un conteneur< T > utiliser un conteneur< std::pair< T, char > >, et utiliser le char de garder une trace de l'état des éléments.
Si vous n'1 et 2, vous supprimez la copie complètement et obtenir une beaucoup plus efficace de mise en œuvre.
Éléments de ce que l'? Peut-être que je vais prendre votre poste de sérieux, mais si vous avez un vecteur de 1000 éléments, pourquoi ne pas marquer ceux qui ne sont pas plus valable et de rompre avec l'effacement de la première place. Évidemment, je suis en train de faire l'hypothèse ici que les éléments ne demandant pas beaucoup de mémoire.
Je ne apportez ceci parce que vous semblez être concernées par la vitesse. Si les suggestions déjà donné de ne pas faire l'affaire peut-être que cette idée mérite d'être pensée! En substance, d'accélérer les choses en ne faisant pas l'opération de la première place.
Si vous avez un (par exemple, non ordonnée) de l'ensemble des indices que vous voulez effacer, vous pouvez utiliser ceci:
C'est la solution la plus rapide qui est venu à mon esprit. Vous avez besoin C++11cependant. Exemple d'utilisation pour effacer des éléments à l'index 2 et 5:
Avant:
Après:
Edit:
Si vous voulez être plus flexible en ce qui concerne le type de conteneur qui détiennent les indices pour effacer:
Maintenant vous pouvez utiliser n'importe quel type de conteneur à partir de la Les Conteneurs De La Bibliothèque de fournir les indices d'être effacées tant que le
value_type
de ce récipient eststd::size_t
. L'utilisation reste la même.J'ai écrit une fonction, basée sur Benjamin Lindley réponse https://stackoverflow.com/a/4115582/2835054.