I know that STL has a HashMap API, but I cannot find any good and thorough documentation with good examples regarding this.
Any good examples will be appreciated.
I know that STL has a HashMap API, but I cannot find any good and thorough documentation with good examples regarding this.
Any good examples will be appreciated.
The STL (currently) only includes a Map - no hash-table (in a map the elements are sorted by the key, insert and access is in O(log n)).
First example:
#include <map>
std::map<std::string, int> m;
m["hello"] = 23;
// check if key is present
if (m.find("world") != m.end())
std::cout << "map contains key world!\n";
// retrieve
std::cout << m["hello"] << '\n';
std::map<std::string, int>::iterator i = m.find("hello");
assert(i != m.end());
std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
If you really need a Hash-Table (O(1) insert/access). Check out unordered_map, which has a similar to std::map API. It is part of tr1 and boost. E.g. current GCC's include it:
#include <tr1/unordered_map>
in the namespace std::tr1, e.g.
std::tr1::unordered_map hash;
Or use the corresponding boost-header for better portability.
A hash_map is an older, unstandardized version of what for standardization purposes is called an unordered_map (currently available as part of TR1, and will be included in C++0x). As the name implies, it's different from std::map primarily in being unordered -- if, for example, you iterate through a map from begin() to end(), you get items in order by key1, but if you iterate through an unordered_map from begin() to end(), you get items in a more or less arbitrary order.
An unordered_map is normally expected to have constant complexity. That is, an insertion, lookup, etc., takes essentially a fixed amount of time, regardless of how many items are in the table. An std::map has complexity that's logarithmic on the number of items being stored -- which means the time to insert or retrieve an item grows, but very slowly, as the map grows larger. For example, if it takes 1 microsecond to lookup one of 1 million items, then you can expect it to take around 2 microseconds to lookup one of 2 million items, 3 microseconds for one of 4 million items, 4 microseconds for one of 8 million items, etc.
From a practical viewpoint, that's not really the whole story though. By nature, a simple hash table has a fixed size. Adapting it to the variable-size requirements for a general purpose container is somewhat non-trivial. As a result, operations that (potentially) grow or shrink the table (e.g., insertion and deletion) are often relatively slow. Lookups, which cannot change the size of the table, are generally much faster. As a result, most hash-based tables tend to be at their best when you do a lot of lookups and relatively few insertions and deletions. For situations where you insert a lot of data, then iterate through the table once to retrieve results (e.g., counting the number of unique words in a file) chances are that an std::map will be just as fast, and quite possibly even faster.
1 Where the order is defined by the third template parameter when you create the map, std::less<T> by default.