unordered_multimap<string, string> to map<string, string> soft search, How to do such thing and how to preprocessed maps for faster search?

Question

We have a map<boost::shared_ptr<service>, rules> service_map where rules is

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

In my case of rules are pairs from of http request headers and arguments, for example in one such unordered_multimap we could find Accept-Language : FR and Accept-Language : US.

Each boost::shared_ptr<service> is some instance of class that inherits from service class.

I fill this map of servise <-> rules on fly with services and rules (from some shared libs and some text files with rules).

Now I am given instances of data

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

For each given data object I need to find most relevant service from service_map and call its service->inherited_method();

By relevant here we mean one whose rules fit to given data mostly. For example if we have in rules Accept-Language : FR and Accept-Language : US than if data contains pair Accept-Language : fr-FR,ru;q=0.8,en-US;q=0.6,en;q=0.4 we think it is relevant.

What would be best way to preprocess my service_map for faster soft search, and how to implement such search?

Answer 1

This is a tall order, and you'll have to develop some of the logic yourself. However, here's a skeleton solution:

1) Write a function that ranks rules according to their relevance for a given set of data:

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

2) For each piece of data, create a sorted ranking of the rules. For instance, you could keep a bunch of iterators around. Then find the service that matches the most relevant rule set.

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.");
}

I'm supposing that all your rules are kept in RuleCollection rc;, some container of value type rules.

Edit: Fixed multimap element insertion -- multimap does not have a [] access operator for obvious reasons.