Jonathan Boccara's blog

Tweet

Making Strong Types Hashable

Published May 30, 2017 - 5 Comments

Strong types are types that are built over primitive types, and add meaning to them. My purpose today is two-fold:

  • showing you how to write an STL-compliant hash function for custom types so that they can be used in unordered containers such as std::unordered_map,
  • making a hash function available for strong types.

For more about the motivation and implementation of strong types, I suggest you read Strong types for strong interfaces first, as we’ll use the NamedType class and in particular its feature to inherit functionalities from the underlying type.

Strong types are an essential tool to bring expressiveness into code. Here is the series dedicated to strong types on Fluent C++:

Implementing a hash function in C++

Since C++11, the standard offers an std::hash structure declared in the namespace std:

namespace std
{
    template< class Key >
    struct hash;
}

The standard also specifies specializations for this structure for a fair amount of standard types. There are about 30 such types, including int, bool, char, double, std::string, and even some generic types such as T*, std::optional<T> or std::unique_ptr<T>, with a fallback on the template type hashing in the latter case.

These specializations of std::hash have notably 2 methods:

  • a default constructor (taking no parameter),
  • an operator(), whose prototype is of the form 
    size_t operator()(Key const&) const;

    and which actually does the job of providing a hash value (of type size_t) from an object of the type inside std::hash.

On the other side, the unordered containers of the STL such as std::unordered_map accept a hash structure in their template parameters. And this template has a default value of std::hash specialized on the Key type of the container:

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

The container builds hash objects of type Hash, and invokes them on an element whenever it needs a hash value, like when inserting or searching a key in the container.

Making strong types hashable

Our purpose will be here to allow any strong type to inherit from the hash function of its underlying type, if it exists. And this functionality should be explicitly asked for when defining the strong type, exactly like the other functionalities inherited from the underlying type.

To illustrate, let’s take the example of a type representing a serial number, modeled by a string. We want to be able to define the serial number as a strong type like so:

using SerialNumber = NamedType<std::string, SerialNumberTag, Comparable, Hashable>;

(Comparable provides operator== inherited from the underlying type, also used by the STL hash table via std::equal_to visible in the above definition of std::unordered_map).

So let’s specialize std::hash for our NamedType class:

namespace std
{
    template <typename T, typename Parameter, typename Converter, template<typename> class... Skills>
    struct hash<NamedTypeImpl<T, Parameter, Converter, Skills...>>
    {
        size_t operator()(NamedTypeImpl<T, Parameter, Converter, Skills...> const& x) const
        {
            return std::hash<T>()(x.get());
        }
    };
}

Despite its bushy aspect the above code is really easy to understand. The class that we progressively built along the posts of this series to represent strong types is:

template <typename T, typename Parameter, typename Converter, template<typename> class... Skills>
class NamedTypeImpl<T, Parameter, Converter, Skills...>;

and the rest is just putting into std::hash and calling std::hash on the underlying type.

Are we done then?

Almost, but not quite. With the above implementation, every strong type will be hashable. However, we want this feature to be activated on demand, by including Hashable in the list of skills to be inherited from the underlying type. And the feature is not asked for explicitly, we’d like the above code of the specialization to go away.

Said differently, we want this code to be enabled if the strong type is Hashable. This sounds like a job for std::enable_if.

The class representing strong types inherits from its policies such as Hashable and Comparable. So let’s define Hashable simply as a token:

template<typename T>
struct Hashable
{
    static constexpr bool is_hashable = true;
};

And base the enabling of the specialization of std::hash on the presence of this token. Look at the using declarations added to the below specialization, that rely on enable_if to make the instantiation of the structure valid or not:

namespace std
{
template <typename T, typename Parameter, typename Converter, template<typename> class... Skills>
struct hash<NamedTypeImpl<T, Parameter, Converter, Skills...>>
{
    using NamedType = NamedTypeImpl<T, Parameter, Converter, Skills...>;
    using checkIfHashable = typename std::enable_if<NamedType::is_hashable, void>::type;
    
    size_t operator()(NamedTypeImpl<T, Parameter, Converter, Skills...> const& x) const
    {
        return std::hash<T>()(x.get());
    }
};
}

And this does the job. The following code:

using SerialNumber = NamedType<std::string, struct SerialNumberTag, Comparable, Hashable>;

std::unordered_map<SerialNumber, int> hashMap = { {SerialNumber{"AA11"}, 10}, {SerialNumber{"BB22"}, 20} };
std::cout << hashMap[SerialNumber{"BB22"}] << '\n';

outputs 20.

And the same code without Hashable in the strong type declaration yields a compile error.

If you want to see the code, have a look at the GitHub repository for NamedType.

Related articles:

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin


Comments are closed