LINUX.ORG.RU

Выбор структуры данных для матрицы принятия решений

 , ,


1

3

Всех приветствую, прошу совета в выборе оптимальной структуры данных для хранения, выбора и вызова определённых callback-функций (в соответсвии с поступающими аргументами).

В частности, в программу подаются строки, которые сопоставляются с регулярными выражениями, в случае совпадения строки с регулярным выражением вызывается функция. В линейном случае (одного аргумента - паттерна boost::regex) напрашивается структура типа key-value, например так:

typedef std::map<boost::regex, boost::function<void(void)> > regex_callback;

void SuOpenedCallback()
{
}

void SuClosedCallback()
{
}


int main(int argc, char** argv)
{
    //Регулярные выражения для сопоставления
    boost::regex su_opened  ("some_regexp_1"); 
    boost::regex su_closed  ("some_regexp_2"); 

    //Структура данных, хранящая коллбеки
    regex_callback resolver = boost::assign::map_list_of
        (su_opened, boost::bind(&SuOpenedCallback))
        (su_closed, boost::bind(&SuClosedCallback));

    std::string line("some_part_of_/var/log/secure");
    boost::smatch result; 
    
    BOOST_FOREACH(const auto& pair, resolver)
    {
        if(boost::regex_match(line, result, pair.first)
        {
             pair.second();
             break;
        } 
    } 
}

Мой вопрос относительно случая, когда аргументов будет много (не только один boost::regex):

  • Существует ли в С++ типовое решение для структуры типа multiple_keys-value и как там осуществляется перебор ключей? Или же надо писать свой класс, состоящий из нескольких аргументов, и подставлять его в key?
  • Есть ли вообще какие-то шаблоны для такой «многофакторной» матрицы решений?

Благодарю.

Ответ на: комментарий от nanoolinux

и пишешь операторы меньше, равно и хеш для multiple_key

Для unordered_map ЕМНИП operator<() не обязателен.

DELIRIUM ☆☆☆☆☆
()
Ответ на: комментарий от nanoolinux

Вместо map берёшь unordered_map и пишешь операторы меньше, равно и хеш для multiple_key.

То есть в multiple_key подставлять свой составной класс?

vitalyisaev2
() автор топика

Зачем тут map, если тебе не нужно уметь быстро получать значение по ключу, а только итерироваться? Тут нужен простой список типа

std::vector<std::tuple<boost::regex, boost::regex, std::function<void(void)>>> v;

for (auto& i : v) 
{
    if (boost::regex_match(..., get<0>(i)) && boost::regex_match(..., get<1>(i)))
        get<2>(i)();
}

vzzo ★★★
()
Ответ на: комментарий от vzzo

Ну да, согласен, что в простом случае легче просто перебрать все варианты. Но если параметров будет два, развивая этот подход, необходимо ввести вектор векторов (и так далее). И как по ним искать, также перебирать все варианты подряд? Тогда, насколько я понимаю, получается О(n^2)? Если появится третий, то О(n^3)?

vitalyisaev2
() автор топика
Ответ на: комментарий от vitalyisaev2

Да.

Может знатоки буста что-то другое подскажут, я в бусте не силён. Не удивлюсь, если есть какой-нибудь variadic templates в духе multikey_hash_map.

nanoolinux ★★★★
()
Ответ на: комментарий от vitalyisaev2

А как это должно быть в случае нескольких вариантов?

Если есть f: A->B, g: A->C и h: (BxC)->D, и надо посчитать h(f(x), g(x)), то никакой multi_key_map не поможет, так как проход по нему все равно будет требовать |B|*|C| операций.

В этом случае нужно завести что-то вроде

std::vector<std::pair<boost::regex, int>> f, g;
std::vector<std::vector<std::function<void(void)>>> h;
int fx, gh;
for (auto i : f)
    if (boost::match(..., i.first)) fx = i.second;
for (auto i : g)
    if (boost::match(..., i.first)) gx = i.second;
h[fx][gx]();
В этом случае сложность будет |B|+|C|.

vzzo ★★★
()

Или же надо писать свой класс, состоящий из нескольких аргументов

Ничего писать не надо, есть boost::tuple.

no-such-file ★★★★★
()

На что только люди не пойдут чтобы lex (и аналоги) не использовать.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.