Ho bisogno di una multimappa leggermente diversa

Question

Sto cercando una classe contenitore C++, che assomigli molto a una multimappa, ma leggermente diversa.Il contenitore memorizzerebbe coppie di stringhe.Ma quando recupero gli elementi dal contenitore utilizzando la chiave K, voglio trovare tutti gli elementi in cui K inizia con la chiave dell'elemento.

PER ESEMPIO.Se utilizzo la chiave "abcde" voglio trovare gli elementi con la chiave "adc" e "abcde", ma non "abcqz".

O in forma 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;

Il tempo di inserimento non è importante, ma ho bisogno di un accesso rapido agli elementi.È possibile farlo con un normale Multimap creando un operatore < speciale?La mia impressione è che avrei bisogno del normale < operatore per l'inserimento e di uno speciale per il recupero.

Grazie

Ugo

Answer 1

Suggerirei di utilizzare a prova.

Fondamentalmente hai un albero con 1 nodo per personaggio unico.Il tuo algoritmo sarebbe O(m) sia per le ricerche che per l'inserimento, dove m è la lunghezza di una stringa.

Quindi seguendo il tuo esempio con:

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

Quindi avresti il ​​seguente tentativo:

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

Per eseguire una ricerca è sufficiente iniziare dal nodo radice (nodo radice non mostrato sopra) e seguire il carattere successivo nella stringa di input.Ogni volta che raggiungi un nodo che ha un risultato di dati, lo includerai come una delle stringhe di output.

Quindi una ricerca per abcde ti darebbe:"ciao", "ciao" come volevi.Non ti darebbe "arrivederci" perché non hai attraversato quel nodo del risultato.

Answer 2

Innanzitutto, con std :: multimap, non è possibile disporre di un ordine diverso per l'inserimento e il recupero.

In secondo luogo, qualsiasi ordine totale non è abbastanza buono per il tuo scopo, il che significa che non renderà i set di risposte che desideri come intervalli.

Vorrei cercare tutti i prefissi con una ricerca ciascuno (potresti ottimizzarlo ricordando la lunghezza del prossimo prefisso più corto ecc.) o usare un Trie (ma piuttosto un trie PATRICIA che richiede meno spazio).