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

Question

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

Например,G.Если я использую ключ "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;

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

Спасибо

Хьюго

Answer 1

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

По сути, у вас есть дерево с 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 дал бы вам:"привет", "привет", как ты и хотел.Это не дало бы вам "до свидания", потому что вы не пересекли этот результирующий узел.

Answer 2

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

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

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