3

我正在使用反向迭代器遍历 std::list 并使用插入它们时获得的正向迭代器从列表中删除一些元素。示例程序如下所示。我读到从列表中删除元素不会使其他迭代器无效，除了那些引用已删除元素的迭代器。但是没有提到 reverse_iterators 并且我的程序正在崩溃。有人可以告诉用法是否不正确吗？

程序所做的是将一个元素添加到列表中，存储其迭代器，反向迭代列表并使用其存储的迭代器删除列表中的唯一元素。

输出粘贴在代码示例下方。

#include <list>
#include <iostream>
using namespace std;

struct node
{
    int data;
    list<node*>::iterator iter;
} a;

int main()
{
    list<node*> l;
    a.data = 1;
    l.push_front( &a );
    a.iter = l.begin();
    list<node*>::reverse_iterator ri = l.rbegin();
    while ( ri != l.rend() )
    {
        cout << (*ri)->data << endl;
        list<node*>::reverse_iterator rj = ri;
        ++ri;
        if ( ri ==  l.rend() )
            cout << "before erase: reached end" << endl;
        l.erase((*rj)->iter);
        if ( ri ==  l.rend() )
            cout << "after erase : reached end" << endl;
        else
            cout << "after erase : Not reached end" << endl;
    }
}

输出

1
before erase: reached end
after erase : Not reached end
610568524
before erase : reached end
Segmentation fault
4

4 回答 4

2

在 VS2010 下，它会在第一次循环传递时在这里抛出异常：

 l.erase((*rj)->iter);
 if ( ri ==  l.rend() ) // exception

这应该让您大致了解发生了什么。你看，reverse_iterator它只是标准迭代器的包装器。也就是说，你应该记住它有base()返回底层迭代器的成员——你不必像在nodestruct 中那样将它存储在其他地方。

这reverse_iterator是与iterator. 在您的情况下，rbegin将基于begin迭代器。如果您begin从列表中删除 （您这样做，因为它只有一个元素），所有reverse_iterator基于此的 siterator都将变为invalid。牢记这一点，您可以通过以下方式重写循环：

while ( ri != l.rend() )
{  
    cout << (*ri)->data << endl;
    list<node*>::reverse_iterator rj = ri;
    ++ri;

    if ( ri ==  l.rend() )
        cout << "before erase: reached end" << endl;

    // the actual underlying iterator has an offset of one
    list<node*>::iterator it = l.erase(--rj.base());
    ri = reverse_iterator<list<node*>::iterator>(it);
    // or just
    // ri = reverse_iterator<list<node*>::iterator>(l.erase(--rj.base()));

    if ( ri ==  l.rend() )
        cout << "after erase : reached end" << endl;
    else
        cout << "after erase : Not reached end" << endl;
}
于 2012-07-05T07:57:14.320 回答
1

反向迭代器（通常）不是一个唯一的类，而是普通迭代器上的一个适配器——它有一个迭代器到一个列表中作为成员，并使用它来进行自己的移动和取消引用。所以当这个列表迭代器失效时，反向迭代器也会失效。

于 2012-07-05T07:27:00.270 回答
0

我正在写一个答案来记录我的发现；如果你遇到这个问题试试

SingerOfTheFall 的建议方法，它就像一个魅力，例如：

        for(auto it=values.end();it!=values.begin();){
            if((*it).second.endPoint)
                break;
            values.erase((*(it--)).first);
        }

回到我对此的发现：

当我遇到程序挂起的问题时，我进行了valgrind检查，它退出了一些奇怪Invalid reads的起源于libstdc++

Invalid read of size 8
    at 0x4EAA633: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.20)
    by 0x402FEC: std::_Rb_tree_iterator<std::pair<int const, GroupControl::Group::Entry> >::operator--() (stl_tree.h:218)

i suspect that after the last element's erase the rend() doesnt stop the iterator, and the ++ op is trapped in a loop

于 2015-01-28T23:02:45.880 回答
-1

您需要将擦除返回值存储到迭代器中。进行以下更改。

(*rj)->iter= l.erase((*rj)->iter);
于 2012-07-05T07:40:17.233 回答