Некоторое время я размышлял над проблемой структуры данных, но, похоже, не могу найти хорошего решения. Я не могу избавиться от ощущения, что решение простое, и я просто не вижу его, поэтому, надеюсь, вы, ребята, можете помочь!
Вот проблема: у меня есть большая коллекция объектов в памяти. Каждое из них имеет несколько полей данных. Некоторые поля данных, такие как идентификатор, уникальны для каждого объекта, но другие, например имя, могут появляться в нескольких объектах.
class Object {
size_t id;
std::string name;
Histogram histogram;
Type type;
...
};
Мне нужно организовать эти объекты таким образом, чтобы я мог быстро (даже если количество объектов относительно велико, например, миллионы) отфильтровать коллекцию, учитывая спецификацию произвольного числа членов объекта, в то время как количество всех оставленных элементов не указано как подстановочные знаки. Например, если я укажу данный name
Я хочу получить все объекты, имя члена которых равно заданному имени. Однако, если я затем добавлю гистограмму к запросу, я бы хотел, чтобы запрос возвращал только те объекты, которые совпадают в обоих name
и histogram
поля и тд. Так, например, я хотел бы функцию
std::set<Object*> retrieve(size_t, std::string, Histogram, Type)
что может сделать
retrieve(42, WILDCARD, WILDCARD, WILDCARD)
так же как
retrieve(42, WILDCARD, WILDCARD, Type_foo)
где второй вызов вернул бы меньше или столько же объектов, сколько первый. Какая структура данных допускает подобные запросы и может быть построена и запрошена за разумное время для подсчета объектов в миллионах?
Спасибо за помощь!
Сначала вы могли бы использовать Boost Multi-index осуществлять эффективный поиск по различным членам вашего Object
, Это может помочь ограничить количество элементов для рассмотрения. В качестве второго шага вы можете просто использовать лямбда-выражение для реализации предиката для std::find_if
чтобы получить первый элемент или использовать std::copy_if
скопировать все элементы в целевую последовательность. Если вы решили использовать Boost, вы можете использовать Boost Range с фильтрация.
Других решений пока нет …