Мне нужна немного другая мультикарта - PullRequest
Новая
       21

Мне нужна немного другая мультикарта

2 голосов
/ 18 января 2009

Я ищу контейнерный класс C ++, он очень похож на мультикарту, но немного отличается. Контейнер будет хранить пары строк. Но когда я получаю элементы из контейнера с помощью ключа K, я хочу найти все элементы, где K начинается с собственного ключа элемента.

например. Если я использую ключ «abcde», я хочу найти элементы с ключами «adc» и «abcde», но не «abcqz».

Или в псевдо-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;

Время вставки неважно, но мне нужен быстрый доступ к предметам. Можно ли сделать это с помощью обычной Multimap, создав специальный оператор <? Я догадываюсь, что мне понадобится обычный оператор <для вставки и специальный оператор для извлечения. </p>

спасибо

Hugo

Ответы [ 2 ]

11 голосов
/ 18 января 2009

Я бы предложил использовать три .

В основном у вас есть дерево с 1 узлом на каждого уникального персонажа. Ваш алгоритм будет O (m) как для поиска, так и для вставки, где m - длина строки.

Итак, следуя вашему примеру с: 

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

Тогда у вас будет следующее дерево: 

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

Чтобы выполнить поиск, вы просто начинаете с корневого узла (корневой узел не показан выше) и следите за следующим символом во входной строке. Каждый раз, когда вы достигаете узла, на котором есть результат данных, вы будете включать его в качестве одной из ваших выходных строк.

Так что поиск abcde дал бы вам: "привет", "привет", как вы хотели. Это не даст вам «до свидания», потому что вы не прошли через этот узел результатов.

1 голос
/ 18 января 2009

Во-первых, с помощью std :: multimap вы не можете иметь другой порядок вставки и извлечения.

Во-вторых, любой общий порядок не подходит для вашей цели, что означает, что он не будет отображать наборы ответов, которые вы хотите, в качестве интервалов.

Я бы либо искал все префиксы с одним поиском каждый (вы могли бы оптимизировать его, запомнив длину следующего более короткого префикса и т. Д.), Либо использовал бы Trie (а скорее три, PATRICIA, который требует меньше места).

...