структуры данных — иерархический отфильтрованный поиск в переполнении стека

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

Вот проблема: у меня есть большая коллекция объектов в памяти. Каждое из них имеет несколько полей данных. Некоторые поля данных, такие как идентификатор, уникальны для каждого объекта, но другие, например имя, могут появляться в нескольких объектах.

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)

где второй вызов вернул бы меньше или столько же объектов, сколько первый. Какая структура данных допускает подобные запросы и может быть построена и запрошена за разумное время для подсчета объектов в миллионах?

Спасибо за помощь!

0

Решение

Сначала вы могли бы использовать Boost Multi-index осуществлять эффективный поиск по различным членам вашего Object, Это может помочь ограничить количество элементов для рассмотрения. В качестве второго шага вы можете просто использовать лямбда-выражение для реализации предиката для std::find_if чтобы получить первый элемент или использовать std::copy_if скопировать все элементы в целевую последовательность. Если вы решили использовать Boost, вы можете использовать Boost Range с фильтрация.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector