tags:

views:

79

answers:

2

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.

+2  A: 

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.

maxschlepzig
While _the_ standard library does not have a hash table-based container, almost all implementations include `hash_map` from the SGI STL in some form or another.
James McNellis
A: 

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.

Jerry Coffin