Eu preciso de um multimap ligeiramente diferente

Question

Eu estou procurando uma classe de contêiner C ++, que é muito parecido com um multimap, mas um pouco diferente. O recipiente que armazena pares de cordas. Mas quando eu recuperar itens do recipiente usando chave K, eu quero encontrar todos os itens onde K começa com a própria chave do item.

por exemplo. Se eu usar a tecla "ABCDE" Quero encontrar itens com chave de "ADC" e "ABCDE", mas não "abcqz".

Ou na pseudo C ++ forma:

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;

tempo

A inserção não é importante, mas eu preciso de acesso rápido aos itens. É possível fazer isso com um Multimap normal, criando um operador

graças

Hugo

Answer 1

Eu sugiro usar um trie .

Basicamente, você tem uma árvore com um nó por personagem único. Seu algoritmo seria O (m) para ambas as pesquisas e de inserção, onde m é o comprimento de uma string.

Assim, seguindo o seu exemplo, com:

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

Em seguida, você teria o seguinte trie:

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

Para fazer uma pesquisa você simplesmente começar no nó raiz (nó raiz não mostrada acima), e siga o próximo caractere em sua cadeia de entrada. Cada vez que você chegar a um nó que tem um resultado de dados, você vai incluir isso como uma das suas cadeias de saída.

Assim, uma busca por abcde iria dar-lhe: "oi", "Olá" como você queria. Não lhe daria "adeus" porque você não fez travessia sobre esse nó resultado.

Answer 2

Em primeiro lugar, com std :: multimap, você não pode ter uma ordenação diferente para a inserção e recuperação.

Em segundo lugar, qualquer ordenação total não é bom o suficiente para a sua finalidade, o que significa que não irá processar os conjuntos de resposta que você quer como intervalos.

Eu seria ou procurar todos os prefixos com um lookup cada (você pode otimizá-lo por lembrar o comprimento do lado mais curto prefixo etc.) ou usar um Trie (mas sim um trie PATRICIA que exige menos espaço).