O'Reilly logo

C++ Cookbook by Jeff Cogswell, Jonathan Turkanis, Christopher Diggins, D. Ryan Stephens

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required