What is the best way to use a HashMap in C++?
c++, hashmap
Solution
The standard library includes the ordered and the unordered map (`std::map` and `std::unordered_map`) containers. In an ordered map (`std::map`) the elements are sorted by the key, insert and access is in O(log n). Usually the standard library internally uses red black trees for ordered maps. But this is just an implementation detail. In an unordered map (`std::unordered_map`) insert and access is in O(1). It is just another name for a hashtable.
An example with (ordered) `std::map`:
#include <map>
#include <iostream>
#include <cassert>
int main(int argc, char **argv)
{
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';
return 0;
}
Output:
23
Key: hello Value: 23
If you need ordering in your container and are fine with the O(log n) runtime then just use `std::map`.
Otherwise, if you really need a hash-table (O(1) insert/access), check out `std::unordered_map`, which has a similar to `std::map` API (e.g. in the above example you just have to search and replace `map` with `unordered_map`).
The `unordered_map` container was introduced with the C++11 standard revision. Thus, depending on your compiler, you have to enable C++11 features (e.g. when using GCC 4.8 you have to add `-std=c++11` to the CXXFLAGS).
Even before the C++11 release GCC supported `unordered_map` - in the namespace `std::tr1`. Thus, for old GCC compilers you can try to use it like this:
#include <tr1/unordered_map>
std::tr1::unordered_map<std::string, int> m;
It is also part of boost, i.e. you can use the corresponding boost-header for better portability.
Problem
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.