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

Попалась небольшая задачка, где-то на 4 часа кодирования, которую счел занимательной.

Есть база пользователей 10 миллионов:

class User{
 int id; 
 time_t birthday; // дата рождения
 int gender;      // пол
 int city_id;     // место проживания
 time_t time_reg; // дата регистрации
};

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

• город;
• город, пол;
• пол, возраст.

Данные выдачи должны быть отсортированы по дате регистрации пользователей, и выдаваться постранично по 100 пользователей.

Подсказка 1: СУБД не даст нужной скорости.
Подсказка 2: Вспомнить сложность операций со множествами, сложность стандартных алгоритмов.
Подсказка 3: Проверить время поиска реализованного алгоритма, неплохой результат это порядка 0.005 сек.

Из готовых контейнеров для этой задачи можно использовать std::vector, отсортированный по нужному кретерию поиска, и std::lower_bound с реализацией:

template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                               const T& val, Compare comp);

Или использовать std::multiset. Выбрал std::multiset по причине того, что в него можно засунуть компаратор, который будет использоваться для вставки и поиска.

Захотелось заложить легкое расширение поиска, поэтому пошел по заветам Александреску и реализовал компаратор как стратегию.

Для экономии памяти multiset хранятся указатели на User, поэтому интерфейс критерии поиска выглядит так:

class AbstractCriterion
{
public:

    virtual ~AbstractCriterion() = default;

    virtual bool matched(const User &user) const noexcept = 0;

    User patternForSearch() const noexcept
    {
        User user;
        initPattern(user);
        return user;
    }

    virtual int signature() const noexcept = 0;
    virtual void initPattern(User &user) const noexcept = 0;
    virtual bool operator()(const User *first, const User *second) const noexcept = 0;
};

Метод	Описание
matched	соответствует User данному критерию или нет
patternForSearch	шаблонный метод для формирования ключа поиска
operator()	сравнение элементов
signature	используется как идентификатор критерии

Примеры реализации двух критерий:

class CityCriterion: public AbstractCriterion
{
public:

    CityCriterion()
        : m_city(0)
    {
    }

    CityCriterion(int city)
        : m_city(city)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return user.cityId == m_city;
    }

    void initPattern(User &user) const noexcept final
    {
        user.cityId = m_city;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::City;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        return first->cityId < second->cityId;
    }

private:

    int m_city;
};

class GenderCriterion: public AbstractCriterion
{
public:

    GenderCriterion()
        : m_gender(No)
    {
    }

    GenderCriterion(int gender)
        : m_gender(gender)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return user.gender == m_gender;
    }

    void initPattern(User &user) const noexcept final
    {
        user.gender = m_gender;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::Gender;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        return first->gender < second->gender;
    }

private:

    int m_gender;
};

Необязательно ограничиваться имеющимися полями структуры. Например возраст можно вычислять:

class AgeCriterion: public AbstractCriterion
{
public:

    static const unsigned int SECONDS_IN_YEAR = 31536000;

    AgeCriterion()
        : m_age(0)
    {
        time(&m_curTime);
    }

    AgeCriterion(int age)
        : m_age(age)
    {
        time(&m_curTime);
    }

    bool matched(const User &user) const noexcept final
    {
        const unsigned int age = difftime(m_curTime, user.birthday) / SECONDS_IN_YEAR;
        return m_age == age;
    }

    void initPattern(User &user) const noexcept final
    {
        user.birthday = m_curTime - (m_age + 1) * SECONDS_IN_YEAR;
    }

    virtual int signature() const noexcept final
    {
        return Signatures::Age;
    }

    bool operator()(const User *first, const User *second) const noexcept final
    {
        const int firstAge = difftime( m_curTime, first->birthday) / SECONDS_IN_YEAR;
        const int secondAge = difftime( m_curTime, second->birthday) / SECONDS_IN_YEAR;

        return firstAge < secondAge;
    }

private:

    size_t m_age;
    time_t m_curTime;
};

Для поиска по двум полям ввел следующий шаблонный класс и функцию:

template<typename FirstCriterion, typename SecondCriterion>
class BiCriterion: public AbstractCriterion
{
public:

    BiCriterion(const FirstCriterion &first, const SecondCriterion &second)
        : m_first(first), m_second(second)
    {
    }

    bool matched(const User &user) const noexcept final
    {
        return m_first.matched(user) && m_second.matched(user);
    }

    void initPattern(User &user) const noexcept final
    {
        m_first.initPattern(user);
        m_second.initPattern(user);
    }

    int signature() const noexcept final
    {
        const auto sign1 = m_first.signature();
        const auto sign2 = m_second.signature();
        return sign1 | sign2;
    }

    bool operator()(const User *first,
                    const User *second) const noexcept final
    {
        const bool less = m_first(first, second);

        if (!less && !m_first(second, first)) {
            return m_second(first, second);
        }
        else {
            return less;
        }
    }

private:

    FirstCriterion m_first;
    SecondCriterion m_second;
};

template<typename FirstCriterion, typename SecondCriterion>
BiCriterion<FirstCriterion, SecondCriterion> AND(const FirstCriterion &first, const SecondCriterion &second)
{
    return BiCriterion<FirstCriterion, SecondCriterion>(first, second);
};

Если захочу найти мужиков в возрасте 30 лет, то

auto criterion = AND(AgeCriterion(30), GenderCriterion(Male));

std::multiset завернул в класс UserDataBase:

class UserDataBase
{
    using SetComparator = std::function<bool(User *, User *)>;
    using Multiset = std::multiset<User *, SetComparator>;

    std::vector<User *> m_users;
    std::map<int, Multiset> m_searchMap;

public:

    using SearchResultIteratorPtr = std::unique_ptr<ISearchResultIterator>;

    UserDataBase() = default;
    ~UserDataBase();

    template<typename Criterion>
    void registryCriterion(const Criterion &criterion)
    {
        m_searchMap[criterion.signature()] = Multiset(criterion);
    }

    void append(const User &user)
    {
        auto item = new User(user);
        m_users.push_back(item);

        for (auto iter = m_searchMap.begin();
             iter != m_searchMap.end();
             ++iter) {
            iter->second.insert(item);
        }
    }

    template<typename Criterion>
    SearchResultIteratorPtr search(const Criterion &criterion) const
    {
        typedef SearchResultIterator<Multiset::const_iterator, Criterion> ResultIterator;
        const auto end = Multiset::const_iterator();
        SearchResultIteratorPtr iterator(new ResultIterator(end, end, criterion));

        User pattern;
        pattern = criterion.patternForSearch();

        if (m_searchMap.count(criterion.signature())) {

            const auto &set = m_searchMap.at(criterion.signature());
            auto iter = set.find(&pattern);
            if (iter != set.end()) {
                iterator.reset(new ResultIterator(iter, set.end(), criterion));
            }
        }

        return iterator;
    }
};

Вроде все просто. Сперва регистрируем критерии поиска, потом добавляем элементы:

UserDataBase base;
base.registryCriterion(AgeCriterion());
base.registryCriterion(GenderCriterion());

base.registryCriterion(AND(AgeCriterion(), GenderCriterion()));
base.registryCriterion(AND(CityCriterion(), GenderCriterion()));
//..
for (int i = 0; i < MAX_USERS; ++i) {
    User usr;
    ifs >> usr;
    base.append(usr);
}

В самом методе поиска нет ничего интересного. Только возврящается указатель на ISearchResultIterator, что бы срезать информацию о типе.

Итератор это обертка над итератором std::multiset, хранящий критерий поиска:

template<typename MultisetIterator, typename Criterion>
class SearchResultIterator: public ISearchResultIterator
{
public:

    SearchResultIterator(MultisetIterator iter,
                         MultisetIterator end,
                         const Criterion &criterion)
        : m_iter(iter), m_end(end), m_criterion(criterion)
    {

    }

    bool isValid() const noexcept final
    {
        return (m_iter != m_end)
            && (m_criterion.matched(**m_iter));
    }

    bool next() noexcept final
    {
        if (isValid()) {
            ++m_iter;
            return m_criterion.matched(**m_iter);
        }
        else {
            return false;
        }
    }

    const User &user() const noexcept final
    {
        if (isValid()) {
            return **m_iter;
        }
        else {
            return m_emptyUser;
        }
    }

private:

    MultisetIterator m_iter;
    MultisetIterator m_end;

    Criterion m_criterion;
    User m_emptyUser;
};

Идем по std::multiset пока не дошли до конца и элементы сооветсвтуют критерию поиска.
Использование выглядит так:

auto iterator = base.search(AND(AgeCriterion(30), GenderCriterion(Male)));
if (iterator->isValid()) {
    printReuslt(iterator);
}
//... 
void printReuslt(std::unique_ptr<ISearchResultIterator> &iter)
{
    int cnt = 1;

    std::vector<User> users;
    users.reserve(100);

    do {
        users.push_back(iter->user());
        if (cnt == 100) {
            break;
        }
        ++cnt;
    }
    while (iter->next());

    std::sort(users.begin(), users.end(), timeSort);

    std::cout << std::setw(8) << "USR ID"
              << std::setw(12) << std::left << " REG"
              << std::setw(5) << std::right << "GNDG"
              << std::setw(6) << "CITY"
              << std::setw(12) << "BIRTHDAY" << std::endl;

    for (const auto &usr: users) {
        std::cout << std::setw(8) << usr.id
                  << std::setw(12) << usr.timeReg
                  << std::setw(5) << usr.gender
                  << std::setw(6) << usr.cityId
                  << std::setw(12) << usr.birthday << std::endl;
    }
}

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

Вроде получилось не так много кода, который вполне можно написать за 4 часа.