J'ai besoin d'une carte multimédia légèrement différente

Question

Je recherche une classe de conteneur C ++, qui ressemble beaucoup à une carte multiple, mais légèrement différente. Le conteneur stockerait des paires de chaînes. Mais lorsque je récupère des éléments du conteneur à l'aide de la clé K, je souhaite rechercher tous les éléments pour lesquels K commence par la clé propre de l'élément.

E.G. Si j'utilise la clé & Quot; abcde & Quot; Je souhaite rechercher des éléments avec la clé & Quot; adc & Quot; et & "Abcde &"; mais pas & "Abcqz &";.

Ou sous une forme pseudo C ++:

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;

La durée d'insertion n'a pas d'importance, mais j'ai besoin d'un accès rapide aux éléments. Est-il possible de faire cela avec un Multimap normal en créant un & Lt spécial; opérateur? Mon intuition est que j'aurais besoin de la normale & Lt; opérateur pour l'insertion et un spécial pour la récupération.

merci

Hugo

Answer 1

Je suggérerais d'utiliser un trie .

En gros, 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.

Vous suivez donc votre exemple avec:

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

Vous obtiendrez alors le test suivant:

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

Pour effectuer une recherche, vous commencez simplement au nœud racine (le nœud racine n'est pas présenté ci-dessus) et suivez le caractère suivant dans votre chaîne d'entrée. Chaque fois que vous atteignez un nœud contenant un résultat de données, vous l'incluez en tant que chaîne de sortie.

Donc, une recherche sur abcde vous donnerait: & "hi &"; & "hello &"; comme tu voulais. Cela ne vous donnerait pas & "Au revoir &"; parce que vous n'avez pas traversé ce noeud de résultat.

Answer 2

Tout d'abord, avec std :: multimap, vous ne pouvez pas avoir un ordre différent pour l'insertion et la récupération.

Deuxièmement, un ordre total n’est pas suffisant pour votre objectif, ce qui signifie qu’il ne restituera pas les réponses que vous souhaitez sous forme d’intervalles.

Je voudrais rechercher tous les préfixes avec une recherche chacun (vous pouvez l’optimiser en mémorisant la longueur du préfixe le plus court, etc.) ou utiliser un Trie (mais plutôt un trie PATRICIA qui demande moins d’espace).