Задачка на std::multiset или поиск по полям структуры

[Elsedar]

Вы делали сравнение с выборкой из БД? Если да, то с какой? Вы же понимаете, что просто создали кучу индексов на все нужные вам комбинации. А так же то, что всю БД вы держите в памяти. Поэтому, если выбрать in-memory БД, и создать так же много индексов, то, мне кажется, результат будет примерно таким же.

[RPG18]

Обычно в таких ситуациях берут какой-нибудь SQLite, который можно сделать in-memory и заводят индексы. Такое проходил когда заставили переписывать приложение с C# и его linq на C++. Тут мне взяли и поставили задачку седлать без БД.

[mad_god]

Мой преподаватель по СУБД только фыркал, когда я упоминал про SQLite.

[hd_keeper]

И есть за что.

[RomanArzumanyan]

Задача на собеседование или рабочий проект?

[RPG18]

Переписывание с C# на C++ был рабочим проектом. Грустное это дело переписывать что-либо с C#/Java на C++, в основном из-за поиска чем бы заменить ту или иную библиотеку.

[RomanArzumanyan]

Тогда отказ от СУБД придаёт проекту особый шарм.

[RPG18]

Конкретно эта задачка, была как тестовое задание. Счел её интересной.

[Dionis_mgn]

Ребятам из фотостраны придется сочинять новое тестовое задание =)

[Siemargl]

Есть более-менее стандартное решение в виде Boost Multi-index Конечно, если огромный бюст вас не пугает в проекте.

[RPG18]

Спасибо, не знал про Boost Multi-index. Вот за что люблю хабр, что в комментариях можно узнать что-то новое.

[D_T]

Еще есть boost::multi_index

[k0t_begemot]

Неплохо было бы выложить проект на github.

[ProstoTyoma]

del

[Shamov]

Если переделать BiCriterion таким образом, чтобы это была фабрика, то получится код на Java :)

[ProstoTyoma]

А зачем вам AbstractCriterion? Обязать производные классы иметь этот интерфейс?

[RPG18]

На будущее. Можно сделать такую штуку:

class MultiCriterion: public AbstractCriterion
{
//
void add(const std::shared_ptr<AbstractCriterion>& cri)
{
    m_criteria.push_back(cri);
}
//...
std::vector<std::shared_ptr<AbstractCriterion>> m_criteria;
}

т.е. можно сделать по 3 и более условиям.

[narick]

А как же високосные года? =)

class AgeCriterion: public AbstractCriterion
{
public:

    static const unsigned int SECONDS_IN_YEAR = 31536000;
    ...

[RPG18]

Тогда наверное проще использоваться localtime и работать с tm

[RPG18]

Я не знаю имеет ли задачка практического применения. Тут пишут, что:

Multisets are typically implemented as binary search trees.

Поэтому все будет зависеть от конкретной реализация дерева.

[gorodnev]

Совершенно необязательно, STL говорит про интерфейс, а не реализацию. Может и AVL быть, или еще что. Но самые популярные реализации на красно-черном.

[Videoman]

Сдается мне, что ваше решение будет жутко расточительным по памяти. Дело в том что std::*set и std::*map очень активно используют кучу внутри себя.и из-за этого, относительно, медленно добавляют/удаляют такое большое количество элементов. Такое ощущение что у вас очень мощная 64-х битная операционка с большим количеством памяти. В 32-х битном процессе такая реализация легко может вызвать OutOfMemory.
Можно полюбопытствовать, сколько памяти занимает таким образом созданный индекс?

[RPG18]

4 std::multiset на 10 000 000, плюс std::vector для хранения исходных данных отъели 2.4Gb. CLion отъел 735 Mb.
В условии задачки есть подсказка:

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

[Videoman]

Условие я заметил. Но тут все зависит от того, как его трактовать. Если база совсем редко изменяется, то выгоднее использовать 5-ть отсортированных std::vector-ов (четыре для индекса и один для самих структур). Будет занимать 200 + 160 = 360 Мб, Примерно в два раза меньше памяти. Ну а вообще, тут, конечно, самым оптимальным будет использование B+Tree. У него плотность будет сравнима с векторами, а скорость поиска с двоичным деревом.