Remove elements from a vector at given indices, the order does not matter

Question

The fact that I have vector elements, I don’t care about them . Than I have N indices (each addressing a unique position in a vector) of elements that should be removed from the vector. I want the removal to be as quick as possible.

The best I could come up with was to store indexes in a set (order indices):

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

And than iterating over the set in the reverse order and replacing the index with the deletion over the 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 wondering if there is an even more efficient way to do this, since using the set seems a bit overkill for me, and I would like to avoid sorting into everything.

EDIT1: Suppose I use a 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 click on next?

EDIT2: I should have mentioned that a vector will contain up to 10 elements. However, deletion in my program happens very often (hundreds of thousands of times).

Answer 1

set is a good choice. I assume that using another distributor (such as an arena) will have the greatest impact. Why not use a set instead of a vector of elements to start with?

I see the following relevant options:

• Instead of deleting, create a new vector and copy the saved items, and then swap back.
  This maintains stable performance (as opposed to deletion, which will require sorting or updating indexes).

• Instead of an index vector, use a bools vector of the same length as your data. For a given length of "maximum 10" enough matte mask

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); } 

Answer 2

You can use swap / pop_back to delete an element at a specified index and keep track of which indexes you have moved using a hash table. This linear space and time are among the abstractions.

 std::vector<T> vec = ...; std::vector<unsigned int> idxs; std::unordered_map<unsigned int, unsigned int> map; for(auto index : idxs) { unsigned int trueIndex = index; while (trueIndex >= vec.size()) { trueIndex = map[trueIndex]; } // element at index 'vec.size()-1' is being moved to index 'index' map[vec.size()-1] = index; swap(vec[trueIndex], vec[vec.size()-1]); vec.pop_back(); }