用于快速搜索的二进制数据结构
我正在寻找一种能够非常快速搜索的二进制数据结构（树、列表）。我只会在程序的开头/结尾一次性添加/删除项目。所以它将是固定大小的，因此我并不真正关心插入/删除速度。基本上我正在寻找的是一种提供快速搜索并且不使用太多内存的结构。
谢谢
I'm looking for a binary data structure (tree, list) that enables very fast searching. I'll only add/remove items at the beginning/end of the program, all at once. So it's gonna be fixed-sized, thus I don't really care about the insertion/deletion speed. Basically what I'm looking for is a structure that provides fast searching and doesn't use much memory.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
此处查找 Boost C++ 库中的 Unordered 集。与搜索时间为 O(log n) 的红黑树不同，无序集基于哈希，平均提供 O(1) 搜索性能。
Look up the Unordered set in the Boost C++ library here. Unlike red-black trees, which are O(log n) for searching, the unordered set is based on a hash, and on average gives you O(1) search performance.
一个不容忽视的容器是排序的 std::vector。
它肯定会在内存消耗方面获胜，特别是如果您可以预先保留（）正确的数量。
One container not to be overlooked is a sorted std::vector.
It definitely wins on the memory consumption, especially if you can reserve() the correct amount up front.
因此键可以是简单类型，值是由五个指针组成的小型结构。
只有 50 个元素，它开始变得足够小，以至于 Big-O 理论性能可能会被算法或结构的固定时间开销所掩盖或至少受到可测量的影响。
例如，具有线性搜索的数组或向量通常是最快的，其元素少于十个，因为其结构简单且内存紧张。
我会包装容器并定时在其上运行真实数据。从STL的向量开始，转到标准STL映射，升级到unordered_map，甚至可能尝试Google的dense或sparse_hash_map：
http://google-sparsehash.googlecode.com/svn/trunk/doc /性能.html
So the key can be a simple type and the value is a smallish structure of five pointers.
With only 50 elements it starts getting small enough that the Big-O theoretical performance may be overshadowed or at least measurable affected by the fixed time overhead of the algorithm or structure.
For example an array a vector with linear search is often the fastest with less than ten elements because of its simple structure and tight memory.
I would wrap the container and run real data on it with timing. Start with STL's vector, go to the standard STL map, upgrade to unordered_map and maybe even try Google's dense or sparse_hash_map:
http://google-sparsehash.googlecode.com/svn/trunk/doc/performance.html
一种有效的（尽管有点令人困惑）算法是红黑树。
在内部，C++ 标准库使用红黑树来实现
std::map- 请参阅 这个问题One efficient (albeit a teeny bit confusing) algorithm is the Red-Black tree.
Internally, the c++ standard library uses Red-Black trees to implement
std::map- see this questionstd::map和哈希映射是不错的选择。他们还有构造函数来简化一次性构造。哈希映射将关键数据放入返回数组索引的函数中。这可能比
std::map慢，但只有分析才能告诉我们。我的偏好是 std::map，因为它通常以二叉树的形式实现。
The
std::mapand hash map are good choices. They also have constructors to ease one time construction.The hash map puts key data into a function that returns an array index. This may be slower than an
std::map, but only profiling will tell.My preference would be
std::map, as it is usually implemented as a type of binary tree.最快的往往是 trei/trie。我实现的速度比 std::unordered_map 快 3 到 15 倍，但它们往往会使用更多的内存，除非您使用大量元素。
The fastest tends to be a trei/trie. I implemented one 3 to 15 times faster than the std::unordered_map, they tend to use more ram unless you use a large number of elements though.