I usually use C++ STL 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 STL map implementation is based on trees which provides better performance (O(log n)) than the standard array or STL 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.
Have a look at this blog posting: Comparison of Hash Table Libraries.
See std::hash_map from SGI.
This is included in the STLPort distribution as well.
If you're using a C++ Standard Library with support for TR1 (e.g., GCC 4.0+, or Visual Studio 2008 SP1), then you have access to the <unordered_map> and <unordered_set> headers. These provide classes std::tr1::unordered_map and std::tr1::unordered_set.
Hope it helps!
Edit: I've downvoted all the std::hash_map answers; that's an SGI extension, not really part of the C++ standard. Use the TR1 facilities instead.
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.
hash_map is also supported in GNU's libstdc++.
Dinkumware also supports this, which means that lots of implementations will have a hash_map (I think even Visual C++ delivers with Dinkumware).
If you don't already have unordered_map or unordered_set, they are part of boost.
Here's the documentation for both.
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.
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>