Erasing multiple objects from a std::vector?

问题:

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

回答1:

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.

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

回答3:

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.

回答4:

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

回答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).