どちらか一方を選択する必要があるのはいつですか? 適切な STL コンテナーを使用するための推奨事項はありますか?
51402 次
5 に答える
48
hash_setC++ 標準の一部ではない拡張機能です。のルックアップは O(log n) ではなく O(1) である必要があるsetため、ほとんどの状況で高速になります。
コンテナーを反復処理すると、別の違いが見られます。setコンテンツはソートされた順序で配信されhash_setますが、基本的にはランダムになります (Lou Franco に感謝します)。
編集: C++ 標準への C++11 の更新が導入されましunordered_setたhash_set。パフォーマンスは同様であり、標準によって保証されています。名前の「順不同」は、反復すると特定の順序で結果が生成されないことを強調しています。
于 2010-03-25T18:34:28.523 に答える
22
stl::set二分探索木として実装されます。
hashsetハッシュテーブルとして実装されます。
ここでの主な問題は、多くの人stl::setが、O（1）をルックアップしたハッシュテーブルであると考えて使用していることです。これは、そうではなく、持っていません。ルックアップ用のO（log（n））が実際にあります。それ以外に、データ構造をよりよく理解するために、バイナリツリーとハッシュテーブルについて読んでください。
于 2010-03-25T18:42:31.487 に答える
4
もう1つ覚えておくべきことは、hash_setではハッシュ関数を提供する必要があるのに対し、セットには定義が簡単な（ネイティブタイプ用に事前定義された）比較関数（'<'）のみが必要なことです。
于 2010-03-25T18:56:27.967 に答える
3
質問の他の部分にはまだ誰も答えていないと思います。
hash_set または unordered_set を使用する理由は、通常 O(1) ルックアップ時間です。通常は、実装によっては、ハッシュをより大きなハッシュ配列にコピーする必要がある場合や、ハッシュ バケットに数千のエントリが含まれる場合があるためです。
セットを使用する理由は、セットの最大または最小のメンバーが頻繁に必要になる場合です。ハッシュには順序がないため、最小のアイテムをすばやく見つける方法はありません。ツリーには順序があるため、最大または最小は非常に高速です。単純なツリーの場合は O(log n)、両端へのポインターを保持する場合は O(1)。
于 2010-03-25T18:57:43.797 に答える
2
hash_set は、ほとんどが O(1) 操作を持つハッシュ テーブルによって実装されますが、セットは、O(log n) 操作を持つある種のツリー (AVL、赤黒など) によって実装されますが、ソートされた順序で。
編集：木はO（n）であると書いていました。それは完全に間違っています。
于 2010-03-25T18:34:24.017 に答える