C ++ベクターの検索＆lt;カスタムクラス＆gt;値の最初/最後の出現に対して

StackOverflow https://stackoverflow.com/questions/1649139

質問

「Tracklet」型のベクトルを検索するための最良の方法を探しています。 （私が自分で作成したクラス）変数の1つに対して指定された値の最初と最後の出現を検索します。たとえば、次のクラスがあります（この例では簡略化しています）：

class Tracklet {
    TimePoint *start;
    TimePoint *end;
    int angle;

    public:
        Tracklet(CvPoint*, CvPoint*, int, int);
}

class TimePoint {
    int x, y, t;

    public:
        TimePoint(int, int, int);
        TimePoint(CvPoint*, int);
        // Relevant getters and setters exist here   
};

ベクター＆quot; vector＆lt; Tracklet＆gt;があります。トラックレット＆quot;そして、「t」の値が指定されたトラックレットを検索する必要があります。終了時点。ベクトルは終了時間の順に並べられます（つまり、 tracklet.end-＆gt; t ）。

検索アルゴリズムをコード化できてうれしいですが、どのルートを使用するかわかりません。バイナリ検索が適切かどうかはわかりません。必ずしも最初の検索が見つかるとは限らないことを覚えているようです。私は、バイナリ検索を使用して正しい時刻の要素のインデックスを見つけ、最初の要素を見つけるために戻って、最後の要素を見つけるために前方に繰り返す方法を考えていました。繰り返しによるバイナリ検索O（log n）を無駄にするので、それよりも良い方法があると確信しています。

うまくいけばそれは理にかなっています：私はそれを少し説明するのに苦労しました！ 乾杯！

役に立ちましたか？

解決

ベクトルがソートされ、値が含まれている場合、 std :: lower_bound は、指定された値を持つ最初の要素へのイテレーターを提供し、 std :: upper_bound は値を含む最後の要素の1つ後の要素に反復子を与えます。値を返された要素と比較して、ベクトルに存在しているかどうかを確認します。これらの関数は両方ともバイナリ検索を使用するため、時間はO（logN）です。

tracklet.end-＆gt; t で比較するには、次を使用します：

bool compareTracklets(const Tracklet &tr1, const Tracklet &tr2) {
    return (tr1.end->t < tr2.end->t);
}

lower_bound または upper_bound

の4番目の引数としてcompareTrackletsを渡します

他のヒント

find を使用するだけです find_end を実行し、テストする場合にのみより複雑な操作を行います遅すぎることを示しました。

ルックアップのパフォーマンスが本当に心配な場合は、タイムスタンプをキーとして map や vector または値としての要素のリスト。

ベクトルがソートされたままである限り、バイナリ検索はここでの最良のオプションのようです。これは、バイナリツリー構造でルックアップを実行するのと基本的にパフォーマンスが同じです。

直接参照最適な最適化の比較。しかし、実際にはこのために std :: vector を使用しません。

通常、STLコンテナーを使用することを決定するとき、パフォーマンスの側面はあまり考慮しませんが、使用する操作の種類に関するインターフェイスを考慮します。

std::set<T>::find
std::set<T>::lower_bound
std::set<T>::upper_bound
std::set<T>::equal_range

本当に、キー/値の設定以外で順序付けされたシーケンスが必要な場合、 std :: set は他のどのものよりも簡単に使用できます。

  • 「悪い」位置に挿入することを心配する必要はありません
  • 要素を追加/削除するときにイテレータの無効化の問題はありません
  • 検索用の組み込みメソッドがあります

もちろん、すべての場合において、比較述語を本当に輝かせたい（コンパイラーがoperator（）実装をインライン化することを望んでいます）。

しかし、本当に確信が持てない場合は、 std :: vector と手動挿入/検索（＆lt; algorithm＆gt; ヘッダーを使用）でビルドを試してください。 std :: set を使用して別のビルドを試してください。

実装のサイズ（コードの行数）を比較し、バグの数を比較し、速度を比較してから決定します。

ほとんどの場合、あなたが目指す「最適化」は実際にはです。悲観化、そしてまれなケースではありませんが、非常に複雑なので価値がありません。

最適化：

  • しないしない
  • エキスパートのみ：しないでください
  

ベクトルは時間の順に並べられます

開始時間ですか、終了時間ですか？

単純なO（n）検索の何が問題になっていますか？並べ替えではなく、検索のみを行っていることに注意してください。ソートされたコンテナも使用できます（それが基本設計に反しない場合）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top