Why does the following code crash?

Question

This simply creates some list elements, then deletes an element at its beginning approaching it via reverse iteration. It's a replica of an actual problem with the code which deletes elements while traversing them in reverse.

#include <list>

int main()
{
  std::list< int > lst;

  for ( int c = 33; c--; )
    lst.push_back( 0 );

  int count = 0;
  for ( std::list< int >::reverse_iterator i = lst.rbegin(), e = lst.rend();
        i != e; )
  {
    switch( count++ )
    {
      case 32:
      case 33:
        ++i;
        i = std::list< int >::reverse_iterator( lst.erase( i.base() ) );
      break;
      default:
        ++i;
    }
  }

  return 0;
}

When run, it crashes with:

*** glibc detected *** ./a.out: double free or corruption (out): 0x00007fff7f98c230 ***

When run with valgrind, it says:

==11113== Invalid free() / delete / delete[] / realloc()
==11113==    at 0x4C279DC: operator delete(void*) (vg_replace_malloc.c:457)
==11113==    by 0x40104D: __gnu_cxx::new_allocator<std::_List_node<int>     >::deallocate(std::_List_node<int>*, unsigned long) (in /tmp/a.out)
==11113==    by 0x400F47: std::_List_base<int, std::allocator<int>   >::_M_put_node(std::_List_node<int>*) (in /tmp/a.out)
==11113==    by 0x400E50: std::list<int, std::allocator<int> >::_M_erase(std::_List_iterator<int>) (in /tmp/a.out)
==11113==    by 0x400BB6: std::list<int, std::allocator<int> >::erase(std::_List_iterator<int>) (in /tmp/a.out)
==11113==    by 0x40095A: main (in /tmp/a.out)

Compiler:

$ g++ --version
g++ (Debian 4.7.1-7) 4.7.1

Arch:

$ uname -a
Linux hostname 3.2.0-2-amd64 #1 SMP Mon Apr 30 05:20:23 UTC 2012 x86_64 GNU/Linux

Do you think it's a bug, or am I doing something wrong here?

p.s. If you remove case 33 (which should never happen), this turns into an infinite loop instead of a crash.

Answer 1

Okay, so I got out a pen and paper and now I think it is to do with invalidated your e iterator. Remember, reverse iterators contain a normal iterator pointing to the next element in the container, which is its base iterator. That is, when you have the rbegin() iterator which points at the last element, its internal iterator points at the past-the-end element. Likewise, when you have the rend() iterator which points to the before-the-beginning iterator (an imaginary element that reverse iterators can point at), its internal iterator points at the first element.

So your list looks something like this (BTB = before the beginning, PTE = past the end):

BTB | 0 | 0 | ... | 0 | 0 | PTE
 ^    :                 ^    :
 |----'                 |----'
 e                      i

The dashed lines show where the base iterators are pointing.

Now, in the first iteration you are pointing at the last element (1st in reverse) and count is 0, because you do postfix increment. So, when the switch is matched for 32, you are pointing at the first element (33rd in reverse) in the list.

Okay, so now we're in this state:

BTB | 0 | 0 | ... | 0 | 0 | PTE
 ^    ^   :
 |----|---'
 e    i

You then execute the following code:

++i;
i = std::list< int >::reverse_iterator( lst.erase( i.base() ) );

The first line puts us in this state:

BTB | 0 | 0 | ... | 0 | 0 | PTE
 ^    :
 |----'
 i
 e

Then you erase the element that the base iterator is pointing at and sets your reverse iterator so that its base is now pointing to the element after the erased element. Now we have:

    BTB | 0 | ... | 0 | 0 | PTE
 ^   ^    :
 |---|----'
 e   i

Now, however, e has been invalidated. It's base doesn't point to the first element of the list any more, it points to an invalid element.

Now, your loop should stop because i is at the end, but it won't. It will continue another time, with count as 33, first doing i++:

    BTB | 0 | ... | 0 | 0 | PTE
 ^   :
 |---'
 i   
 e

And then trying to erase the base. Oh dear! The base isn't pointing at a valid element and we get a crash. In fact, I think you already hit undefined behaviour as soon as you iterated too far.

The solution

The way to fix it is to just get rend() each time you iterate:

for ( std::list< int >::reverse_iterator i = lst.rbegin();
      i != lst.rend(); )

Or alternatively, update e whenever you erase elements:

++i;
i = std::list< int >::reverse_iterator( lst.erase( i.base() ) );
e = lst.rend();

---

Now, my previous answer was to swap the increment and the erasing around, which worked, but why? Well let's go back to the point where it matters (I've added another element in for the sake of clarity over the next few steps):

BTB | 0 | 0 | 0 | ... | 0 | 0 | PTE
 ^    ^   :
 |----|---'
 e    i

So now we erase the base first, giving us this:

BTB | 0 |     0 | ... | 0 | 0 | PTE
 ^    ^       :
 |----|-------'
 e    i

Then we increment i:

BTB | 0 |     0 | ... | 0 | 0 | PTE
 ^    :
 |----'
 i
 e

Then i == e and we end the loop. So while this does work, it doesn't do what you want. It only removes the second element.

Answer 2

The error is that e gets invalidated, you should compare directly to lst.rend(). Why does it get invalidated? Well, let's look at the definition of rend() (§23.2.1.9): reverse_iterator(begin()).

So the construction rend() depends on the begin() iterator which points to the first element, which you'd actually delete with case 32. So because that operation invalidates begin() it very likely it also invalidates rend(), depending on how it's implemented, which clearly happens in this version of libstdc++.

It also makes sense that case 33 makes it crash, this time the iterator will point to something that's not at all in the list anymore. Removing it will of course loop indefinitely because e is invalid and your stop condition won't hit.

Answer 3

When you erase elements, e is invalidated! You have to update e after easing:

i = std::list< int >::reverse_iterator( lst.erase( i.base() ) );
e = lst.rend(); // update e

Answer 4

This shall work -

    #include <list>
    #include <iostream>

    int main()
    {
    std::list< int > list;
    for ( int c = 33; c--; )
    list.push_back( 0 );

    std::list<int>::reverse_iterator it = list.rbegin();
    int count = 0;
    while(  it != list.rend() )
    {

    switch( count++ )
    {
     case 32:
     case 33:
     std::cout<<*it<<std::endl;
     it = std::list< int >::reverse_iterator( list.erase((++it).base()));
     std::cout<<list.size()<<std::endl;
     break;
     default:

    ++it;
    }
   }
  return 0;}