問題タブ [stl-algorithm]

ベクトルオブジェクトのアルゴリズムライブラリのfind関数を使用したいと思います。ベクトルオブジェクトは顧客のベクトルです（顧客は私が作成したクラスです）。私は最初にそれを実行しました、そしてそれは私にエラーを与えましたstl_algo.h。Webで検索し、ここでも検索しました。ここで質問を見つけ、同じコードを実行しましたが、それでもエラーが発生しました。

私のコードはここにあります：

ヘッダーファイル：

ソースコード：

Code :: Blocksでビルドした後、私はこれを手に入れました、

ヘッダーファイル内stl_algo.h：

ありがとう

編集：これがビルドログです

2 つのベクトルに対して、和集合、交点、排他的論理和、減算などのすべての集合演算を実行したいと考えています。どうやってやるの ？

リンクを見てください：セット操作のイメージ

私は、製品の変更によるパフォーマンス関連の影響を測定するためのツールを構築しています。

これを実現するために、関数が呼び出されるか戻るたびにトレースし、それについて通知するプロファイラーを実装しました。まず、出力をファイルにダンプして、使用するデータの感覚をつかみました。多かれ少なかれ、次のようになります。

このデータがどのように見えるかを視覚的に理解するために、最初の 10000 回の関数呼び出しのグラフを次に示します: (x 軸: 時間、y 軸: 深さ/ネスト): ( http://img444.imageshack.us /img444/4710/proflog.gif )

関数の実行が開始されると、その名前/識別子と現在の高精度のタイムスタンプがログに記録されます。関数が戻ると、開始時刻を保存したエントリを検索し、戻りをマークする新しいタイムスタンプを追加する必要があります。

要約すると、これらのデータに対して実行する操作は次のとおりです。

1. 現在のタイムスタンプを持つ新しい関数呼び出しマークを挿入します。
2. 特定の ID の最新の関数呼び出しを検索し、返されたタイムスタンプを保存します。
3. 特定の関数内から呼び出された他の関数を確認します (そして、その時間が費やされている場所を確認します)。たとえば、前の例で関数 #2 を見ている場合、関数 #3、関数 # 4、Function#5 と Function#5 は Function#6 を呼び出し、それから戻ります (すべての呼び出し/戻りタイムスタンプがマークされています)。

さて、このシナリオに適したデータ構造のアイデアがいくつかあります。

1. 各ノードのキーが関数識別子になり、各ノードの値がタイムスタンプ ペアのスタックになる自動バランス ツリー (AVL)。このアプローチにより、関数のタイムスタンプをマークするときに挿入と検索が高速になり、各ノードがスタックであるという事実が得られます。また、正しいリターン タイムスタンプを開始タイムスタンプに一致させることもできます。特定の関数は、最もネストされた/最近の関数呼び出しと一致する必要があります。このアプローチでは、ネストされた関数呼び出しを異なる識別子で維持するのは少し面倒です。なぜなら、ツリーを走査し、タイムスタンプに基づいて一致させてネストを把握する必要があるためです。理想的ではありません。

2. まだ返されていない関数のリストを維持し (呼び出しスタック情報を保持します)、各レベルが関数呼び出しの入れ子レベルと同じになるスキップ リストを使用します。このアプローチにより、操作 #3 が簡単になりますが、ルックアップは遅くなり、返されない関数 (main() など) の非常に長いリストを維持する必要が生じる可能性があります。ここでは、ハッシュテーブルを使用して、メモリ使用量を犠牲にしてルックアップ速度を向上させることもできます。メモリ使用量は重要です。このプロファイラーは約 20 MB/秒を簡単に生成します。

これらのデータを追跡するために単純なスタックを使用しない理由は、定期的に部分的な結果を別のマシンに同期し、すべてが返される前に少なくとも部分的な結果を利用できるようにする必要があるためです。

インターバル ツリー、レンジ ツリー、およびその他の種類のデータ構造を調べましたが、私の 3 つの要件すべてを効率的に満たすものは見つかりませんでした。

たぶん、私が気付いていないすべてを満たすデータ構造があるのでしょうか? 何か案は？

アップデート：

これはどうですか：

ネストされた呼び出しと一緒に関数呼び出しを持つツリーと、返されなかった関数用の別のスタックを持つ。

これで、スタック上のすべての要素がツリー内のコピーへのポインターを持ち、新しい関数呼び出しが到着すると、スタックの一番上の要素を見て、ツリー内の表現へのポインターをトレースし、新しい関数呼び出しを追加します。その呼び出しの子として、新しく作成されたツリー ノードへのポインターを使用して、そのコピーをスタックにプッシュします。

関数の戻り値の場合も同様です。関数の戻り値ごとに、スタックの最新のエントリは常にその呼び出しになります。呼び出しポインターをトレースし、戻り時間をツリーに保存し、呼び出しをポップします。

私の考えに大きな欠陥はありますか？

更新 2:

私のアプローチは完璧に機能しました。2 日間待って、質問にお答えします。

無向グラフに設定された最大独立頂点のメモリ保守的かつ効率的なアルゴリズムを見つけたいです。

従来のアルゴリズムは、補助データ構造 (元のグラフのコピー) を使用して実装します。リアルタイム実装ではメモリ割り当てが遅く、いくつかのメモリ境界があるため、このような並列構造は避けたいと思います。MIS のノードにブール値のラベルを付けたいだけです。出来ますか？

最大の独立集合ではなく、最大の独立集合が必要であることに注意してください。

PS この問題は言語に依存しないことはわかっていますが、C++ と STL でコーディングしています。

要素を出現回数でソートしたいと思います。これは私が思いついたものです（mHeightsはstd :: multisetです）：

したがって、最初にマルチセットからすべての一意の要素を取得し、次にそれらをカウントして新しいコンテナーに並べ替えます（カウントが必要なので、マップを使用します）。これは、このような簡単な作業では非常に複雑に見えます。他の場所でも使用されているHistPairを除いて、equal_rangeやsthを使用するなど、このタスクを単純化するstlアルゴリズムはありません。同様に。

編集：発生回数も必要です、申し訳ありませんがそれを忘れてしまいました

sのベクトルから重複する値を削除したいとしますint。通常の解決策は、ベクトルをソートし、erase-removeイディオムを使用して重複を消去することです。ただし、削除されない要素の順序を維持する必要があるため、並べ替えることはできません。したがって、次のような述語を考え出し、remove_ifアルゴリズムで使用することができます。

setただし、メンバーのコピーが2つ取得されるため、何らかの理由で述語オブジェクトがコピーされると、これは機能しなくなります。そして確かに、gccの実装remove_ifはまさにそれを行います：

回避策はset、ファンクターのメンバーを静的にすることです。

しかし、疑問は残ります：

述語ファンクターの可能なコピーがロジックを壊さないことを確認する必要がありますか？ この問題に関して特定の動作を義務付ける（または禁止する）規格には何かありますか？それとも、実装のバグですか？

カスタムクラスがありstd::vector、このクラスのオブジェクトでいっぱいです。binary_searchそして、私はこの配列でやりたいです。

私は次のようにクラスの演算子をオーバーロードしました：

そして彼らはうまく働いています（彼らは体を持っています、うん）。

エラーエラーが発生しました

コピーコンストラクターを作成する必要がありますか（すでにオーバーロードされていますが、役に立ちませんでした）、または演算子に何か他のものを追加する必要がありますか？

ありがとう。

私はC++アプリケーションに取り組んでいます。

ポイントのベクトルが2つあります

Point2fが定義されていますtypedef Point_<float> Point2f;

vectorAllには1000ポイントがあり、vectorSpecialには10ポイントがあります。

最初の一歩：

vectorAllでの順序に応じて、vectorSpecialでポイントを順序付ける必要があります。だからこのようなもの：

ダブルループを実行してインデックスを保存できます。次に、インデックスに基づいてポイントを並べ替えます。ただし、ポイントが多い場合、このメソッドは時間がかかりすぎます（たとえば、vectorAllで10000ポイント、vectorSpecialで1000ポイントなので、1,000万回の反復になります）

それを行うためのより良い方法は何ですか？

第二段階：

vectorSpecialの一部のポイントは、vectorAllでは使用できない場合があります。sqrt((x1-x2)^2 + (y1-y2)^2)（通常の距離式を使用して）それに最も近いポイントを取得する必要があります

これはループ時にも実行できますが、誰かがより良い方法について何か提案があれば、私はそれをいただければ幸いです。

助けてくれてありがとう

次のような別の基準を定義せずに、基準に従ってコンテナを並べ替えるにはどうすればよいですか。

私はintのペアのセットを持っています set<pair<int,int> > x1, x2, ... xn（nは2から20の間である可能性があります）。それらの集合の和集合を見つけるための最速の方法は何ですか？

申し訳ありませんが、最初に明確にしなかった場合は、パフォーマンスが速いことを意味し、メモリ割り当ては問題ではありません。