关于 std::vector::end() 的问题

Question

我最近修复了以下函数中的一个错误，答案让我感到惊讶。我有以下函数（按照我发现错误之前的方式编写）：

    void Level::getItemsAt(vector<item::Item>& vect, const Point& pt)
    {
        vector<itemPtr>::iterator it; // itemPtr is a typedef for a std::tr1::shared_ptr<item::Item>
        for(it=items.begin(); it!=items.end(); ++it)
        {
            if((*it)->getPosition() == pt)
            {
                item::Item item(**it);
                items.erase(it);
                vect.push_back(item);
            }
        }
    }

该函数查找“items”向量中具有特定位置的所有 Item 对象，将它们从“items”中删除，然后将它们放入“vect”中。随后，名为 putItemsAt 的函数执行相反的操作，并将项目添加到“items”中。第一次通过时，getItemsAt 工作正常。不过，在调用 putItemsAt 后，getItemsAt 中的 for 循环将在“items”末尾运行。 “it”将指向无效的 Item 指针，并且 getPosition() 段错误。凭直觉，我将 it!=items.end() 更改为 it，结果成功了。谁能告诉我为什么？环顾四周表明它可能涉及擦除使迭代器无效，但它仍然没有意义为什么它会第一次工作。

我也很好奇，因为我计划将“项目”从向量更改为列表，因为列表的擦除效率更高。我知道我必须使用 != 作为列表，因为它没有 < 运算符。使用列表我会遇到同样的问题吗？

Answer 1

当您调用擦除（）时，该迭代器将变得无效。由于这是您的循环迭代器，因此在使其无效后调用“++”运算符是未定义的行为。擦除（）返回一个新的有效迭代器，该迭代器指向向量中的下一项。您需要在循环中从该点开始使用该新迭代器，即：

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt) 
{ 
    vector<itemPtr>::iterator it = items.begin();
    while( it != items.end() )
    {
        if( (*it)->getPosition() == pt )
        {
            item::Item item(**it);
            it = items.erase(it);
            vect.push_back(item);
        }
        else
            ++it;
    } 
} 

Answer 2

您正在调用未定义的行为。由于您对该向量调用了erase，因此该向量的所有迭代器都会失效。对于实现来说，做任何它想做的事情是完全有效的。

当您调用 items.erase(it); 时，it 现在无效。为了符合标准，您现在必须假设it已经死亡。

您可以在下一次调用 vect.push_back 时使用该无效迭代器来调用未定义的行为。

您可以使用 it 作为 for 循环的跟踪变量来再次调用未定义的行为。

您可以使用 std::remove_copy_if 使代码有效。

class ItemIsAtPoint : std::unary_function<bool, item::Item>
{
    Point pt;
public:
    ItemIsAtPoint(const Point& inPt) : pt(inPt) {}
    bool operator()(const item::Item* input)
    {
        return input->GetPosition() == pt;
    }
};

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt)
{
    std::size_t oldSize = items.size();
    std::remove_copy_if(items.begin(), items.end(), std::back_inserter(vect), 
        ItemIsAtPoint(pt));
    items.resize(vect.size() - (items.size() - oldSize));
}

如果您使用boost::bind，您可以使它变得更漂亮，但这是可行的。

Answer 3

我将遵循 Remy Lebeau 关于迭代器失效的解释，并补充一点，您可以通过使用 std::list 而不是来使代码有效且渐近更快（线性时间，而不是二次时间）一个 std::vector 。 （std::list 删除只会使已删除的迭代器无效，而插入不会使任何迭代器无效。）

您还可以在调试时通过激活 STL 实现的调试模式来可预测地识别迭代器无效。在 GCC 上，您可以使用编译器标志 -D_GLIBCXX_DEBUG（请参阅那里的一些注意事项）。