少し異なるマルチマップが必要です

StackOverflow https://stackoverflow.com/questions/455251

質問

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

E.G。キー<！> quot; abcde <！> quotを使用する場合;キー<！> quot; adc <！> quot;を持つアイテムを検索したいおよび<！> quot; abcde <！> quot;が、<！> quot; abcqz <！> quot;ではありません。

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

挿入時間は重要ではありませんが、アイテムにすばやくアクセスする必要があります。特別な<！> lt;を作成することにより、通常のマルチマップでこれを行うことは可能ですか？オペレーター？私の考えでは、通常の<！> lt;挿入用の演算子、および取得用の特別な演算子。

ありがとう

ヒューゴ

役に立ちましたか？

解決

トライを使用することをお勧めします。

基本的に、一意の文字ごとに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を検索すると、<！> quot; hi <！> quot;、<！> quot; hello <！> quot;あなたが望むように。 <！> quot;さよなら<！> quot;その結果ノードを横断しなかったからです。

他のヒント

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

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

1回の検索ですべてのプレフィックスを検索するか（次の短いプレフィックスの長さを覚えて最適化できます）、トライを使用します（スペースをあまり必要としないPATRICIAトライ）。 >

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top