Deleting a bunch of elements by their index?

Question

I have a

vector<int> myVector;

And I have a list of index to delete:

vector<size_t> deleteIndex;

Which strategy would be the most efficient to delete those indexes?

Actually one not efficient solution would be to:

//> sort deleteindex
auto deleted= 0;
for(auto i=0;i<deleteIndex.size();i++ {
   myVector.erase(myVector.begin()+deleteIndex[i]-deleted);
   deleted++;
}

Answer 1

Erasing elements from a vector one-by-one is very inefficient. This is because for every erase, it has to copy all elements down by one, then reallocate a smaller-by-one vector.

Instead, use the erase-remove idiom. This process will remove items by moving later items to replace the earlier items (it maintains original order). After the items are removed, it will do a single erase (which is just the end of the list) to reallocate a new vector which is smaller by n items (where n is the number of items removed).

Sample Implementation:

template <class _FwdIt, class _FwdIt2>
_FwdIt remove_by_index(_FwdIt first, 
                       _FwdIt last,
                       _FwdIt2 sortedIndexFirst, 
                       _FwdIt2 sortedIndexLast)
{
  _FwdIt copyFrom = first;
  _FwdIt copyTo = first;
  _FwdIt2 currentIndex = sortedIndexFirst;

  size_t index = 0;
  for (; copyFrom != last; ++copyFrom, ++index)
  {
    if (currentIndex != sortedIndexLast &&
        index == *currentIndex)
    {
      // Should delete this item, so don't increment copyTo
      ++currentIndex;
      print("%d", *copyFrom);
    }
    else
    {
      // Copy the values if we're at different locations
      if (copyFrom != copyTo)
        *copyTo = *copyFrom;
      ++copyTo;
    }
  }
  return copyTo;
}

Sample Usage:

#include <vector>
#include <algorithm>
#include <functional>

int main(int argc, char* argv[])
{
  std::vector<int> myVector;

  for (int i = 0; i < 10; ++i)
    myVector.push_back(i * 10);

  std::vector<size_t> deleteIndex;
  deleteIndex.push_back(3);
  deleteIndex.push_back(6);

  myVector.erase(
    remove_by_index(myVector.begin(), myVector.end(), deleteIndex.begin(), deleteIndex.end()), 
    myVector.end());

  for (std::vector<int>::iterator it = myVector.begin();
       it != myVector.end(); ++it)
  {
    printf("%d ", *it);
  }

  return 0;
}

Gist: https://gist.github.com/eleven41/5746079
Test here: http://ideone.com/0qkDw5

Answer 2

If you are allowed to reorder the myVector, just iterate through the items to delete, removing them by swapping with the last element and popping it off.

If you need to preserve order, the sort the deleteIndex container and do a single ordered pass to remove the element by moving other elements forward.