23

反復によって要素を削除する std::unordered_map があります。

auto itr = myMap.begin();
while (itr != myMap.end()) {
    if (/* removal condition */) {
        itr = myMap.erase(itr);
    } else {
        ++itr;
    }
}

削除する必要があるすべての要素を削除し終わるまで、マップが高価な操作を実行するのを防ぎたいと思います。私は正当な懸念を持っていますか？内部ストレージの仕組みを誤解していますか?

4

3 に答える 3

3

私が知る限り、std::unordered_map再ハッシュが許可されていerase(itr)ます:

C++11 表 103 -- 順序付けられていない連想コンテナーの要件

a.erase(q)

が指す要素を消去しqます。戻り値はq 消去直前のイテレータです。

平均的なケース O(1)、最悪のケース O(a.size())

したがって、あなたには正当な懸念があるように思われます。それに対処するために、いくつかの手段を提案できます。

  1. 仮定の問題ではなく、実際の問題であることを確認してください。アプリケーションのプロファイリング、C++ ライブラリのソース コードの確認などを行います。
  2. 実際の問題である場合は、別のコンテナーまたは別のアルゴリズムの使用を検討してください。
  3. 各要素に関連付けられたブール値フラグを使用して削除する要素を単純にマークし、削除された要素を時々スイープしてコストを償却することを検討してください。
  4. コメントで @amit が提案しているように、負荷係数を試してみることを検討してください。コンテナーがO(a.size())要素を消去するのに時間がかかる場合でも、別の負荷係数がアプリケーションの実際のパフォーマンスに影響を与える可能性があります。
于 2012-12-05T19:24:22.867 に答える
2

動作するかどうかはわかりませんが、ドキュメントに確認はありませんが、unordered_mapが従来のハッシュテーブルのデータ構造に従って再ハッシュされている場合は、max_load_factorを非常に高い値に設定して、にリセットすることができます。完了したら通常（再ハッシュがトリガーされます）（または、削除される要素の数を予測できる場合は予測値になります）。

従来のハッシュテーブルに関しては、サイズが。よりも小さい場合にテーブルを減らすときの再ハッシュが発生するため、これは機能するはず1/max_load_factorです。

（C ++の場合はわかりませんが、実装が非常に簡単なので、試してみる価値があると思います）。

于 2012-12-05T19:35:46.943 に答える