什麼數據結構用於範圍搜索？

Question

試圖製作一個簡單的程序來編目。像這樣的東西，例如：

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

最終，我希望能夠根據範圍做標題搜索。因此，用戶可以指定顯示標題以「aa」到「be」開頭的書籍結果。理想情況下，搜索平均情況是對數的。

在STL中有什麼可以幫助我嗎？否則，最好的辦法是什麼？

謝謝！

Answer 1

您可以將它們存儲在std::set中，並使用std::lower_bound和std::upper_bound來查找範圍（並且是，應該是對數）。要做到這一點，您需要定義operator<以僅在您關心的字段（本例中爲title）上進行操作。

如果你（幾乎）總是處理標題爲關鍵，你可能更願意使用一個std::map<std::string, info>，與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的目錄編號。幾乎沒有任何標準的編號系統（例如杜威小數，國會圖書館，國際標準書號）將很好地存儲在整數中。

Answer 2

你可以把你的元素放在std::set。問題在於，您可能希望用戶能夠按照標題和作者進行搜索。解決方案只是維護兩套，但如果您的數據發生更改，則維護起來可能會非常棘手，您需要兩倍的空間。

你總是可以寫一些類似於Trie的東西，但是你的數據可能會改變，並且保持對數搜索時間變得更困難。您可以實現任何種類的Self-balancing binary search tree，但這基本上就是set是 - Red-black tree。寫一個不是最簡單的任務，但是......

更新：您可以散列一切，實現了某種形式的Rabin-Karp string search algorithm的，但你應該知道，有可能的碰撞，如果你做到這一點。您可以通過雙重哈希和/或使用良好的哈希函數來降低其概率。

Answer 3

您可以使用trie [擴大@smarinov這裏建議]：

尋找一套相關的詞與一個共同的前綴是在特里farily容易，只要按照指針的線索，直到你到達表示節點所需的通用前綴。此節點是包含所需通用前綴的trie。

在你的榜樣，你將需要：

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

預計該OP的複雜性是O(|S|)，其中|S|是常見的前綴的長度。請注意，任何算法預計都不會更好，因爲比較操作取決於字符串的長度，所以算法實際上是O(|S| * logn)。