31

我有一个向量，它存储指向许多动态实例化的对象的指针，我试图遍历向量并删除某些元素（从向量中删除并销毁对象），但我遇到了麻烦。这是它的样子：

    vector<Entity*> Entities;
    /* Fill vector here */
    vector<Entity*>::iterator it;
    for(it=Entities.begin(); it!=Entities.end(); it++)
        if((*it)->getXPos() > 1.5f)
            Entities.erase(it);

当任何实体对象达到 xPos>1.5 时，程序会因断言错误而崩溃……有人知道我做错了什么吗？

我正在使用 VC++ 2008。

4

5 回答 5

43

您需要小心，因为erase()会使现有的迭代器无效。但是，它将返回一个您可以使用的新的有效迭代器：

for ( it = Entities.begin(); it != Entities.end(); ) {
   if( (*it)->getXPos() > 1.5f ) {
      delete * it;  
      it = Entities.erase(it);
   }
   else {
      ++it;
   }
}
于 2009-06-13T19:40:02.107 回答
11

做到这一点的“正确”方法是使用算法：

#include <algorithm>
#include <functional>

// this is a function object to delete a pointer matching our criteria.
struct entity_deleter
{
    void operator()(Entity*& e) // important to take pointer by reference!
    { 
        if (e->GetXPos() > 1.5f)
        {
            delete e;
            e = NULL;
        }
}

// now, apply entity_deleter to each element, remove the elements that were deleted,
// and erase them from the vector
for_each(Entities.begin(), Entities.end(), entity_deleter());
vector<Entity*>::iterator new_end = remove(Entities.begin(), Entities.end(), static_cast<Entity*>(NULL));
Entities.erase(new_end, Entities.end());

现在我知道你在想什么了。您认为其他一些答案更短。但是，（1）这种方法通常编译成更快的代码——尝试比较它，（2）这是“正确的”STL方式，（3）出现愚蠢错误的机会更少，（4）更容易阅读一旦你可以阅读 STL 代码。学习 STL 编程非常值得，我建议您查看 Scott Meyer 的巨著“Effective STL”，其中包含有关此类内容的大量 STL 技巧。

另一个重要的一点是，通过在操作结束之前不擦除元素，元素不​​需要被打乱。GMan 建议使用列表来避免这种情况，但是使用这种方法，整个操作是 O(n)。相比之下，Neil 上面的代码是 O(n^2)，因为搜索是 O(n)，而删除是 O(n)。

于 2009-06-13T20:03:29.553 回答
2 
if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}
于 2009-06-13T19:34:46.517 回答
0

修改向量后，所有未完成的迭代器都将变为无效。换句话说，您不能在迭代时修改向量。想想这对记忆有什么影响，你就会明白为什么。我怀疑您的断言是“无效的迭代器”断言。

std::vector::erase() 返回一个迭代器，您应该使用它来替换您正在使用的迭代器。见这里。

于 2009-06-13T19:34:36.190 回答
0

主要问题是大多数 stl 容器迭代器不支持向容器添加或删除元素。有些会使所有迭代器无效，有些只会使指向已删除项的迭代器无效。在您对每个容器的工作方式有更好的了解之前，您必须仔细阅读有关您可以对容器做什么和不能做什么的文档。

stl 容器不强制执行特定的实现，但向量通常由引擎盖下的数组实现。如果您在开头删除一个元素，则所有其他项目都将被移动。如果您有一个迭代器指向其他项目之一，它现在可能指向旧元素之后的元素。如果您添加一个项目，则可能需要调整数组的大小，因此创建一个新数组，复制旧的东西，现在您的迭代器指向旧版本的向量，这很糟糕。

对于您的问题，向后迭代向量并删除元素应该是安全的。它也会稍微快一些，因为您不会在稍后要删除的项目周围移动。

vector<Entity*> Entities;
/* Fill vector here */
vector<Entity*>::iterator it;
for(it=Entities.end(); it!=Entities.begin(); ){
  --it;
  if(*(*it) > 1.5f){
   delete *it;
   it=Entities.erase(it);
  }
}
于 2009-06-13T20:04:34.950 回答