Binary data structure for fast searching

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/de开发者_如何学Goletion speed. Basically what I'm looking for is a structure that provides fast searching and doesn't use much memory.

Thanks

---

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.

---

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.

---

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

---

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 question

---

The std::map and 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.

---

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.