vs2010 が実際に完全な順序付けを必要とするため、ユーザー定義の必要性が少ないことを知らない場合は、これを参照してください。
回答の1つは、バイナリ検索が可能であると述べましたが、そうは思いません。
ハッシュマップはこの設計からどのように利益を得ますか? このデザインをどのように利用しますか？
ありがとう
ハッシュ関数は均一である必要があり、負荷係数が 1 未満であることが望ましいです。これは、ほとんどの場合、ハッシュ スロットごとに 1 つの要素を意味します。つまり、二分探索は必要ありません。
ハッシュ スロットごとに最大で 1 つの要素はありません。一部のバケットは、複数のキーを保持する必要があります。入力が事前に決定された制限された値のセット (つまり、完全なハッシュ) のみからのものでない限り、ハッシュ関数は、生成できる出力よりも多くの入力を処理する必要があります。衝突があります。これは、これと同じくらい一般的な実装では避けられません。ただし、優れたハッシュ関数は適切に分散されたハッシュを生成する必要があるため、ハッシュ スロットあたりの要素数は低く抑えられます。
明らかに、適切な位置を見つけるため、挿入が遅くなります。
優れたハッシュ関数と非縮退入力 (多くの要素が同じハッシュになるように設計された入力) を想定すると、バケットごとに常に少数のキーしか存在しません。このような二分探索木への挿入はそれほど大きなコストではなく、そのわずかなコストが別の場所で利益をもたらす可能性があります (検索は、リンク リストを使用した実装よりも高速になる場合があります)。また、縮退した入力の場合、ハッシュ マップは二分探索木に縮退します。これは、単純なリンク リストよりもはるかに優れています。
あなたの質問は、実際にはほとんど無関係です.C++は現在、小なりコンパレータではなく述語unordered_mapを使用するなどを提供しているためです。Equal
ただし、 を検討してhash_map<string, ...>ください。明らかに、 の値空間は の値空間stringよりも大きいsize_tため、任意のハッシュ関数に対して、同じハッシュを持つ値が存在するため、同じバケットに配置されます。ハッシュ テーブル内のすべての項目が同じバケットに配置されているという異常な状況では、キー間の順序付けを利用すると、アクセス、挿入、および削除の速度が向上します。
順序付きリスト (またはバイナリ ツリー) の検索は、O(n) ではなく O(log n) であることに注意してください。