139

これでstd実際のハッシュマップが作成されましたが、実際に存在するシステムで古きunordered_map良きものを使用したいのはなぜですか（またはいつ） ？すぐには見えない明らかな状況はありますか？mapunordered_map

4

5 に答える 5

116

すでに述べたようmapに、ソートされた方法で要素を反復処理することはできますが、できunordered_mapません。これは、コレクション（名簿など）の表示など、多くの状況で非常に重要です。これは、次のような他の間接的な方法でも現れます。（1）によって返されたイテレータから反復を開始するfind()、または（2）のようなメンバー関数の存在lower_bound()。

また、最悪の場合の 検索の複雑さにも多少の違いがあると思います。

  • の場合map、O（lg N）です。

  • の場合unordered_map、それはO（N）です[これは、ハッシュ関数が適切でなく、ハッシュの衝突が多すぎる場合に発生する可能性があります。]

最悪の場合の 削除の複雑さにも同じことが当てはまります。

于 2010-10-10T23:59:56.070 に答える
91

上記の回答に加えて、unordered_map一定の速度（ ）であるからといって、 （の順序）O(1)よりも速いという意味ではないことにも注意してください。2 32（または2 64 ）によって制限されるため、定数は特により大きくなる可能性があります。maplog(N)log(N)N

したがって、他の回答（map順序の維持とハッシュ関数が難しい場合があります）に加えて、mapよりパフォーマンスが高い可能性があります。

たとえば、私がブログ投稿のために実行したプログラムでは、VS10の方std::unordered_mapが遅いことがわかりましたstd::map（ただしboost::unordered_map、両方よりも高速でした）。

パフォーマンスグラフ

3番目から5番目の小節に注意してください。

于 2010-10-11T07:22:03.130 に答える
28

これは、CppCon2014の講義でのGoogleのChandlerCarruthによるものです。

std::map（多くの人が考えているように）パフォーマンス指向の作業には役立ちません。O（1）償却アクセスが必要な場合は、適切な連想配列を使用します（または、1つがない場合std::unorderded_map）。ソートされたシーケンシャルアクセスが必要な場合は、ベクトルに基づいたものを使用してください。

また、std::mapバランスの取れたツリーです。そして、あなたはそれをトラバースするか、信じられないほど頻繁にバランスを取り直す必要があります。これらはそれぞれキャッシュキラー操作とキャッシュ黙示録操作です...だから、NOと言ってstd::mapください。

効率的なハッシュマップの実装に関するこのSOの質問に興味があるかもしれません。

（PS-std::unordered_mapリンクリストをバケットとして使用するため、キャッシュに適していません。）

于 2015-05-10T16:05:36.380 に答える
22

std::mapマップ内のアイテムをソートされた順序で反復処理するために必要なものを使用することは明らかだと思います。

ハッシュ関数（一般的に非常に直感的ではない）の代わりに、比較演算子（直感的）を記述したい場合にも使用できます。

于 2010-10-10T23:32:06.463 に答える
11

非常に大きなキー、おそらく大きな文字列があるとします。大きな文字列のハッシュ値を作成するには、文字列全体を最初から最後まで調べる必要があります。キーの長さまで少なくとも線形の時間がかかります。ただし、キーの演算子を使用してバイナリツリーのみを検索する>場合、最初の不一致が見つかったときに各文字列比較が返される可能性があります。これは通常、大きな文字列の場合は非常に早いです。

この推論は、とのfind関数に適用できます。キーの性質が、（の場合）バイナリ検索を使用して要素の場所を見つけるのにかかる時間よりも（の場合）ハッシュの生成に時間がかかるようなものである場合、キーの検索はより高速であるはずです。で。これが当てはまるシナリオを考えるのは非常に簡単ですが、実際には非常にまれであると私は信じています。std::unordered_mapstd::mapstd::unordered_mapstd::mapstd::map

于 2016-08-19T20:22:45.860 に答える