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

破線は、基本反復子が指している場所を示しています。

ここで、最初の反復では、最後の要素 (逆の 1 番目) を指しており、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しません。countas 、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、ループを終了します。したがって、これは機能しますが、あなたが望むことはしません。2 番目の要素のみを削除します。

于 2012-12-22T10:33:26.080 に答える
4

エラーはe無効になることです。直接比較する必要がありますlst.rend()。なぜ無効になるのですか？rend()さて、 ( §23.2.1.9):の定義を見てみましょうreverse_iterator(begin())。

したがって、構築は、実際に削除する最初の要素を指すイテレータにrend()依存します。したがって、その操作はそれを無効にするため、実装方法によってはも無効にする可能性が非常に高く、これは のこのバージョンで明らかに発生します。begin()case 32begin()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 に答える