std :: list reverse iterating & erasing вызывает сбой

Question

Я просматриваю std :: list, используя обратные итераторы и стираю некоторые элементы из списка, используя их передовые итераторы, которые были получены при их вставке. Пример программы показан ниже. Я читал, что удаление элементов из списка не делает недействительными другие итераторы, кроме тех, которые ссылаются на удаленный элемент. Но об обратном-обращении нет и моя программа рушится. Может кто-нибудь, пожалуйста, сообщите, является ли использование неправильным?

Что делает программа - это добавить элемент в список, сохранить его итератор, отменить итерацию списка и удалить единственный элемент в списке, используя его сохраненный итератор.

Выходной сигнал вставляется под образцом кода.

#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 struct.

Here's a great answer как reverse_iterator относится к iterator. В вашем случае rbegin будет основан на итераторе begin. Если вы удалите begin из списка (что вы делаете, так как оно имеет только один элемент), то все reverse_iterator s на основе этого 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; 
} 

Answer 2

Обратный итератор (tpyically) не единственный класс, а адаптер на обычном итератора - он имеет итератор в список в качестве члена и использует его, чтобы сделать его собственное перемещение и разыменование. Поэтому, когда этот итератор списка становится недействительным, обратный итератор также недействителен.

Answer 3

Вам нужно сохранить возвращаемое значение стирания в итераторе. Сделайте следующее изменение.

(*rj)->iter= l.erase((*rj)->iter); 

Answer 4

Я пишу ответ, чтобы отметить мои выводы; если вы нажмете эту проблему пытаются

SingerOfTheFall «s предложил метод, он работает как шарм, например:

 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) 

я подозреваю, что после удаления последнего элемента rend() не останавливает итератор, а ++ op попадает в петлю