2

C++ コンテナー クラスを探しています。これはマルチマップによく似ていますが、少し異なります。コンテナーには、文字列のペアが格納されます。しかし、キー K を使用してコンテナからアイテムを取得するときは、K がアイテム自身のキーで始まるすべてのアイテムを見つけたいと考えています。

EG キー「abcde」を使用する場合、「abcqz」ではなく、キー「adc」および「abcde」を持つアイテムを検索したい。

または疑似 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;

挿入時間は重要ではありませんが、アイテムにすばやくアクセスする必要があります。特別な < 演算子を作成することにより、通常のマルチマップでこれを行うことは可能ですか? 私の推測では、挿入には通常の < 演算子が必要で、検索には特別な演算子が必要です。

ありがとう

ヒューゴ

4

2 に答える 2

11

tryを使用することをお勧めします。

基本的に、一意のキャラクターごとに 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)

検索を行うには、単純にルート ノード (ルート ノードは上に表示されていません) から開始し、入力文字列の次の文字をたどります。データ結果を持つノードに到達するたびに、それを出力文字列の 1 つとして含めます。

したがって、abcde を検索すると、必要に応じて「こんにちは」、「こんにちは」が返されます。その結果ノードをトラバースしなかったため、「さようなら」はありません。

于 2009-01-18T14:56:11.043 に答える
1

まず、std :: multimapでは、挿入と取得の順序を変えることはできません。

第2に、全順序付けは目的に十分ではありません。つまり、必要な回答セットを間隔としてレンダリングしません。

それぞれ1つのルックアップですべてのプレフィックスを検索するか（次に短いプレフィックスの長さを覚えておくことで最適化できます）、またはTrieを使用します（ただし、必要なスペースが少ないPATRICIAトライ）。

于 2009-01-18T15:25:08.487 に答える