I am looking for the best way to extract objects from a large collection based on their position from two sorted parameters.
Example:
struct Object{
Time start;
Time end;
//... data
};
Now, for any time t I want to quickly find all objects that "exist" within this time, i.e. t is between the objects' start and end values.
The approach I have thought of is to use:
std::multimap<Time, object*> objectsOrderedByStart;
std::multimap<Time, object*> objectsOrderedByEnd;
(multimap since there may be many objects with the same Time values, which are the sorted keys)
Every time I create an Object I add it to each multimap which automatically places the object in a sorted list for start and end.
I then "query" for my valid objects for time t by looking for all objects in objectsOrderedByStart where t>Time and objects in objectsOrderedByEnd where t<End, and then taking only those that are in both result sets. But this seems inefficient and the only technique I can think of to find the union is by going through one result set one-by-one and looking to see if that object is in the other result set.
However I suspect this is not the most efficient method. I could iterate by skipping over the elements when iterating each multimap, rather than one-by-one iteration, then fall back if I've gone too far and iterate one-by-one from the last skipping point. Alternately I could retain just one multimap and then peer inside each object to look at its end time.
But I suspect there is a better way to organize this data and find those in the range that interest me?
