unordered_mapC++に関する最近の講演で、検索の効率 (償却 O(1)対O(log n) )のため、以前はunordered_map使用していたほとんどのケースでを使用する必要があることに気付きました。ほとんどの場合、マップを使用するときは、キー タイプとしてまたはを使用します。したがって、ハッシュ関数の定義に問題はありません。考えれば考えるほど、単純なタイプのキーの場合にa ではなく aを使用する理由が見つからないことに気付きました。インターフェイスを確認しましたが、コードに影響を与えるような大きな違いは見つかりませんでした。mapintstd::stringstd::mapstd::unordered_map
そこで疑問が生じます。や のような単純な型の場合にstd::mapoverを使用する本当の理由はあるのでしょうか?std::unordered_mapintstd::string
私は厳密にプログラミングの観点から質問しています。これは完全に標準とはみなされておらず、移植時に問題が発生する可能性があることは承知しています。
また、正しい答えの 1 つは、オーバーヘッドが小さいため「データ セットが小さいほど効率的」である可能性があると予想しています(これは本当ですか?)。したがって、キーの量が重要でない (> 1 024) 場合に質問を制限したいと思います。
編集: ああ、明らかなことを忘れていました (GMan さん、ありがとう!) -- はい、もちろんマップは順序付けられています -- 私はそれを知っており、他の理由を探しています。
ベストアンサー1
が要素の順序を維持することを忘れないでくださいmap。それを放棄できない場合は、当然 は使用できませんunordered_map。
他に覚えておくべきことは、unordered_map一般的にメモリを多く使用するということです。mapは、いくつかのハウスキーピング ポインタと、各オブジェクト用のメモリを備えています。 とは対照的に、unordered_mapは大きな配列 (実装によっては、かなり大きくなる場合があります) と、各オブジェクト用の追加メモリを備えています。 メモリを意識する必要がある場合は、 の方mapが適しているはずです。大きな配列がないためです。
したがって、純粋な検索と取得が必要な場合は、これが最適な方法であると言えますunordered_map。ただし、トレードオフは常に存在するため、トレードオフを許容できない場合は、使用できません。
個人的な経験から言うと、メイン エンティティ ルックアップ テーブルunordered_mapの代わりにを使用すると、パフォーマンスが大幅に向上することがわかりました (もちろん、測定済みです) 。map
一方、要素の挿入と削除を繰り返すと、かなり遅くなることがわかりました。比較的静的な要素のコレクションには最適ですが、大量の挿入と削除を実行する場合は、ハッシュ + バケット化が積み重なっていくようです。(注: これは多数の反復処理で実行されました。)