2 つの並べ替えられたパラメーターからの位置に基づいて、大規模なコレクションからオブジェクトを抽出する最良の方法を探しています。
例：
struct Object{
Time start;
Time end;
//... data
};
ここで、この時間内に「存在する」すべてのオブジェクト、つまりオブジェクトと値の間にあるすべてのオブジェクトをすばやくt見つけたいと考えています。tstartend
私が考えたアプローチは、次を使用することです。
std::multimap<Time, object*> objectsOrderedByStart;
std::multimap<Time, object*> objectsOrderedByEnd;
(ソートされたキーである同じ値multimapを持つオブジェクトが多数存在する可能性があるため)Time
を作成するたびObjectに、それを each に追加します。これにより、オブジェクトがおよびmultimapのソート済みリストに自動的に配置されます。startend
次に、 wheret内のすべてのオブジェクトとobjectsOrderedByStartwhere内のオブジェクトを検索し、両方の結果セットにあるオブジェクトのみを取得することt>Timeで、有効なオブジェクトの時間を「クエリ」します。しかし、これは非効率的であり、結合を見つけるために私が考えることができる唯一の手法は、1 つの結果セットを 1 つずつ調べて、そのオブジェクトが他の結果セットにあるかどうかを確認することです。objectsOrderedByEndt<End
ただし、これは最も効率的な方法ではないと思います。1 つずつ反復するのではなく、 each を反復するときに要素をスキップして反復しmultimap、行き過ぎた場合はフォールバックして、最後のスキップ ポイントから 1 つずつ反復することができます。または、 1 つだけ保持してからmultimap、それぞれの内部objectを覗いてそのend時間を確認することもできます。
しかし、このデータを整理して、興味のある範囲でそれらを見つけるためのより良い方法があると思いますか?