Erasing multiple objects from a std::vector?

I am offering several methods:

1. A fast method that does not retain the original order of the elements:

Assign the current last element of the vector to the element to erase, then erase the last element. This will avoid big moves and all indexes except the last will remain constant. If you start erasing from the back, all precomputed indexes will be correct.

void quickDelete( int idx )
{
  vec[idx] = vec.back();
  vec.pop_back();
}

I see this essentially is a hand-coded version of the erase-remove idiom pointed out by Klaim ...

2. A slower method that retains the original order of the elements:

Step 1: Mark all vector elements to be deleted, i.e. with a special value. This has O(|indexes to delete|).

Step 2: Erase all marked elements using v.erase( remove (v.begin(), v.end(), special_value), v.end() );. This has O(|vector v|).

The total run time is thus O(|vector v|), assuming the index list is shorter than the vector.

3. Another slower method that retains the original order of the elements:

Use a predicate and remove if as described in https://stackoverflow.com/a/3487742/280314 . To make this efficient and respecting the requirement of not "sorting then linearly erasing with an offset", my idea is to implement the predicate using a hash table and adjust the indexes stored in the hash table as the deletion proceeds on returning true, as Klaim suggested.

Using a predicate and the algorithm remove_if you can achieve what you want : see http://www.cplusplus.com/reference/algorithm/remove_if/

Don't forget to erase the item (see remove-erase idiom).

Your predicate will simply hold the idx of each value to remove and decrease all indexes it keeps each time it returns true.

That said if you can afford just removing each object using the remove-erase idiom, just make your life simple by doing it.

Erase the items backwards. In other words erase the highest index first, then next highest etc. You won't invalidate any previous iterators or indexes so you can just use the obvious approach of multiple erase calls.