Hashtable in C++?
c++, complexity-theory, dictionary, hashtable, performance
Solution
If you're using C++11, you have access to the `<unordered_map>` and `<unordered_set>` headers. These provide classes `std::unordered_map` and `std::unordered_set`.
If you're using C++03 with TR1, you have access to the classes `std::tr1::unordered_map` and `std::tr1::unordered_set`, using the same headers (unless you're using GCC, in which case the headers are `<tr1/unordered_map>` and `<tr1/unordered_set>` instead).
In all cases, there are corresponding `unordered_multimap` and `unordered_multiset` types too.
Problem
I usually use C++ stdlib map whenever I need to store some data associated with a specific type of value (a key value - e.g. a string or other object). The stdlib map implementation is based on trees which provides better performance (O(log n)) than the standard array or stdlib vector. My questions is, do you know of any C++ "standard" hashtable implementation that provides even better performance (O(1))? Something similar to what is available in the Hashtable class from the Java API.