Remove elements from vector on given indexes, order does not matter

Question

What I have is a vector of elements, I do not care about the order of them. Than I have N indexes (each addressing unique position in the vector) of elements to be removed from the vector. I want the removal be as fast as possible.

Best I could come up with was to store indexes in set (order indexes):

std::set<unsigned int> idxs;
for (int i=0; i<N; ++i)
    idxs.insert(some_index);

And than iterating over the set in reversed order and replacing index to remove by last element of the vector.

std::set<unsigned int>::reverse_iterator rit;
for (rit = idxs.rbegin(); rit != idxs.rend(); ++rit) {
    vec[*rit].swap(vec[vec.size() - 1]);
    vec.resize(vec.size() - 1);
}

However I was thinking whether there is some more efficient way of doing this since the usage of set seems a bit overkill to me and I would love to avoid sorting at all.

EDIT1: Let us assume I use vector and sort it afterwards.

std::vector<unsigned int> idxs;
for (int i=0; i<N; ++i)
    idxs.push_back(some_index);
std::sort(idxs.begin(), idxs.end());

Can I push it any further?

EDIT2: I should have mentioned that the vector will have up to 10 elements. However the removal in my program occurs very often (hundreds of thousands times).

Answer 1

set is a good choice. I'd guess using another allocator (e.g. arena)would have the biggest impact. Why not use a set instead of a vector of elements to begin with?

I see the following relevant variations:

• Instead of remove, create a new vector and copy preserved elements, then swap back.
  This keeps your indices stable (unlike removal, which would require sorting or updating the indices).

• Instead of a vector of indices, use a vector of bools of the same length as your data. With the length of "maximum 10" given, a bit mask seems sufficient

So, roughly:

struct Index 
{
   DWORD removeMask = 0;  // or use bit vector for larger N
   void TagForRemove(int idx) { removeMask |= (1<<idx); }
   boll DoRemove(int idx) const { return (removeMask & (1<<idx)) != 0; }
}

// create new vector, or remove, as you like
void ApplyRemoveIndex(vector<T> & v, Index remove)
{
   vector<T> copy;
   copy.reserve(v.size());
   for (i=0..v.size())
     if (!remove.DoRemove(i))
       copy.push_back(v[i]);
   copy.swap(v);
}