当我使用vector::erase时它崩溃的原因是什么

Question

我正在尝试对向量进行一些操作。并且仅在某些情况下调用矢量上的擦除。

这是我的代码

while(myQueue.size() != 1)
{
    vector<pair<int,int>>::iterator itr = myQueue.begin();
    while(itr != myQueue.end())
    {
        if(itr->first%2 != 0)
            myQueue.erase(itr);
        else
        {
            itr->second = itr->second/2;
            itr++;
        }
    }
}

我在第二次迭代中崩溃了。而且我遇到了消息向量迭代器不兼容的崩溃.

崩溃的原因可能是什么？

Answer 1

如果

调用erase()则迭代器无效，然后在循环的下一次迭代中访问该迭代器。 std::vector::erase() 返回擦除迭代器之后的下一个迭代器：

itr = myQueue.erase(itr);

Answer 2

给定一个迭代器范围[b, e)其中b是向量的开始，并且e超过向量范围的结束，则在该范围内的某个地方对迭代器i擦除操作将使从i到e的所有迭代器无效。这就是为什么您需要非常小心 打电话给erase .erase成员确实返回一个新的迭代器，您可以将其用于后续操作，并且应该使用它：

 itr = myQueue.erase( itr );

另一种方法是交换i元素和最后一个元素，然后擦除最后一个元素。这更有效，因为需要的元素移动次数更少，超出i。

myQueue.swap( i, myQueue.back() );
myQueue.pop_back();

另外，从外观上看，你为什么要使用vector？如果您需要queue不妨使用 std::queue .

Answer 3

这是未定义的行为。特别是，一旦擦除迭代器，它就会变得无效，您将无法再将其用于任何用途。展开循环的惯用方式是这样的：

for ( auto it = v.begin(); it != v.end(); ) {
   if ( it->first % 2 != 0 )
      it = v.erase(it);
   else {
      it->second /= 2;
      ++it;
   }
}

但话又说回来，不滚动自己的循环而是使用算法会更有效和更惯用：

v.erase( std::remove_if( v.begin(),
                         v.end(),
                         []( std::pair<int,int> const & p ) {
                             return p.first % 2 != 0;
                       }),
         v.end() );
std::transform( v.begin(), v.end(), v.begin(), 
                []( std::pair<int,int> const & p ) {
                    return std::make_pair(p.first, p.second/2);
                } );

这种方法的优点是擦除时元素的副本数量较少（该范围内的每个有效元素都不会被复制一次），并且更难出错（即滥用无效的迭代器......缺点是没有remove_if_and_transform所以这是一个双通道算法，如果有大量元素，效率可能会降低。

Answer 4

在修改循环时进行迭代通常很棘手。

因此，有一个特定的C++习语可用于非关联序列：擦除删除习语。

它将remove_if算法的使用与erase方法的范围重载相结合：

myQueue.erase(
    std::remove_if(myQueue.begin(), myQueue.end(), /* predicate */),
    myQueue.end());

其中谓词表示为典型的函子对象或使用新的 C++11 lambda 语法。

// Functor
struct OddKey {
    bool operator()(std::pair<int, int> const& p) const {
        return p.first % 2 != 0;
    }
};
/* predicate */ = OddKey()
// Lambda
/* predicate */ = [](std::pair<int, int> const& p) { return p.first % 2 != 0; }

lambda 形式更简洁，但可能较少自我记录（无名称），仅在 C++11 中可用。根据您的口味和限制，选择最适合您的一种。

---

可以

提升你编写代码的方式：使用Boost.Range。

typedef std::vector< std::pair<int, int> > PairVector;
void pass(PairVector& pv) {
    auto const filter = [](std::pair<int, int> const& p) {
        return p.first % 2 != 0;
    };
    auto const transformer = [](std::pair<int, int> const& p) {
        return std::make_pair(p.first, p.second / 2);
    };
    pv.erase(
        boost::transform(pv | boost::adaptors::filtered( filter ),
                         std::back_inserter(pv),
                         transformer),
        pv.end()
    );
}

您可以在文档中找到transform和filtered适配器以及许多其他适配器。