为什么以下代码崩溃？

Question

这只是创建了一些列表元素,然后在开始时通过反向迭代删除元素.它是代码的实际问题的复制品,它在反向遍历它们时删除元素.

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

运行时,它会崩溃:

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

当与valgrind一起运行时,它说:

==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)

编译:

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

拱:

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

你认为这是一个错误,还是我在这里做错了什么？

ps如果你删除case 33(永远不会发生),这将变成一个无限循环而不是崩溃.

Answer 1

好了,所以我下了笔和纸,现在我认为这是做无效的e迭代器.请记住,反向迭代器包含一个指向容器中下一个元素的普通迭代器,它是它的基础迭代器.也就是说,当你有一个rbegin()指向最后一个元素的迭代器时,它的内部迭代器指向过去的元素.同样,当你有一个rend()指向开始前迭代器的迭代器(一个反向迭代器可以指向的虚构元素)时,它的内部迭代器指向第一个元素.

所以你的列表看起来像这样(BTB =开头之前,PTE =结束):

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

虚线表示基本迭代器指向的位置.

现在,在第一次迭代中,您指向最后一个元素(反向第一个)并且count为0,因为您执行后缀增量.因此,当匹配开关时32,您指向列表中的第一个元素(反向33).

好的,现在我们处于这种状态:

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

然后执行以下代码:

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

第一行让我们处于这种状态:

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

然后擦除基本迭代器指向的元素并设置反向迭代器,使其基数现在指向擦除元素后的元素.现在我们有:

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

但是,e现在已经失效了.它的基础不再指向列表的第一个元素,它指向一个无效的元素.

现在,你的循环应该停止,因为i它在最后,但它不会.它将继续另一次,与count作为33,首先进行i++:

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

然后试图抹去基地.噢亲爱的!基础没有指向有效元素,我们遇到了崩溃.事实上,我认为你在迭代太久后就已经遇到了未定义的行为.

解决方案

修复它的方法是rend()每次迭代时获取:

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

或者,e每当您擦除元素时更新:

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

现在,我之前的回答是交换增量和擦除,这有效,但为什么呢？好吧,让我们回到重要的位置(为了清晰起见,我在接下来的几个步骤中添加了另一个元素):

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

所以现在我们首先删除基数,给我们这个:

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

然后我们增加i:

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

然后i == e我们结束循环.因此,虽然这确实有效,但它并不能满足您的需求.它只删除第二个元素.