c++ - 按索引删除一堆元素？

Question

我有一个

vector<int> myVector;

我有一个要删除的 index 列表:

vector<size_t> deleteIndex;

哪种策略删除这些索引最有效？

实际上，一个低效的解决方案是:

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

Answer 1

从一个 vector 中一个一个地删除元素是非常低效的。这是因为对于每次删除，它都必须将所有元素向下复制一个，然后重新分配一个更小的 vector 。

相反，使用 erase-remove idiom .此过程将通过移动较晚的项目来替换较早的项目来删除项目(它保持原始顺序)。删除项目后，它将执行一次删除(这只是列表的末尾)以重新分配一个新的 vector ，该 vector 比 n 项小(其中 n 是删除的项目数)。

示例实现:

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

示例用法:

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

要点:https://gist.github.com/eleven41/5746079
在这里测试:http://ideone.com/0qkDw5