2

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

这是我的代码

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++;
        }
    }
}

我在第二次迭代中崩溃了。而且我在消息向量迭代器不兼容的情况下崩溃了。

崩溃的原因可能是什么？

4

4 回答 4

8

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

itr = myQueue.erase(itr);
于 2012-05-24T12:51:12.900 回答
2

给定一个迭代器范围[b, e)，其中b是向量范围的开始和结束，在该范围内某处e的迭代器上的擦除操作将使从upto的所有迭代器无效。这就是为什么您在调用时需要非常小心的原因。该成员确实返回了一个新的迭代器，您可以将其用于后续操作，并且您应该使用它：iieeraseerase

 itr = myQueue.erase( itr );

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

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

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

于 2012-05-24T12:53:45.040 回答
2

那是未定义的行为。特别是，一旦你删除了一个迭代器，它就会变得无效，你不能再将它用于任何事情。展开循环的惯用方式如下：

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，所以这是一个两遍算法，如果有大量元素，效率可能会降低。

于 2012-05-24T12:54:29.597 回答
2

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

因此，有一个特定的 C++ 习语可用于非关联序列：erase-remove 习语。

它结合了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适配器，以及许多其他内容。

于 2012-05-24T12:58:49.833 回答