15

次の問題を解決しようとしています: 数字がコンテナに挿入されています。数値が挿入されるたびに、現在挿入されている数値以上の要素がコンテナー内にいくつあるかを知る必要があります。どちらの操作も対数の複雑さで実行できると思います。

私の質問: C++ ライブラリに、問題を解決できる標準コンテナーはありますか? 対数時間で要素を挿入できることは知っていstd::multisetますが、どのようにクエリを実行できますか? または、それを解決するためにデータ構造 (二分探索木など) を実装する必要がありますか?

4

5 に答える 5

4

素晴らしい質問です。あなたのニーズに合ったSTLには何もないと思います（対数時間を持たなければならないという条件で）。aschepler がコメントで述べているように、最善の解決策は RB ツリーを実装することだと思います。STL ソース コードを見て、特にその一部をstl_tree.h使用できるかどうかを確認することができます。

さらに良いことに、以下をご覧ください: ( C++ のランク ツリー)

実装へのリンクが含まれています：

( http://code.google.com/p/options/downloads/list )

于 2013-07-02T15:39:49.630 に答える
1

はい、対数の複雑さにはマルチセットを使用する必要があります。しかし、set/map イテレータは RandomAccess ではなく Bidirectional であるため、距離の計算が問題です。 std::distance には O(n) の複雑さがあります。

multiset<int> my_set;
...
auto it = my_map.lower_bound(3);
size_t count_inserted = distance(it, my_set.end()) // this is definitely O(n)
my_map.insert(make_pair(3);

あなたの複雑さの問題は複雑です。完全な分析は次のとおりです。

挿入ごとに O(log(n)) の複雑さが必要な場合は、セットとして並べ替えられた構造が必要です。新しいアイテムを追加するときに構造がアイテムを再割り当てまたは移動しないようにする場合、挿入ポイントの距離の計算は O(n) になります。事前に挿入サイズがわかっている場合は、ソートされたコンテナーでの対数挿入時間は必要ありません。すべてのアイテムを挿入して並べ替えることができます。これは、セット内の n * O(log(n)) 挿入と同じ O(n.log(n)) です。唯一の代替手段は、加重 RB ツリーのような専用コンテナーを使用することです。問題によっては、これが解決策になることもあれば、やり過ぎになることもあります。

  • とを使用するmultisetとdistance、挿入時に O(n.log(n)) (はい、n 個の挿入 * それぞれの挿入時間の log(n))、距離計算で O(nn) になりますが、距離の計算は非常に高速です。
  • 挿入されたデータのサイズ (n) が事前にわかっている場合: ベクトルを使用し、塗りつぶし、並べ替え、距離を返すと、O(n.log(n)) になり、コーディングが簡単になります。
  • 事前に n がわからない場合、n は巨大である可能性が高く、各アイテムはメモリが重いため、 O(n.log(n)) 再割り当てを行うことはできません。再エンコードまたは一部を再利用する時間があります。非標準コードの場合、これらの複雑さの期待を満たす必要があり、専用のコンテナーを使用する必要があります。データベースの使用も検討してください。これをメモリに保持する際に問題が発生する可能性があります。
于 2013-07-02T16:09:30.660 に答える