Ich brauche eine etwas andere multimap

Question

Ich bin für eine C ++ Container-Klasse, dass viel wie ein Multimap ist, aber etwas anders. Der Behälter würde speichern Paare von Strings. Aber wenn ich Gegenstände aus dem Behälter mit der Taste K abrufen möchte ich alle Elemente finden, wo K beginnt mit dem eigenen Schlüssel des Artikels.

z. Wenn ich die Taste „ABCDE“ Ich mag Produkte mit der Taste „adc“ zu finden und „ABCDE“, aber nicht „abcqz“.

oder in Pseudo-C ++ Form:

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;

Einführung Es ist unwichtig, aber ich brauche einen schnellen Zugriff auf die Elemente. Ist es möglich, dies mit einem normalen Multimap zu tun, indem sie einen speziellen Operator

Dank

Hugo

Answer 1

Ich würde vorschlagen, eine trie .

Grundsätzlich haben Sie einen Baum mit 1 Knoten pro einzigartigen Charakter. Ihr Algorithmus wäre O (m) für beide Lookups und Insertion, wobei m die Länge eines Strings.

So finden Sie Ihr Beispiel mit:

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

Dann müssen Sie folgende trie:

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

eine Lookup tun Sie einfach am Wurzelknoten (Wurzelknoten nicht oben gezeigt) starten, und das nächste Zeichen in der Eingabezeichenfolge folgen. Jedes Mal, wenn Sie einen Knoten erreichen, die ein Datum Ergebnis hat, werden Sie beinhalten, dass als eine Ihrer Ausgabe-Strings.

So eine Suche nach abcde Sie geben würde: „hallo“, „Hallo“, wie man wollte. Es würde Ihnen nicht „Auf Wiedersehen“, weil Sie nicht dieses Ergebnis Knoten durchqueren über hat.

Answer 2

Zuerst mit std :: multimap, man kann nicht eine andere Anordnung zum Einsetzen und Retrieval hat.

Zweitens ist jede totale Ordnung für Ihre Zwecke nicht gut genug, was bedeutet, es wird die Antwort setzt Sie als Intervalle nicht machen.

würde ich entweder für alle Präfixe mit einem Nachschlag suchen jede (Sie kann es durch die Erinnerung an die Länge der nächsten optimieren könnten kürzeren Präfix etc.) oder verwenden Sie einen Trie (sondern eine PATRICIA-Trie, die weniger Platz erfordert).