範囲検索にはどのようなデータ構造を使用しますか？

Question

書籍をカタログする簡単なプログラムを作成しようとしています。例えば、このような何かは、：

struct book{ 
    string author; 
    string title; 
    int catalogNumber; 
} 

最終的に、私は範囲に基づいて、タイトル検索を行うことができるようにしたいです。したがって、ユーザは、タイトルが "aa"で始まって "be"で始まる書籍の結果を表示するように指定することができる。理想的には、検索平均の場合は対数です。

STLには私を助ける何かがありますか？それ以外の場合は、これを行う最善の方法は何ですか？

ありがとうございます！

Answer 1

std::setに保存し、範囲を見つけるにはstd::lower_boundとstd::upper_boundを使用してください（対数でなければなりません）。これを行うには、気になるフィールド（この場合はtitle）で操作するには、operator<を定義する必要があります。

あなたは（事実上）いつものように定義されたinfoで、あなたはstd::map<std::string, info>を使用することを好むかもしれませんが、キーとしてタイトルを処理している場合：など、

struct info { 
    string author; 
    int catalogNumber; 

    info(string a, int c) : author(a), catalogNumber(c) {} 
}; 

これは、いくつかの操作が少し楽になります：

books["Moby Dick"] = info("Herman Melville", 1234); 

あなたはタイトルや著者によって検索をサポートしたい場合は（たとえば）ブーストbimapまたはmulti_indexのようなものを使用することを検討してください。何が価値があるために

、私はまた、stringを使用して代わりのカタログ番号についてintに深刻考えを与えるだろう。標準的なナンバリングシステム（例えば、Dewey decimal、議会図書館、ISBN）のほとんどはintに非常にうまく格納されません。

Answer 2

あなたの要素はstd::setに入れることができます。その問題は、ユーザーがタイトルだけでなく著者によっても検索できるようにしたいということです。解決策は2つのセットを維持することだけですが、データが変更された場合は、これを維持するのが難しく、2倍のスペースが必要になります。

いつでもTrieのように書くことができますが、データが変更される可能性があり、対数検索時間を維持するのが難しくなります。任意の種類のSelf-balancing binary search treeを実装できますが、それは基本的にはsetです - Red-black treeです。 1を書くことは最も簡単な作業ではありません、しかし...

更新：あなたはすべてをハッシュしRabin-Karp string search algorithmのいくつかのフォームを実装していますが、あなたがそれを行う場合は衝突の可能性があることに注意する必要がありますすることができます。ダブルハッシュや良好なハッシュ関数を使用して、1つの確率を下げることができます。

Answer 3

あなたは[こちら@smarinovの提案を拡大] trieを使用することができます。共通のプレフィックスと関連する単語の集合を見つける

あなたが表すノードに到達するまで、ちょうどトライ内のポインタをたどる、トライにfarily簡単です。必要な共通プレフィックスこのノードは、必要な共通プレフィックスを含むトライです。あなたの例では

、あなたが必要となります。

range("aa","be") = prefix("a") + (prefix("b[a-e]") 

このOPに予想される複雑さは|S|が共通のプレフィックスの長さである、O(|S|)です。比較演算子は文字列の長さに依存するため、アルゴリズムは実際にはO(|S| * logn)であることに注意してください。