2

std::set 挿入メンバー関数の効率的な実装は何でしょうか? データ構造は std::less に基づいて要素をソートするため (演算子 < は要素の型に対して定義する必要があります)、重複を検出することは概念的に簡単です。

実際に内部でどのように機能しますか？レッドバック ツリーのデータ構造 (Josuttis の本で言及されている実装の詳細) を利用していますか?

標準データ構造の実装は異なる場合があります...

一意である必要がある (一般的に言えば) 整数のセットを持たなければならないという問題があります。セットの長さはさまざまなので、動的なデータ構造が必要です (私の狭い知識に基づいて、これはリスト、セットに絞り込みます)。要素は必ずしもソートする必要はありませんが、重複はありません。候補セットには常に多くの重複があるため (セットは小さく、最大 64 個の要素)、insert メンバー関数を使用して std::set に重複を挿入しようとすると、std::list や別のアルゴリズムと比較して多くのオーバーヘッドが発生します。要素をソートすることに頼らないかもしれませんか？

追加: 出力セットは 27 要素の固定サイズです。申し訳ありませんが、これを忘れていました...これは、問題の特殊なケースで機能します。それ以外の場合、長さは任意です (入力セットよりも小さい)。

4

3 に答える 3

3

セット全体を一度に作成する場合は、 を使用std::vectorして要素を保持し、std::sort並べ替えてstd::unique、重複を取り除くことができます。

于 2012-05-09T13:32:13.633 に答える
2

の複雑さstd::set::insertはO（log n）、または「位置」挿入を使用して正しい位置を取得する場合は償却O（1）です（たとえば、http ：//cplusplus.com/reference/stl/set/insert/を参照）。

基盤となるメカニズムは実装に依存します。多くの場合、赤黒木ですが、これは必須ではありません。お気に入りの実装のソースコードを見て、それが何をしているのかを知る必要があります。

小さなセットの場合、たとえば、ベクトルの単純な線形探索は、空間的な局所性のために安価になる可能性があります。ただし、挿入自体では、次のすべての要素をコピーする必要があります。確実に知る唯一の方法は、各オプションのプロファイルを作成することです。

于 2012-05-09T13:19:39.850 に答える
1

事前にわかっている可能性のある値が 64 個しかない場合は、ビット フィールドを取得して、実際に表示される要素のビットをオンにします。これは n+O(1) ステップで機能し、それより少なくなることはありません。

サイズ mの a に挿入するにstd::setは O(log(m)) の時間と比較std::setが必要です。入力を単純に並べ替え (追加のスペースが必要)、重複を破棄します。

リスト内の挿入場所を見つけるには O(n) が必要なため、同じことを an で行うにはstd::list平均 O(n^2) 時間がかかります。

一度に 1 つの要素を an に挿入するのstd::vectorにも O(n^2) 平均時間がかかります。挿入場所を見つけるのは O(log(m)) で実行できますが、スペースを空けるために要素を移動する必要があります。最終結果の要素数が入力よりもはるかに小さい場合、O(n*log(n)) にまで減少し、スペースのオーバーヘッドはほとんどありません。

C++11 コンパイラを使用している場合、またはブーストを使用している場合は、ハッシュ テーブルも使用できます。挿入特性についてはよくわかりませんが、結果の要素数が入力サイズに比べて少ない場合は、O(n) 時間だけで済みます。また、ビット フィールドとは異なり、その必要はありません。潜在的な要素または結果のサイズを先験的に知っている (ただし、再ハッシュを回避できるため、サイズを知っていると役立ちます)。

于 2012-05-09T13:37:07.457 に答える