C++ Cookbook

6.7. Using Hashed Containers

Problem

You are storing keys and values , you need constant-time access to elements, and you don’t need the elements to be stored in sorted order.

Solution

Use one of the hashed associated containers, hash_map or hash_set. Be aware, however, that these are not standard containers specified by the C++ Standard, rather they are extensions that most standard library implementations include. Example 6-8 shows how to use a hash_set.

Example 6-8. Storing strings in a hash_set

#include <iostream>
#include <string>
#include <hash_set>

int main() {

   hash_set<std::string> hsString;
   string s = "bravo";

   hsString.insert(s);
   s = "alpha";
   hsString.insert(s);
   s = "charlie";
   hsString.insert(s);

   for (hash_set<string>::const_iterator p = hsString.begin();
        p != hsString.end(); ++p)
      cout << *p << endl; // Note that these aren't guaranteed
                          // to be in sorted order
}

Discussion

Hashed containers are popular data structures in any language, and it is unfortunate that C++ Standard does not require an implementation to supply them. All is not lost, however, if you want to use a hashed container: chances are that the standard library implementation you are using includes hash_map and hash_set, but the fact that they are not standardized means their interfaces may differ from one standard library implementation to the next. I will describe the hashed containers that are provided in the STLPort standard library implementation.

Tip

STLPort is a free, portable standard library implementation ...