如何擦除C ++中的vector条目?

我基本上遍历所有条目来检查是否有一些条目要被删除,但似乎是错误的:

std::vector<HANDLE> myvector; for(unsigned int i = 0; i < myvector.size(); i++) { if(...) myvector.erase(myvector.begin()+i); } 

任何人都发现它的问题? 如何正确地做到这一点?

你的问题是算法。 如果两个相邻元素符合删除标准,会发生什么情况? 第一个将被删除,但是因为i在循环的每次迭代之后递增,第二个将被跳过。 这是因为一个向量在内存中是连续的,并且所有被删除元素之后的元素都会向前移动一个索引。

一个丑陋的黑客将是做以下几点:

 std::vector<HANDLE> myvector; for(unsigned int i = 0; i < myvector.size();) { if(...) myvector.erase(myvector.begin()+i); else i++; } 

我不确定是否使用迭代器可以工作,因为调用erase会使迭代器无效到erase元素之后的元素。

优雅的解决方案是使用std :: remove_if ,正如GMan建议的那样。 这将抽象出两件事:

  1. 您的移除条件
  2. 容器元素被移除的过程

编辑:我也应该补充说,在最坏的情况下,被攻破的解决方案是O(n 2 。 GMan的解决方案是O(n) ,假设您的移除条件是O(1) 。 我强烈建议您学习和使用GMAN的解决方案。

你可以使用std::remove_if 。 这将把所有剩下的元素移动到前面,并将一个迭代器返回到新的后面。 你可以删除它:

 struct my_predicate { bool operator()(HANDLE) const { return ...; } }; typedef std::vector<HANDLE> vector_type; vector_type::iterator newEnd = std::remove_if(myvector.begin(), myvector.end(), my_predicate()); myvector.erase(newEnd, myvector.end()); 

这通常在一行上完成。 如果你的编译器支持lambda的(C ++ 0x),你可以这样做:

 vector_type::iterator newEnd = std::remove_if(myvector.begin(), myvector.end(), [](HANDLE){ return ... }); myvector.erase(newEnd, myvector.end()); 

保持谓词本地。


如果你觉得这很丑,那就把它包起来:

 template <typename Vec, typename Pred> Pred erase_if(Vec& pVec, Pred pPred) { pVec.erase(std::remove_if(pVec.begin(), pVec.end(), pPred), pVec.end()); return pPred; } 

然后:

 erase_if(myvector, mypredicate); 

当然,C ++ 0x lambda的工作原理是一样的。

也许另一个hacky解决方案…

 std::vector<HANDLE> myvector; for(unsigned int i = myvector.size()-1; i >=0; --i) { if(...) myvector.erase(myvector.begin()+i); } 

但至少这很简单。

你应该使用矢量迭代器, AND ,在删除时,为迭代器赋值erase()返回的值

 for (it = myvector.begin(); it != myvector.end();) { if (...) { it = myvector.erase(it); continue; } ++it; }