试图制作一个简单的程序来编目。像这样的东西，例如：什么数据结构用于范围搜索？
struct book{
string author;
string title;
int catalogNumber;
}
最终，我希望能够根据范围做标题搜索。因此，用户可以指定显示标题以“aa”到“be”开头的书籍结果。理想情况下，搜索平均情况是对数的。
在STL中有什么可以帮助我吗？否则，最好的办法是什么？
谢谢！
您可以将它们存储在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的目录编号。几乎没有任何标准的编号系统（例如杜威小数，国会图书馆，国际标准书号）将很好地存储在整数中。
你可以把你的元素放在std::set。问题在于，您可能希望用户能够按照标题和作者进行搜索。解决方案只是维护两套，但如果您的数据发生更改，则维护起来可能会非常棘手，您需要两倍的空间。
你总是可以写一些类似于Trie的东西，但是你的数据可能会改变，并且保持对数搜索时间变得更困难。您可以实现任何种类的Self-balancing binary search tree，但这基本上就是set是 - Red-black tree。写一个不是最简单的任务，但是......
更新：您可以散列一切，实现了某种形式的Rabin-Karp string search algorithm的，但你应该知道，有可能的碰撞，如果你做到这一点。您可以通过双重哈希和/或使用良好的哈希函数来降低其概率。
这就是我正在想的...两套。我希望能有更好的东西，但仍然非常简单！哈哈谢谢！ – 2012-03-20 15:27:02
您可以使用trie [扩大@smarinov这里建议]：
寻找一套相关的词与一个共同的前缀是在特里farily容易，只要按照指针的线索，直到你到达表示节点所需的通用前缀。此节点是包含所需通用前缀的trie。
在你的榜样，你将需要：
range("aa","be") = prefix("a") + (prefix("b[a-e]")
预计该OP的复杂性是O(|S|)，其中|S|是常见的前缀的长度。请注意，任何算法预计都不会更好，因为比较操作取决于字符串的长度，所以算法实际上是O(|S| * logn)。
+1，因为目录编号点！ – 2012-03-20 15:29:07
值得注意的是（通过Scott Meyers，Effective STL）你可以通过排序后的向量获得更好的性能，如果你通常不使用插入查找插入。也就是说，如果您不会因为必须定期重新排列载体而失败，那么您可能从载体更小且更本地化的事实中获益。 – Chowlett 2012-03-20 15:32:43