Как найти ряд объектов в контейнерах на основе нескольких параметров

Question

Я ищу лучший способ извлечения объектов из большой коллекции на основе их положения от два отсортированных параметров.

Пример:

struct Object{ 
    Time start; 
    Time end; 
    //... data 
}; 

Теперь для любого времени t я хочу быстро найти все объекты, которые «существуют» в течение этого времени, т.е. t находится между start и end значениями Объектами.

Подход, который я думал, это использовать:

std::multimap<Time, object*> objectsOrderedByStart; 
std::multimap<Time, object*> objectsOrderedByEnd; 

(multimap, поскольку может быть много объектов с одинаковыми Time значениями, которые являются упорядоченные ключи)

Каждый раз, когда я создать Object Я добавляю его каждому multimap, который автоматически помещает объект в отсортированный список для start и end.

я тогда «запрос» для моих действительных объектов для времени t путем поиска всех объектов в objectsOrderedByStart, где t>Time и объектов в objectsOrderedByEnd где t<End, а затем принимать только те, которые находятся в обоих наборах результатов. Но это кажется неэффективным, и единственная техника, которую я могу найти, чтобы найти объединение, - это один из одного набора результатов и посмотреть, находится ли этот объект в другом результирующем наборе.

Однако я подозреваю, что это не самый эффективный метод. Я мог бы итерации, пропуская элементы при повторении каждого multimap, а не поочередной итерации, а затем отступить, если я зашел слишком далеко и повторю один за другим с последней точки прохода. В качестве альтернативы я мог сохранить только один multimap, а затем заглянуть внутрь каждого object, чтобы посмотреть на его end раз.

Но я подозреваю, что есть лучший способ организовать эти данные и найти тех, кто интересует меня?

Answer 1

Вы можете использовать два вручную отсортированных массива вместо двух мультиплексоров, а затем использовать std::lower_bound и std::upper_bound или ручной двоичный поиск вручную для поиска в них.

Answer 2

Я думаю, вы должны взглянуть на Boost.ICL