セットに基づくデータ構造とは何か

Question

C++では、マップは黒赤のツリーに基づいているため、挿入/削除のコストはO（logn）になり、hash_mapはハッシュに基づいています。

しかし、私はどのデータ構造が基づいて設定されているのか迷っていますか？

マップはソートされているので、黒赤色のツリーにも基づいて設定されていますか？

そのキーと値がそのツリーにどのように格納されていますか？

もしそうなら、unorder_setのデータ構造は何ですか？ありがとう！

Answer 1

保証はありません。標準で要求されているのは操作のコストだけなので、実装者は自由に任意のデータ構造を使用できます。通常、std::setとstd::mapはバランスのとれたバイナリツリーです。

また、std::unordered_setおよびstd::unordered_mapはハッシュテーブルです。これは実際には標準によって保証されていると私は信じています。なぜならあなたは手動でハッシュ関数を指定することが許されているからです。

Answer 2

setとmapのタイプは、バランスのとれたバイナリ検索ツリーの時間複雑度に時間複雑性を基づいたC++仕様の時間複雑さの要件に準拠していれば、かなり実装することができます。赤色/黒色の樹木はmapとsetで共通ですが、唯一の選択肢ではありません。 AVLツリー、Bツリー、AAツリーなどで実装することができます。

Answer 3

std::set<...>とstd::map<...>とそれらの "マルチ"バージョンはノードベースであり、最悪の場合はO(ln n)の複雑さを持っています。これは、バランスのとれたツリーが使用されることを意味します。複雑さに加えて、ツリーが突然変異したときには、ポインタもイテレータも無効になりません（もちろん、ポインタやイテレータはerase()オブジェクトになります）。

Bツリーには悲しいことに、イテレータの無効化プロパティが正しくありません（マップには、std::pair<Key, Value>を使用して強制的に表示されるため、キーを重複して格納する必要があります）。実際には、赤色/黒色の樹木が最も効果的であるように思われるが、他の可能なバランシング戦略、例えばAVLツリーがある。スキップリストにも必要なプロパティがあります。どちらの場合でも、標準では正確な実装戦略が義務付けられていません。

Answer 4

他の人からも言われているように、この規格では特定の実装が保証されていないようです。しかし、標準はでO（log n）時間のセットに挿入するなどのパフォーマンスの保証をしています。これはあなたが求めている本当の疑問です。