Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

C++ Hash Table Memoization: Simplifying Dynamic Programming


Sample Code for gcc

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

gcc puts the hashing header files in the ext folder, and uses the __gnu_cxx namespace, isolating the non-standard library extensions into a ghetto of sorts. Both of these are dealt with in the first two lines of the sample code below.

The gcc implementation of hash_map needs two template parameters to handle keys that aren't defined as built-in types: one class that has an operator which returns a hash index given an input key, and a second that returns a boolean value for equality test. I pack both of these into a single class, SampleTraits. The traits class is then passed to the hash_map type definition as the third and fourth template parameters.

When you are defining the hash function, you need to somehow combine hash values for each of the members of your structure. Creating hash keys is somewhat of an art, so I try to use the ones provided by the library writer as the basis for my hash function. In this case I take the hash values for the two members of class Sample and simply XOR them together, which should provide a decent value.

If you are using g++ 4.x, you may be better off using the TR1 unordered_map class. While it is not quite part of the standard yet, it should be soon, and that will insure its future support and compatibility.

#include <ext/hash_map> 
using namespace __gnu_cxx; 
#include <string> 
class Sample { 
public : 
   Sample( int age=-1, const std::string &genre="" ) 
   : mAge( age ) 
   , mGenre( genre ){} 
   int mAge; 
   std::string mGenre; 
}; 
struct SampleTraits 
{ 
   size_t operator()( const Sample& that ) const 
   { 
      return hash<int>()( that.mAge ) ^ 
        hash<const char *>()( that.mGenre.c_str() ); 
   } 
   bool operator()( const Sample &that1, const Sample& that2 ) const 
   { 
      return that1.mAge == that2.mAge && that1.mGenre == that2.mGenre; 
   } 
}; 
int main() 
{ 
   hash_map<Sample, 
      int, 
      SampleTraits, 
      SampleTraits< AnnualBooksReadByAgeAndGenre; 
      AnnualBooksReadByAgeAndGenre[ Sample( 15, "Fantasy" ) ] = 15; 
      AnnualBooksReadByAgeAndGenre[ Sample( 18, "Sports" ) ] = 12; 
      AnnualBooksReadByAgeAndGenre[ Sample( 35, "Mystery" ) ] = 17; 
      AnnualBooksReadByAgeAndGenre[ Sample( 42, "Romance" ) ] = 125; 
   return 1; 
} 

Visual C++ .NET 2003/2005

Microsoft's compilers have similar issues, but deal with them differently. (That's the problem with non-standard features.)

Although the hash_map header file is accessed from the normal C++ header folder, the class itself, as was the case with g++, is defined in a different namespace, stdext. Again, that is dealt with in the first two lines of the sample code.

The remaining two issues are resolved by defining a global hash_value class that has an operator that returns a hash key for a given object of class Sample, and a global comparison operator that is used to test for equality of two objects of class Sample. (It is not unusual to use the less-than operator to test for equality, by testing both a > b and a < b, we determine whether the objects are equal or not.)

#include <hash_map> 
using namespace stdext; 
#include <string> 
class Sample { 
public : 
  Sample( int age=-1, const std::string &genre="" ) 
    : mAge( age ) 
    , mGenre( genre ){} 
    int mAge; 
    std::string mGenre; 
}; 
   namespace stdext { 
     size_t hash_value( const Sample& that ) 
     { 
        return hash_value( that.mAge ) ^ hash_value( that.mGenre ); 
     } 
}; 
bool operator<( const Sample& that1, const Sample& that2) 
{ 
    return that1.mAge <that2.mAge && that1.mGenre <that2.mGenre; 
} 
int main() 
{ 
    hash_map<Sample,int> AnnualBooksReadByAgeAndGenre; 
    AnnualBooksReadByAgeAndGenre[ Sample( 15, "Fantasy" ) ] = 15; 
    AnnualBooksReadByAgeAndGenre[ Sample( 18, "Sports" )  ] = 12; 
    AnnualBooksReadByAgeAndGenre[ Sample( 35, "Mystery" ) ] = 17; 
    AnnualBooksReadByAgeAndGenre[ Sample( 42, "Romance" ) ] = 125; 
    return 1; 
} 

Some Notes on Usage

The member functions of most implementations of hash_map will be identical to those of the standard std::map container. Storing an entry in a hash_map can be done using an overloaded operator that makes the container look like an associative array:

hash_map<std::string,int>my_map; 
 ... 
my_map[ "foo" ] = 42; 

Looking up a value from the table is done using a call to hash_map::find(). This method takes a reference to a key as its argument, and returns an iterator which points to the end of the container on failure, or to a key/value pair on success. The pair is stored in an std::pair object, which allows you to access the elements with the first and second members of that object:

hash_map<std::string,int>::iterator ii = my_map.find( "bar" ); 
if ( ii == my_map.end() ) 
    std::cout <<"Couldn't find an entry for 'bar'\n"; 
else 
    std::cout <<"Entry in map for key '" 
              <<ii->first 
              <<" is " 
              <<ii->second 
              <<"\n"; 


Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.