unordered_multimapна картумягкий поиск, как сделать такую ​​вещь и как предварительно обработать карты для более быстрого поиска? - PullRequest
Новая
       10

unordered_multimapна картумягкий поиск, как сделать такую ​​вещь и как предварительно обработать карты для более быстрого поиска?

0 голосов
/ 09 июля 2011

У нас есть map<boost::shared_ptr<service>, rules> service_map, где правила 

struct rules
{
boost::unordered_multimap<string, string> set_of_rules_1;
boost::unordered_multimap<string, string> set_of_rules_2;
}

В моем случае правила - это пары из запросов http headers и arguments, например, в одном таком unordered_multimap мы можем найти Accept-Language : FR и Accept-Language : US.

Каждый boost::shared_ptr<service> является некоторым экземпляром класса, который наследуется от service class.

Я заполняю эту карту правил обслуживания <-> на лету службами и правилами (из некоторых общих библиотек и некоторых текстовых файлов с правилами).

Теперь мне даны случаи data

struct data
{
map<string, string> headers;
map<string, string> arguments;
}

Для каждого данного data объекта мне нужно найти наиболее подходящий service из service_map и вызвать его service->inherited_method();

Под релевантным здесь подразумевается тот, чьи правила в основном соответствуют заданным данным. Например, если мы имеем в правилах Accept-Language : FR и Accept-Language : US, то если данные содержат пару Accept-Language : fr-FR,ru;q=0.8,en-US;q=0.6,en;q=0.4, мы думаем, что это уместно.

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

1 Ответ

2 голосов
/ 10 июля 2011

Это сложная задача, и вам придется самостоятельно разрабатывать логику.Однако вот скелетное решение:

1) Напишите функцию, которая ранжирует правила в соответствии с их релевантностью для данного набора данных: 

int relevance(const rules & r, const data & d); // write this

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

typedef RuleCollection::const_iterator rit;

boost::shared_ptr<service> find_service(cosnt data & d, ...)
{
  std::multimap<int, rit> relevant_rules;

  for (rit it = rc.begin(), end = rc.end(); it != end; ++it)
  {
    // relevant_rules[relevance(*it, d)] = it; // sorry, that was nonsense
    relevant_rules.insert(std::make_pair(relevance(*it, d), it));
  }

  for (auto it = relevant_rules.rbegin(), rend = relevant_rules.rend(); it != rend; ++it)
  {
    for (auto st = service_map.begin(), end = service_map.end(); st != end; ++st)
    {
      if (*st->second == *it->second) return st->first;
    }
  }
  throw std::exception("Could not find suitable service.");
}

Я полагаю, что все ваши правила хранятся в RuleCollection rc;, некотором контейнере типа значения rules.

Редактировать: Исправлена ​​вставка элемента мультикарты - в мультикарте нет оператора доступа [] по понятным причинам.

...