Necesito un multimapa ligeramente diferente

Question

Estoy buscando una clase de contenedor C ++, que se parece mucho a un multimapa, pero un poco diferente. El contenedor almacenaría pares de cuerdas. Pero cuando recupero elementos del contenedor con la tecla K, quiero encontrar todos los elementos donde K comienza con la propia clave del elemento.

E.G. Si uso la tecla & Quot; abcde & Quot; Quiero encontrar elementos con la tecla & Quot; adc & Quot; y " abcde " ;, pero no " abcqz " ;.

O en forma de 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;

El tiempo de inserción no es importante, pero necesito un acceso rápido a los elementos. ¿Es posible hacer esto con un Multimap normal creando un & Lt especial; ¿operador? Mi presentimiento es que necesitaría el & Lt normal; operador para inserción, y uno especial para recuperación.

gracias

Hugo

Answer 1

Sugeriría usar un trie .

Básicamente tiene un árbol con 1 nodo por carácter único. Su algoritmo sería O (m) tanto para búsquedas como para inserción, donde m es la longitud de una cadena.

Entonces, siguiendo su ejemplo con:

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

Entonces tendría el siguiente trie:

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

Para realizar una búsqueda, simplemente comience en el nodo raíz (el nodo raíz no se muestra arriba) y siga el siguiente carácter en su cadena de entrada. Cada vez que llegue a un nodo que tenga un resultado de datos, lo incluirá como una de sus cadenas de salida.

Entonces, una búsqueda de abcde te daría: " hola " ;, " hola " como quisieras No te daría & Quot; adiós & Quot; porque no atravesó ese nodo de resultados.

Answer 2

Primero, con std :: multimap, no puede tener un orden diferente para la inserción y recuperación.

Segundo, cualquier pedido total no es lo suficientemente bueno para su propósito, lo que significa que no representará los conjuntos de respuestas que desee como intervalos.

Buscaría todos los prefijos con una búsqueda cada uno (podría optimizarlo recordando la longitud del siguiente prefijo más corto, etc.) o usaría un Trie (pero más bien un PATRICIA trie que exige menos espacio).