C++でsetとunordered_setの違いは何ですか？

Question

は、アクセサ/ミューテータ Differences between HashMap and Hashtable?

を同期化したのおかげで、ハッシュテーブルの異なる実装を持つJava、話して以来、そう違いは何で似ているこの良い質問、出くわしたけど全然同じC++ではsetとunordered_setの実装ですか？ この質問は、他のC++コンテナのvs unordered_mapなどへのマッピングに拡張できます。ここで

がを設定

私の最初の評価である：標準のdoesntが明示的にツリーとして実装することを要求しますが、検索/挿入のためにその業務を尋ね時間複雑度の制約は、それはいつものように実装されることを意味します木。 通常、（GCC 4.8に見られるような）RBツリーとして、高さのバランスがとられています。 それらが高バランスであるため、それらは（検索のための予測可能な時間複雑度を有する）

長所：コンパクト（比較して、他のDSと比較して）

コン：アクセス時間複雑度はO（LG n）が

あります

unordered_set：標準ではツリーとして実装するよう明示的に要求していますが、検索/挿入の操作を要求する時間複雑度の制約は、常にハッシュテーブルとして実装されることを意味します。

長所：ツリー-DS

短所と比較して、スレッドセーフするための基本的なプリミティブを変換する（約束は検索のためのO（1）償却）

簡単

1. の高速化：
   1. （1）Therotical最悪の場合はO（n）の
   であるOであることを保証しませ見上げて0
   2. 木ほどコンパクトではありません。 （実用的な負荷係数は決して1ではありません）

   注：ハッシュテーブルのO（1）は、衝突がないことを前提としています。負荷係数が0.5であっても、すべての2番目の可変挿入が衝突につながります。 ハッシュテーブルの負荷係数は、ハッシュテーブル内の要素にアクセスするために必要な操作の数に反比例することが分かります。より多くは、＃オペレーションを減らし、より疎なハッシュテーブルを作成します。記憶された要素がポインタに匹敵するサイズである場合、オーバヘッドはかなり重要である。

   編集：ほとんどの質問には十分な答えが含まれているので、私は に質問を変更しています。「マップ/設定の違いが分からないのですか？

Answer 1

私はあなたが、一般的に、あなた自身の質問に答えたと思う、しかし、この：

ないよう木のようにコンパクト。 （実用的な目的のために負荷率は決して1ではない）

は必ずしも真ではない。タイプTのツリーの各ノード（赤黒のツリーであると仮定します）は、少なくとも2 * pointer_size + sizeof(T) + sizeof(bool)に等しいスペースを使用します。これは、ツリーに各ツリーノードのparentポインタが含まれているかどうかによって、3 * pointer sizeになる場合があります。

これをハッシュマップと比較してください：あなたが言ったように、load factor < 1という事実のために、各ハッシュマップに無駄な配列スペースがあります。しかし、ハッシュマップが連鎖のために単独でリンクされたリストを使用すると仮定すると、挿入される各要素はsizeof(T) + pointer sizeになります。

この分析では、配置によって使用される余分なスペースに起因するオーバーヘッドは無視されることに注意してください。

小さいサイズ（したがって、任意の基本タイプ）を持つ任意の要素Tの場合、ポインタのサイズおよびその他のオーバーヘッドが支配的です。 > 0.5の負荷係数（たとえば）の場合、std::unordered_setは実際には相当するメモリより少ないメモリを使用する可能性があります（std::set）。

もう1つの大きな欠点は、std::setを反復すると、指定された比較関数に基づいて最小値から最大値への順序が保証され、std::unordered_setを反復すると値が「ランダム」の順序で返されるという事実です。

Answer 2

もう1つの違いは（パフォーマンス関連ではありませんが）、set挿入はイテレータを無効にしませんが、unordered_set挿入は再ハッシュをトリガする場合に挿入できます。実際のところ、実際の要素への参照は有効なので、これはかなり軽度の問題です。

Answer 3

ゆうしは、空間効率などの点について十分に取り組んでいます。私がコメントする質問のちょっと他の部分...

ハッシュテーブルのO（1）は、衝突がないことを前提としています。

これは正しくありません。 O（1）が意味することは、最初のルックアップの試みが常に成功するということではなく、値の数が増えるにつれて増加するものではなく、平均して一定の試行回数が必要であるということです。たとえば、unordered_setまたは... _mapの場合、max_load_factorはデフォルトで1.0になり、負荷係数が良好なハッシュ関数を使用して負荷係数に近づくと、の平均値のいずれかのバケットにハッシュする要素数は関係なく約2になります表にある値の数

0.5の負荷係数でも、2回目の可変挿入がすべて衝突につながります。

真実ですが、直感的に思えるほど致命的ではありません。1.0の負荷係数での平均チェーン長は2であり、悪くありません。

ハッシュテーブルの負荷係数が逆それに 要素にアクセスするために必要な操作の数に比例 であることが観察されました。より多くは、＃オペレーションを減らし、より疎なハッシュテーブルを作成します。

確かに相関があります（逆ではありません）。