Erasing multiple objects from a std::vector?

Question

Here is my issue, lets say I have a std::vector with ints in it.

let's say it has 50,90,40,90,80,60,80.

I know I need to remove the second, fifth and third elements. I don't necessarily always know the order of elements to remove, nor how many. The issue is by erasing an element, this changes the index of the other elements. Therefore, how could I erase these and compensate for the index change. (sorting then linearly erasing with an offset is not an option)

Thanks

Answer 1

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 ...

Answer 2

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.

Answer 3

I would move the elements which you don't want to erase to a temporary vector and then replace the original vector with this.

Answer 4

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.

Answer 5

Would this work:

void DeleteAll(vector<int>& data, const vector<int>& deleteIndices)
{
    vector<bool> markedElements(data.size(), false);
    vector<int> tempBuffer;
    tempBuffer.reserve(data.size()-deleteIndices.size());

    for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++)
        markedElements[*itDel] = true;

    for (size_t i=0; i<data.size(); i++)
    {
        if (!markedElements[i])
            tempBuffer.push_back(data[i]);
    }
    data = tempBuffer;
}

It's an O(n) operation, no matter how many elements you delete. You could gain some efficiency by reordering the vector inline (but I think this way it's more readable).