CODEWITHSUNDEEP
c++listcrash
vrk001
vrk001

Reputation: 335

std::list reverse iterating & erasing causes crash

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

Upvotes: 3

Views: 1404

Answers (4)

Zolt&#225;n Haindrich
Zolt&#225;n Haindrich

Reputation: 1808

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

Upvotes: 0

gwiazdorrr
gwiazdorrr

Reputation: 6329

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

Upvotes: 2

Sach
Sach

Reputation: 659

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

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

Upvotes: -1

C. Stoll
C. Stoll

Reputation: 376

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.

Upvotes: 1

Related Questions