C++マルチマップイテレータの無効化

Question

私はイテレータがどのように動作するのか把握しようとしています。したがって、問題の実体を示す簡単な例を作成しました。ケース1のコメントを外すと、イテレータがキー1を持つ最初の要素を指し示すことが期待されますが、実際にはキー0に関連するすべての値が出力されます（何も消去されていない）ので、場合によってはイテレータが無効であるためクラッシュすることがあります。ただし、ケース2のコメントを外すと、キー1のすべての値が適切に削除されます。

消去後にmultimapの次に有効なイテレータが何であるかを知る方法はありますか？ （例えばstd::vector.erase(...)リターン1）

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

あなたがキー0を持つ要素で、あなたの例ではitポイントをm.erase(0)を呼び出す問題

の原因 - そうitが無効化されます。 m.erase(1)が動作するのは、最初に呼び出されたときにitがキー1を持つ要素を指していないため、影響を受けません。後の反復では、キーが1の要素は残っていないので、何も削除されず、イテレータは影響を受けません。

ソリューション

multimapは、次の有効なイテレータを返しますerase -methodを持っていません。 1つの代替方法は、削除後にit = m.upper_bound(deleted_key);に電話することです。これは対数ですが、あなたのシナリオでは遅すぎるかもしれません（erase(x)とupper_boundは2つの対数演算になります）。

は

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

これは、1つの線形演算を使用しています。

あなたはこのような何かを行うことができ、あなたの反復子が現在指しているキーを削除したいと仮定すると、（テストしていないそうでない場合は、eraseはもちろん、大丈夫です）すべての残りは一定の時間です。マップが非常に大きく、等価キーを持つアイテムがほとんどない場合、これはおそらくより高速になります。ただし、等しいキーを持つアイテムが多数ある場合は、間隔の終了を検索すると、間隔の終了を検索するときにupper_bound（O(n)の代わりにO(log n)）を使用する方がよいでしょう。 multimapの内容に応じて発生することが原因m.eraseへ

itイテレータの無効化に加えて

Answer 2

まず答え

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

ハム....

第二に答え、再：編集した質問

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

は非常に注意してくださいコンテナ（任意のコンテナ）を反復処理しているときにコンテナを変更しているときは、あなたが依存しているイテレータを無効にするかもしれません。

いわゆる「ノードベースコンテナ」（list、set、mapは...）最も堅牢なコンテナWRTイテレータの無効化されている：彼らは、これらのイテレータはならないための方法はありません（削除された要素にイテレータを無効にします無効にされた）。

この場合、削除しようとしている要素が実際には*itでないことを確認する必要があります。

あなたのループで本当に何をしようとしているのかよくわかりません。

Answer 3

イテレータを消去すると無効になります。代わりに次の要素を覚えておいてください。

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

あなたのコードを見ると、あなたの++が問題を引き起こしていると思います。削除されている可能性がある場所に割り当てています。 ifステートメントとテストの後に、最後に移動します。以下のようなので：

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

（編集後）

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

（既に別の答えで説明）を使用逆参照の問題が常にありますプログラムを実行するたびにif((*it).second == 3)を実行すると、forループの最後の反復で、m.end()イテレータが実行されます。

デバッグビルドで実行してデバッグすることをお勧めします。ほとんどの標準ライブラリの実装では、参照解除のためのアサートが含まれているはずです。end()逆参照。

Answer 6

上記の人の中には、あなたが火事で遊んでいると回答している人がいます。

また、マルチマップが順序付けされたマップであることを忘れていると思いますので、最小のキーから最大のものまで繰り返しています。したがって、最初のケースではキーの一部を印刷した後にキーを削除しますが、2番目のケースではキーを削除するだけです。