Channels ▼
RSS

C/C++

User-Defined Hash Functions for Unordered Maps in C++0x


Method 4 — Specializing std::hash

When you use unordered_map with all the default class parameters, it tries to use a function object of type std::hash<Key> to create your hash keys. As discussed way back at the start of this program, this doesn't work in many cases because nobody bothered to create a specialization of the hash object for your specific class. In many cases, this is because your specific class had not been invented yet.

It stands to reason that if you are providing a class that will be used by other people, it might be nice to actually create the instances of the hash class for your class. When you do that, and include the definition in the header file that defines your class, people will be able to use your class as a key for any of the unordered containers without any additional work.

Defining a specialization of std::hash<T> for your class is really no different than method 3, shown immediately above. The only difference is that you have to use the name hash for your object, you have to define it as a specialization of that template class, and finally, you have to hoist the whole thing into the std namespace.

//
// This program uses a specialization of
// std::hash<T> to provide the function
// object needed by unordered_map.
// 
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include <iostream>
#include <unordered_map>
#include <string>
#include <functional>

using namespace std;

typedef pair<string,string> Name;

namespace std {
    template <>
        class hash<Name>{
        public :
            size_t operator()(const Name &name ) const
            {
                return hash<string>()(name.first) ^ hash<string>()(name.second);
            }
    };
};

int main(int argc, char* argv[])
{
    unordered_map<Name,int> ids;
    ids[Name("Mark", "Nelson")] = 40561;
    ids[Name("Andrew","Binstock")] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.first 
             << " "
             << ii->first.second 
             << " : "
             << ii->second
             << endl;
	return 0;
}

As you can see, for the user of your class, this is the simplest of all possible solutions — no changes are needed to get the default versions of unordered_map to work properly. If you are going to be using this class in multiple places, this is probably the best solution. However, you need to be sure you aren't going to pollute the std namespace with a hash function that might conflict with those used by other classes.

One Last Source of Trouble

In addition to requiring a hash function, the unordered containers also need to be able to test two keys for equality. The canonical way for them to do this is with a version of operator==() defined at the global namespace. This is typically a function you are used to having to construct when creating new classes, but if you overlook it, you will be up against the same raft of incomprehensible compiler errors seen earlier in this article.

I didn't have to deal with it in this article because the standard library already defines this operator for std::pair. Of course, when using std::pair, you also have to make sure you have an equality operator for T1 and T2.

Wrap-Up

This article showed you four different ways to define a hash function for use with a user-defined class and the unordered C++0x containers. When it comes to performance, there is probably no reason to prefer one over another.

None of the techniques described here are particularly difficult to implement, it is just always a surprise and a disappointment to see how hard it is to get this information out of the standard resources.


This article is the opinion of the author. It does not represent the opinion or position of UBM LLC.


Related Reading


More Insights






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.
 

Video