[解決済み] mapとunordered_mapのどちらを選択するか？

質問

文字列をキーとしたデータをマッピングしたいとします。 どのようなコンテナを選べばよいのでしょうか。 map それとも unordered_map ? unordered_map はより多くのメモリを消費するので、メモリは問題ではなく、懸念は速度であるとします。

unordered_map は一般に O(1) の平均的な複雑さを与え、最悪の場合は O(n) となるはずです。 どのような場合にO(n)になるのでしょうか？ どのような場合に map よりも時間効率が良くなるのはいつですか？ unordered_map ? nが小さいとそうなるのでしょうか？

STLを使用すると仮定して unordered_map で、デフォルトの haser Vs. map で、string がキーになります。

もし私が毎回個々の要素にアクセスするのではなく、要素に対して反復処理を行うのであれば、どちらかというと map ?

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

実際には、メモリが問題ない場合 unordered_map の方が常に高速です。

最悪のケースは理論的なもので、すべての要素を占める単一のハッシュに束縛されます。これは実用的な関連性ではありません。その unordered_map は、同じハッシュに属する要素が少なくとも対数Nになるとすぐに遅くなります。これも実用的な関連性ではありません。ある特別なシナリオでは、より均一な分布を保証する特定のハッシュ アルゴリズムを使用することができます。特定のパターンを共有しない普通の文字列の場合、一般的なハッシュ関数は unordered_map で提供される一般的なハッシュ関数がちょうどよいでしょう。

イテレータを使って）マップをソートしてたどりたい場合は unordered_map . それどころか map はそれを可能にするだけでなく、キーの近似値に基づいてマップの次の要素を提供することもできます ( lower_bound と upper_bound メソッド)。