Самый эффективный способ стирания / удаления нескольких элементов std :: vector с сохранением исходного порядка?

i have a std::vector and a second container holding iterators or indexes (no keys, i want constant access to the element) to this vector for deletion purposes. Предположим, у меня есть вектор из 1000 элементов, и я хочу стереть 200 из них. Порядок неудаленных элементов должен быть таким же после операций удаления, как и раньше.

Еще одна вещь, которую я упустил в первой версии моего вопроса: значения уникальны . Это идентичности.

Как бы вы сделали это безопасным (в отношении правил stl) и эффективным способом (решение для вектора должно быть окончательным)?

Возможности или Методы я думал о:

• идиоме удаления-удаления (http://en.wikipedia.org/wiki/Erase-remove_idiom): первоначально для удаления элементов, которые удовлетворяют условию (включая линейный поиск ), но я думаю, что с диапазонами размера 1 этот метод можно использовать с уже заданными итераторами и фиктивным условием. Вопрос: сохраняется ли исходный порядок элементов и является ли он более производительным, чем последний метод?
• перебирает индексы и стирает элементы с помощью vector.erase (vector.begin () + index + offset) , сохраняя индексы удаленными в контейнере для вычисления смещения. Это смещение можно определить для каждой итерации удаления с помощью std :: lower_bound в контейнере уже удаленных элементов. Проблема: много binary_searches для получения смещения и много операций перемещения из-за удаления случайного местоположения.
• На данный момент я делаю следующее: получаю все итераторы для элементов, которые нужно удалить . Отсортируйте их в порядке убывания в соответствии с положением в векторе и переберите их в цикле для окончательного удаления с помощью vector.erase . Сейчас я' m не делает недействительным ни один итератор, и нет никаких операций перестановки векторов, кроме самого удаления. Проблема: много сортировки.

Итак, как бы вы с этим справились? Есть новые идеи? Есть рекомендации?

Спасибо за ваш вклад.

Саша

Редактировать / Обновить / Собственные результаты: Я применил идиому удаления-удаления , которая также была упомянута Кенни TM, с предикат , основанный на поиске в boost :: dynamic_bitset , и он безумно быстрый . Кроме того, я попробовал метод перемещения и усечения PigBen (также упомянутый Стивом Джессопом), который также обращается к битовому набору в его цикле while. Оба кажутся одинаково быстрыми с моими данными. Я попытался удалить 100 из 1000 элементов (беззнаковые целые числа), сделал это 100 удалений 1M раз, и не было значительной разницы. Поскольку я думаю, что идиома стирания-удаления на основе stl более "естественна", я выбираю этот метод (аргумент также упоминался Кенни TM).