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


Hash Table Refresher

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

Hash tables were part of the Standard Template Library when the language standard was ratified in 1998. And while most of the Standard Template Library was incorporated into the standard library at that time, the hash_set and hash_map classes were excluded. According to Bjarne Stroustroup Evolving a Language In and For the Real World: C++ 1991-2006:

"they would have been in C++98 had we had the time to do a proper detailed design and specification job. There was no doubt that a hash_map was needed as an alternative to map for large tables where the key was a character string and we could design a good hash function. In 1995, Javier Barreirro, Robert Fraley and David Musser tried to get a proposal ready in time for the standard and their work became the basis for many of the later hash_maps [8]. The committee didn't have the time, though..."

While these containers will be added to the standard library under the awkward names unordered_map and unordered_set when TR1 is adopted, there is no reason we have to wait that long. Despite the fact that they are missing from the standard, virtually every modern C++ compiler has adopted a reasonable variant of hash_map and hash_set.

The hash_map container does a great job of memoization as described in this article, with a caveat. As I said earlier, you'll need the key to your hash table to be some subset of the input parameters. That's all fine if your key is a single value using a built-in type, such as int, a std::string, or a pointer. These key values are supported implicitly by most implementations of hash_map.

Things get a little more complicated if you are using multiple values or your own structures as a key into the map. Owing to the lack of a standard, implementing non-standard keys requires slightly different techniques, depending on your compiler.

I'll give you examples here that work with the two compilers you are most likely to encounter: Visual C++ .NET 2003/2005, or gcc 3.x.

Let's say you're doing a study tracking peoples reading habits by age, and you want to implement the following code:

class Sample { 
public :
  Sample( int age=-1, const std::string &genre="" )
  : mAge( age )
  , mGenre( genre ){}
  int mAge;
  std::string 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;
}

You won't be able to compile this code as-is, for at least three reasons:

  1. You need to include the correct header file, which unfortunately differs depending on which compiler you are using.
  2. You need to hoist the hash_map name into your namespace.
  3. You need to define the hash function and at least one comparison function for the key class, Sample.

Item 3 is only needed if you are using something other than a basic type for your class, and it's the trickiest. Defining the comparison is necessary so that the hashing library code can verify key equality during lookups or collisions.

In both cases, the function is usually pretty easy to write -- you just compose it using existing functions. Examples for Microsoft and gcc compilers circa 2007 are given below.


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.