unordered_multimap <string, string> pour mapper <string, string> soft search, Comment faire une telle chose et comment faire des cartes prétraitées pour une recherche plus rapide?

Question

Nous avons un map<boost::shared_ptr<service>, rules> service_map où les règles est

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

Dans mon cas, des règles sont des paires de la demande http headers et arguments, par exemple dans un tel unordered_multimap nous pourrions trouver Accept-Language : FR et Accept-Language : US. Chaque boost::shared_ptr<service> est une instance de classe qui hérite de service class.

Je remplis cette carte de servise < -> règles à la volée avec les services et les règles (à partir de certaines bibliothèques partagées et certains fichiers texte avec des règles).

Maintenant, je suis cas donné de data

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

Pour chaque objet à data Je dois trouver les plus pertinentes service de service_map et appeler sa service->inherited_method();

Par pertinent ici, nous entendons une dont les règles s'adapter à données données principalement. Par exemple si nous avons dans les règles Accept-Language : FR et Accept-Language : US que si les données contiennent la paire Accept-Language : fr-FR,ru;q=0.8,en-US;q=0.6,en;q=0.4 nous pensons qu'il est pertinent.

Quelle serait la meilleure façon de pré-traiter mon service_map pour une recherche rapide plus rapide, et comment implémenter une telle recherche?

Answer 1

Ceci est une commande importante, et vous devrez développer vous-même une partie de la logique. Cependant, voici une solution squelette:

1) une fonction qui se classe règles en fonction de leur pertinence pour un ensemble de données:

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

2) Pour chaque donnée, créer un classement triée des les règles. Par exemple, vous pourriez garder un tas d'itérateurs autour. Ensuite, trouvez le service correspondant à l'ensemble de règles le plus pertinent.

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

Je supposant que toutes vos règles sont conservés dans RuleCollection rc;, certains conteneurs de type valeur rules.

Édition: Insertion d'élément multimap fixe - multimap n'a pas d'opérateur d'accès [] pour des raisons évidentes.