[解決済み] 些細なキーの場合、unordered_mapよりもmapを使用する利点はありますか？

質問

最近の話題は unordered_map を使うべきであると気づかされました。 unordered_map を使用していたほとんどのケースで map 以前は、ルックアップの効率性から、( 償却済みO(1) 対して O(log n) ). 私がマップを使う場合、ほとんどの場合、どちらか一方を使います。 int または std::string をキータイプにすることで、ハッシュ関数の定義に問題はない。しかし、考えれば考えるほど、このような「ハッシュ関数」を使う理由が見つからない。 std::map の上に std::unordered_map インターフェイスを見てみましたが、私のコードに影響を与えるような大きな違いは見つかりませんでした。

そこで質問です。 std::map オーバー std::unordered_map のような単純な型の場合 int と std::string ?

私は厳密にはプログラミングの観点から質問しているのですが、完全に標準とみなされているわけではなく、移植の際に問題が生じる可能性があることは承知しています。

また、正解の1つは、以下のようなものかもしれないと予想しています。 より小さなデータセットではより効率的です。 というのは、オーバーヘッドが小さいからです（本当でしょうか）。ですから、質問は、キーの量が自明でない場合（>1024）に限定したいと思います。

編集 duh, I forgot the obvious (thanks GMan!) -- yes, maps are ordered of course -- I know that, and am looking for other reasons.

どのように解決するのですか？

忘れちゃいけないのが map は、その要素の順序を保ちます。それを放棄できないのであれば、明らかに unordered_map .

他に気をつけるべきことは unordered_map は一般に、より多くのメモリを使用します。 map は、いくつかのハウスキーピングポインタと、各オブジェクトのためのメモリを持っているだけです。反対に unordered_map は大きな配列（実装によってはかなり大きくなる）を持ち、さらに各オブジェクトのためのメモリが必要です。もし、メモリを意識する必要があるのなら map は、大きな配列がないため、より良いことが証明されるでしょう。

ですから、純粋な検索が必要な場合は、私は unordered_map がいいんじゃないでしょうか。しかし、常にトレードオフがあり、その余裕がないのであれば、使うことはできません。

個人的な経験ではありますが unordered_map の代わりに map を主エンティティルックアップテーブルで使用することができます。

一方で、要素の挿入と削除を繰り返すと、かなり遅くなることがわかりました。比較的静的な要素のコレクションには最適ですが、大量の挿入と削除を行う場合は、ハッシュ化とバケット化が加算されるようです。(注、これは何度も繰り返した場合です)。