問題タブ [multiset]

std :: multisetについて別の質問をしましたが、今では十分な理解が必要であり、インターネットでこれ以上複雑な例を見つけることができません。

std::multiset<A,B>ここでAとBのどのように機能し、どのような機能があるのか​​、またそれらのいずれかを省略できるかどうかを説明していただけますか？AまたはBをいくつかの変数に入れることはできますか？私はいくつかの短い例、または参照を本当に感謝します、

マルチセットからすべての重複を出力したいのですが、どういうわけかイテレータが奇妙に動作します。このコードを修正するにはどうすればよいですか? このコードは永久ループを引き起こします。これには驚かされます。

EDIT サイクルの最後に --it を追加しました

以下の TEST_FUNCTION の呼び出しは、「ORA-03113: 通信チャネルのファイルの終わり」で失敗します。回避策は TEST_FUNCTION2 に示されています。私の実際の機能ははるかに複雑なので、コードを煮詰めました。Oracle 11G でテスト済み。最初の関数が失敗する理由を知っている人はいますか?

マルチセットを介して O(n) の k 番目の要素を検索することは可能ですか (値は繰り返すことができます)?

クイック選択のアイデアを理解している限り、ピボットを使用して入力を分割する必要があるためです。次に、再帰検索用に選択する2つの配列があります。これは、検索しているインデックス要素と、たとえば両方の配列のサイズによって異なります。

1 7 8 5 3 2 4

ピボットが 4 だとしましょう。私は 2 番目に大きな要素を探しています。したがって、パーティショニング後、次のような順序になる可能性があります

1 3 2 4 7 8 5

右側のサブ配列は 3 つの要素で構成されているため、正しい場合は右側の配列で 2 番目に大きいものを見つけようとしますか?

しかし、ピボットとして 8 を使用すると、次のような結果が得られる可能性があります。

1 3 2 7 5 4 8

したがって、左のテーブル内で最大の要素を見つけようとします（おそらく線形ですが、一般的には左のサブ配列を取得して要素を検索します-（|右のサブ配列サイズ| + 1））

しかし、マルチセットはどうですか? 私が配列を持っているとしましょう：

4 5 6 7 7 7 4 3 2 1

そして、私のピボットは 6 番目に大きい要素を検索することです。

4 5 3 2 4 1 6 7 7 7

したがって、上記のアプローチを使用すると、右側のサブ配列で再帰を実行しようとしますが、3 番目に大きい値は左側にある 5 であることが明らかですか?

私が思いついた唯一の解決策は、BST、Setなどのデータ構造を使用して、O(nlogn)で繰り返しを除外することです。次に、O(n) クイック選択を使用します。しかし、全体としては非線形のアプローチになりましたが、これを線形にすることはできますか?

追加の質問もありますが、メモリの割り当てができない場合はどうすればよいですか? そして、私ができることは、ローカル ints + スタック再帰のみを使用することです。問題は O(n) で解決できますか? O(nlogn) は、並べ替え + 線形の「カウントを通過する」ことで実行できるためです。

楽しみのために、想像できる最も単純な並べ替えアルゴリズムを実装しました。

std::sort私のテストデータよりも約20倍遅いだけです:)

次に、移動セマンティクスを使用してパフォーマンスを改善したいと考えました。

しかし、私が s をソートしているにもかかわらず、これはパフォーマンスに大きな影響を与えませんでしたstd::string。

次に、連想コンテナは外部から一定であることを思い出しました。つまり、ここでも同じことをstd::move行いstd::copyます:(データをツリーから移動する他の方法はありますか?

多数の整数をファイルに保存する必要があります。整数の順序は重要ではないため、情報内容の合計は順序付けられたリストよりも低くなるはずです。任意に順序付けられた配列よりも、数値を格納するスペース効率の良い方法はありますか?

編集：整数は完全にランダムであると想定しています。順列を修正することによって導入される冗長な情報を絞り出す普遍的な方法を本当に探しています。

クラスメンバーに従ってソートするマルチセットmymulti がありm_aます。

次に、並べ替えられたすべての要素をチェックしたいのですがm_a、隣のフィールドの差が、指定しmymultiたしきい値、たとえば 0.001 より小さい場合です。もしそうなら、私は別のクラスメンバー m_b が小さい方を優先したいと思います。

マルチセットやイテレータの経験がありません。2 つの反復から反復子を比較する方法がわかりません。私がやりたいことの正しいコードを私に提供できれば、とても感謝しています! 私の試み、あまり多くはありませんが、私のコンセプトだけです：

このような方法で、2 つのメンバーに従ってクラス オブジェクトの並べ替えを取得しようとしています: メンバーに従って並べ替えます。2 つのオブジェクトの値が同じ場合 (または差がしきい値を下回っている場合) は、メンバーbに従って検索します。私はそれでマルチセットを使用しています。

問題は、別のオブジェクトが来て、並べ替えクラスに従ってチェックされ、満たすと true を返す (比較対象のオブジェクトよりも上位に配置される) 場合、別のオブジェクトが 1 段階上にあることで満たされる可能性があることです。ここで、できるだけ多くの以前のオブジェクトをチェックし、可能な限り高くする必要があることをどのように紹介できますか? (非常によくソートされたマルチセットを取得するために!) ソート クラスの書き方を以下に示します。素敵なアイデアを教えてください！

そして、コードのこの部分にインデントを導入するのに問題がありました。編集を手伝ってくれる人はいますか? それは読めません。

編集：

これを貼り付けて、私が望むものと達成できないものを見てください。m_a が同じ場合、m_a で増加し、m_b で減少するように並べ替えたい (等値または不等値をそこに置くことができ、どちらも機能しない)

Oracle 11g で次のようなことができますか。

タイプを事前定義せずにプレーンSQLで？ポリモーフィズムのようなものをサポートしていますか?

Facebook Hacker Cup 2013 Qualification Problems を Scala で試していました。3 番目の問題については、順序付けされたマルチセットが必要だと感じましたが、scala の (2.10) コレクションには見つかりませんでした。このデータ構造はscalaのコレクションにありませんか? 将来のバージョンで実装される予定はありますか? すでにセットを実装している場合、マルチセットは本当に必要ありませんか?