Hashtable in C++?
-
02-07-2019 - |
Question
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.
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.
OTHER TIPS
If you don't already have unordered_map or unordered_set, they are part of boost.
Here's the documentation for both.
There is a hash_map object as many here have mentioned, but it is not part of the stl. It is a SGI extension, so if you were looking for something in the STL, I think you are out of luck.
std::tr1::unordered_map, in <unordered_map>
if you don't have tr1, get boost, and use
boost::unordered_map in <boost/unordered_map.hpp>
Visual Studio has the class stdext::hash_map
in the header <hash_map>
, and gcc has the class __gnu_cxx::hash_map
in the same header.
See std::hash_map from SGI.
This is included in the STLPort distribution as well.
If you have the TR1 extensions available for yor compiler, use those. If not, boost.org has a version that's quite similar except for the std:: namespace. In that case, put in a using-declaration so you can switch to std:: later.