std::list reverse iterating & erasing causes crash

Question

I am traversing an std::list using reverse iterators and erasing some elements from the list using their forward iterators that were obtained when inserting them. A sample program is shown below. I read that deleting elements from a list doesn't invalidate other iterators except for the ones referring to element that's deleted. But there's no mention of reverse_iterators and my program is crashing. Can someone please tell if the usage is incorrect?

What the program is doing is adding an element into the list, storing its iterator, reverse iterating the list and deleting the only element in the list using its stored iterator.

The output is pasted below the code sample.

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

OUTPUT

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

What exactly do you want it to do (not this particular case with 1 element, but in general)? — SingerOfTheFall, Jul 05 '12 at 07:24
I'm adding objects, with a create timestamp, into the list for some processing. After processing is done, they get erased and deleted immediately. There's a timeout for the processing and a function continuously checks for timed out objects by reverse iterating through this list for efficiency reasons. — vrk001, Jul 05 '12 at 07:36
If you are sure about normal iterators and unsure about reverse ones, you can as well use the normal one, start from `vec.end()`, process in a cycle like `while(iterator!=vec.begin)`, and in the cycle itself, use `iterator--` instead of `iterator++`. IMO it's easier to understand, but it's up to you. — SingerOfTheFall, Jul 05 '12 at 08:03

score 2 · Accepted Answer · edited May 23 '17 at 12:27

Under VS2010 it will throw an exception here, on the first loop pass:

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

That should give you a general idea what's going on. You see, reverse_iterator is just a wrapper for standard iterator. That said, you should remember that it's got base() member that returns underlying iterator - you don't have to store it elsewhere, like you do in node struct.

Here's a great answer to how reverse_iterator relates to the iterator. In your case, rbegin will be based on begin iterator. If you remove the begin from the list (which you do, since it has only one element), all reverse_iterators based on this iterator will become invalid. Keeping that in mind you could rewrite your loop the following way:

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

Also, the point about not needing to store the iterator but getting it using base() was really good ! :-) — vrk001, Jul 05 '12 at 08:36
Great solution! For readability, reverse_iterator::iterator>(...) can be swapped with std::make_reverse_iterator(...) — buttonsrtoys, Mar 26 '19 at 16:33

score 1 · Answer 2 · answered Jul 05 '12 at 07:27

1

The reverse iterator is (tpyically) not a unique class, but a adapter on a normal iterator - it has a iterator into a list as member and uses it to do its own moving and dereferencing. So when this list iterator gets invalidated, the reverse iterator is invalidated too.

answered Jul 05 '12 at 07:27

C. Stoll

376
1
6

So is my usage incorrect? If so, is there a way to reverse iterate over a list and erase some elements too? – vrk001 Jul 05 '12 at 07:39
You can erase the elements, you can't just erase the element your iterator is currently pointing to (btw, physically the reverse iterator points to the element after the one shown and does some iterator arithmetics to get the current value on dereferencing). – C. Stoll Jul 05 '12 at 07:55

score 0 · Answer 3 · answered Jan 28 '15 at 23:02

i'm writing an answer to note my findings; if you hit this problem try

SingerOfTheFall 's suggested method, it works like a charm, example:

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

back to my findings about this:

when i hit the problem the program hanged, and i've run a valgrind check, it dropped out some strange Invalid reads originated from 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

score -1 · Answer 4 · answered Jul 05 '12 at 07:40

-1

You need store erase return value into iterator. Do following change.

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

answered Jul 05 '12 at 07:40

Sach

659
8
20

list::erase takes only a forward iterator and returns a forward iterator to the next node of the erased node. The returned iterator is not useful to me as I am doing reverse iteration and need a reverse_iterator to the erased node's prev node. – vrk001 Jul 05 '12 at 07:46
check with below answer then... http://stackoverflow.com/questions/1830158/how-to-call-erase-with-a-reverse-iterator – Sach Jul 05 '12 at 07:59
This is a terrible anwser. First of all, this is not what causes problems. Secondly, it's nonsense - why to store iterator of a node that has been removed in that very node? – gwiazdorrr Jul 05 '12 at 08:03

std::list reverse iterating & erasing causes crash

4 Answers4