1

我有一个

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

2 回答 2

1

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

相反，请使用擦除删除成语。此过程将通过移动后面的项目以替换较早的项目来删除项目（它保持原始顺序）。删除项目后，它将执行一次擦除（这只是列表的末尾）以重新分配一个新的向量，该向量比 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

于 2013-06-09T23:56:50.707 回答
1

如果您被允许重新排序myVector，只需遍历要删除的项目，通过与最后一个元素交换并将其弹出来删除它们。

如果您需要保持顺序，请对deleteIndex容器进行排序并执行一次有序传递以通过向前移动其他元素来移除元素。

于 2013-06-09T23:43:50.110 回答