我基本上遍历所有条目来检查是否有一些条目要被删除,但似乎是错误的:
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建议的那样。 这将抽象出两件事:
编辑:我也应该补充说,在最坏的情况下,被攻破的解决方案是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; }