J'ai besoin d'un multimap légèrement différent

Question

Je cherche une classe de conteneur C++, c'est un peu comme un multimap, mais légèrement différent. Le conteneur stockera des paires de chaînes. Mais quand je récupère des éléments du conteneur en utilisant la clé K, je veux trouver tous les éléments où K commence par la clé de l'élément.

E.G. Si j'utilise la touche "abcde" je veux trouver des éléments avec la clé "adc" et "abcde", mais pas "abcqz".

ou en pseudo C la forme de:

multimap2<string, string> myMultiMap; 
myMultiMap.insert(pair("abcde", "hello")); 
myMultiMap.insert(pair("abc", "Hi")); 
myMultiMap.insert(pair("abcqz", "goodbye")); 

// prints 2 
cout << myMultiMap.count("abcde") << endl; 

// prints "hello" and "Hi" 
cout << myMultiMap.everything_which_matches("abcde") << endl; 

// prints "Hi" 
cout << myMultiMap.everything_which_matches("abc") << endl; 

// prints "goodbye" 
cout << myMultiMap.everything_which_matches("abcqz") << endl; 

temps d'insertion est sans importance, mais je besoin d'un accès rapide aux éléments. Est-il possible de le faire avec un Multimap normal en créant un opérateur spécial <? Mon intuition est que j'aurais besoin de l'opérateur < normal pour l'insertion, et un spécial pour la récupération.

grâce

Hugo

Answer 1

Je suggère d'utiliser un trie.

Fondamentalement, vous avez un arbre avec 1 nœud par caractère unique. Votre algorithme serait O (m) pour les recherches et l'insertion, où m est la longueur d'une chaîne.

Ainsi votre exemple avec:

"abcde", "hello" 
"abc", "Hi" 
"abcqz", "goodbye" 

Ensuite, vous auriez la structure arborescente suivante:

 a 
     | 
     b 
     | 
     c  (c holds data of hi) 
    /\ 
    d q 
    | | 
    e z (z holds data of goodbye) (e holds data of hello) 

Pour faire une recherche, vous commencez simplement au niveau du nœud racine (nœud racine non illustré ci-dessus) et suivez le caractère suivant dans votre chaîne d'entrée. Chaque fois que vous atteignez un noeud contenant un résultat de données, vous l'incluez dans l'une de vos chaînes de sortie.

Donc, une recherche sur abcde vous donnerait: "salut", "bonjour" comme vous le vouliez. Cela ne vous donnerait pas «au revoir» parce que vous n'avez pas traversé ce nœud de résultat.

Answer 2

D'abord, avec std :: multimap, vous ne pouvez pas avoir un ordre différent pour l'insertion et la récupération. Deuxièmement, toute commande totale n'est pas suffisante pour votre usage, ce qui signifie qu'elle ne rendra pas les ensembles de réponses souhaités comme des intervalles. Je voudrais soit chercher tous les préfixes avec une recherche chacun (vous pouvez l'optimiser en se souvenant de la longueur du prochain préfixe plus court, etc.) ou utiliser un Trie (mais plutôt un trie PATRICIA qui demande moins d'espace).