96

文字列をキーとしてデータをマッピングしたいとします。どのコンテナを選ぶべきでしたmapかunordered_map？unordered_mapより多くのメモリを消費するので、メモリが問題ではなく、速度が問題であると仮定しましょう。

unordered_map一般に、O（n）の最悪の場合でO（1）の平均的な複雑さを与えるはずです。どのような場合にO（n）に到達しますか？いつmapよりも時間効率が良くなりunordered_mapますか？nが小さいときに起こりますか？

unordered_mapデフォルトのhaserVsでSTLを使用すると仮定します。地図。文字列がキーです。

毎回個々の要素にアクセスするのではなく、要素を反復処理する場合は、どちらを選択する必要がありmapますか？

4

5 に答える 5

228 
                       | map              | unordered_map
---------------------------------------------------------
element ordering       | strict weak      | n/a 
                       |                  |
common implementation  | balanced tree    | hash table
                       | or red-black tree|  
                       |                  |
search time            | log(n)           | O(1) if there are no hash collisions
                       |                  | Up to O(n) if there are hash collisions 
                       |                  | O(n) when hash is the same for any key
                       |                  |     
Insertion time         | log(n)+rebalance | Same as search
                       |                  | 
Deletion time          | log(n)+rebalance | Same as search
                       |                  | 
needs comparators      | only operator <  | only operator ==
                       |                  |
needs hash function    | no               | yes
                       |                  |
common use case        | when good hash is| In most other cases. 
                       | not possible or  | 
                       | too slow. Or when|
                       | order is required|
于 2012-12-10T11:16:33.087 に答える
72

実際には、メモリに問題がない場合、unordered_map単一要素のアクセスが必要な場合は常に高速です。

最悪のケースは理論的であり、すべての要素を説明する単一のハッシュにバインドされます。これは実際的な関連性はありません。unordered_map同じハッシュに属する少なくともlogN個の要素があるとすぐに、は遅くなります。これも実際的な関連性はありません。いくつかの特別なシナリオでは、より均一な分布を保証する特定のハッシュアルゴリズムを使用できます。特定のパターンを共有しない通常の文字列の場合、付属の汎用ハッシュ関数unordered_mapも同様に優れています。

（イテレータを使用して）ソートされた方法でマップをトラバースする場合は、を使用できませんunordered_map。それどころか、mapそれを可能にするだけでなく、キーの近似に基づいてマップ内の次の要素を提供することもできます（lower_boundおよびupper_boundメソッドを参照）。

于 2012-12-10T11:07:14.263 に答える
8

どのコンテナを選択する必要がありますか、mapまたはunordered_map？unordered_mapはより多くのメモリを消費するので、メモリが問題ではなく、速度が問題であると仮定しましょう。

プロファイルしてから決定します。unordered_map一般的に高速ですが、ケースごとに異なります。

どのような場合にO（n）に到達しますか？

ハッシュが適切でなく、多数の要素が同じビンに割り当てられている場合。

マップがunordered_mapよりも時間効率が良くなるのはいつですか？nが小さいと起こりますか？

おそらくそうではありませんが、本当に気になる場合はプロファイルを作成してください。小さなサイズのコンテナがプログラムのボトルネックになる可能性は非常に低いようです。とにかく、そのvectorような場合には、線形探索を使用した単純な方が高速になる可能性があります。

決定する際に最も重要なことは、順序付けの要件とイテレータの無効化の欠如です。どちらかが必要な場合は、ほとんどを使用する必要がありますmap。それ以外の場合、unordered_map。

于 2012-12-10T11:09:10.937 に答える
7

どのような場合にO（n）に到達しますか？

すべての入力攪拌に対して同じハッシュ値を生成する（つまり、衝突を生成する）ような悪いハッシュ関数がある場合...

どのコンテナを選択する必要がありますか、mapまたはunordered_map？

それは常に要件とデータの種類/量の問題です。

マップがunordered_mapよりも時間効率が良くなるのはいつですか？

それはただ異なる構造です。一般的なユースケースに応じて、そのうちの1つを使用するように選択することをお勧めします（どのような種類のデータとその量を考慮に入れて）

nが小さいときはhppaenですか？

データ量が少ない場合は、すべてが特定のSTL実装に依存します...したがって、単純なベクトル/配列でさえ、連想コンテナよりも高速である場合があります...

于 2012-12-10T11:07:04.730 に答える
0

std::mapバランスの取れたBSTに要素を内部的に格納します。したがって、要素はキーのソートされた順序で格納されます。

std :: unordered_mapは、ハッシュテーブルを使用して要素を格納します。したがって、要素はソートされた順序で保存されません。それらは任意の順序で保存されます。

メモリ使用量 ：

unordered_mapはハッシュテーブルを格納するためのスペースも必要とするため、メモリ使用量はmapと比較してunordered_mapの方が多くなります。

要素を検索するための時間計算量：

std :: mapで要素を検索するための時間計算量はO（log n）です。最悪の場合でも、要素は平衡二分探索木（BST）として内部に格納されるため、O（log n）になります。

一方、std :: unordered_mapでは、検索の最良の場合の時間計算量はO（1）です。一方、ハッシュコード関数が適切でない場合、最悪の場合の複雑さはO（n）になる可能性があります。

于 2020-12-21T13:15:54.163 に答える