9

这只是创建一些列表元素，然后在开始通过反向迭代接近它时删除一个元素。它是代码实际问题的复制品，该代码在反向遍历元素时删除元素。

#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（这永远不会发生），这将变成一个无限循环而不是崩溃。

4

4 回答 4

11

好的，所以我拿出笔和纸，现在我认为这与您的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已经作废了。它的 base 不再指向列表的第一个元素，它指向一个无效元素。

现在，您的循环应该停止，因为i在最后，但它不会。它将继续另一次，首先使用countas ：33i++

    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我们结束循环。因此，尽管这确实有效，但它并不能满足您的要求。它只删除第二个元素。

于 2012-12-22T10:33:26.080 回答
4

错误是e无效，您应该直接比较lst.rend(). 为什么会失效？好吧，让我们看一下rend()( §23.2.1.9) 的定义：reverse_iterator(begin())。

所以构造rend()取决于begin()指向第一个元素的迭代器，你实际上用case 32. 因此，因为该操作使其失效begin()，它很可能也会失效rend()，这取决于它是如何实现的，这显然发生在这个版本的libstdc++.

让它崩溃也是有道理的case 33，这一次迭代器将指向不再在列表中的东西。删除它当然会无限循环，因为e它是无效的并且你的停止条件不会命中。

于 2012-12-22T11:05:40.480 回答
1

当你擦除元素时，e是无效的！您必须e在缓动后更新：

i = std::list< int >::reverse_iterator( lst.erase( i.base() ) );
e = lst.rend(); // update e
于 2012-12-22T10:43:04.177 回答
0

这应该工作 -

    #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;}
于 2012-12-22T12:38:42.030 回答