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'un std::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