c++ - std::list 反向迭代和删除导致崩溃

Question

我正在使用反向迭代器遍历 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

Answer 1

在 VS2010 下，它会在第一次循环传递时在此处抛出异常:

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

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

Here's a great answer reverse_iterator 与 iterator 的关系。在您的情况下，rbegin 将基于 begin 迭代器。如果您从列表中删除 begin(您这样做了，因为它只有一个元素)，所有基于此 iterator 的 reverse_iterator 都将变得无效。牢记这一点，您可以按以下方式重写循环:

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