C++11, unordered_map & enums

Español


Hi all!
 
This time with a detour from Logger to show a little utility for those working with C++11.
Some time ago, doing I don’t remember what, I wanted to make an std::unordered_map using scoped enums (new from C++11) as keys. Well, depending on your OS and/or libstd++ and/or compiler version, you can’t. This was recently experienced by a friend who reminded me of it and a fix I made for that.
 
It’s an issue with the standard and the implementations which, as far as I read, it was fixed with C++14 and newer versions of the failing implementations (i.e. it works fine on Visual Studio 2015 regardless of the standard) but it has an extremely easy fix, so I wrapped it on a header and I’m presenting it to you.
 
The problem is just that there is no template specialization for the std::hash function when the key type is an enum. And then, the fix just involves defining that 🙂

Implementation

namespace ext11 {
    struct echash {
        template <typename enumclass_t>
        std::size_t operator()(enumclass_t&& ec) const {
            using under_type = typename std::underlying_type<typename std::decay<enumclass_t>::type>::type;
            return std::hash<under_type>()(static_cast<under_type>(ec));
        }
    };

Here you can see the struct echash and the hashing operator that takes as input the key and returns an std::size_t associated with it. The using declaration is long, but not that complicated, just type traits applied to the enum type.
 
std::decay allows us to remove constant/volatile qualifiers, rvalue references and all extra data of the type, leaving us with the essential part. For example, std::decay<const volatile unsigned int&&>::type will in turn return unsigned int.
 
To understand std::underlying_type we need to know that enums in C++11 have a type associated, a holder that is one of the integral types. It can be explicit or implicit, it doesn’t matter, if you don’t define it yourself the implementation of C++11 will use one for you. I.E.:

// explicit declaration of the underlying type
enum class my_enum : long {
    FIRST=2000000,
    SECOND
};  

// implicit declaration of the underlying type
enum class my_other_enum {
    FIRST = 0,
    SECOND
};

What std::underlying_type does then is return the underlying type of a given enum, in the case of my_enum that will be long and in the other, my_other_enum, it might be int.
Finally what the using declaration does is just obtain the underlying type of the enum that’s passed as parameter.
In the return statement we just forward the responsibility to the corresponding implementation of std::hash based on that underlying type, safely casting the input enum to that type.
 
What I also provided is an alias for unordered_map within the ext11 namespace that provides this function only when necessary to the std::unordered_map.

template <typename key_t>
    using hash_t = typename std::conditional<std::is_enum<key_t>::value, echash<key_t>, std::hash<key_t>>::type;

    template <typename key_t, 
        typename value_t,
        typename _hasher = hash_t<key_t>,
        typename _eqt = std::equal_to<key_t>,
        typename _alloc = std::allocator<std::pair<const key_t, value_t>>>
    using unordered_map = std::unordered_map<key_t, value_t, _hasher, _eqt, _alloc>;
}

First, using std::is_enum and std::conditional we define the hasher function based on the key type. This will make hash_t be either echash for enums or std::hash (default) for any other type.
 
Later we declare a new type ext11::unordered_map as an alias of std::unordered_map with the only difference being the hasher function to take into account our specialization. (The comparison and allocator functions are left as default but present so that the interface to this new unordered_map is identical to the STL provided one).
 
Hope you like it, this allowed us to see various examples of type traits and SFINAE-based definition of types as std::underlying_type, std::decay, std::conditional and std::is_enum. As always, here is the source code.
 
Best!

Back to Top




¡Buenas!
 
Esta vez vengo con un desvío del Logger para mostrar una pequeña utilidad para aquellos que están trabajando con C++11.
Hace un tiempo, haciendo no sé que cosa, quería usar un std::unordered_map usando scoped enums (nuevos, desde C++11) como keys. Bueno, resulta que dependiendo de tu SO y/o versión de libstdc++ y/o compilador, no podés. Hace poco, un amigo sufrió con lo mismo y me hizo acordar del problema y del fix que armé para ello.
 
Es un problema con el estandar y las implementaciones de C++11, que según leí, ya fue arreglado con C++14 y las nuevas versiones de las implementaciones que no funcionaban (p.e. funciona bien en Visual Studio 2015, independientemente del estandar y lo que dice) pero como tiene un arreglo bastante fácil, lo metí en un header y ahora se los presento.
 
La cuestión es simplemente que no hay especialización de la función std::hash cuando el typo de la clave es un enum. Entonces, el arreglo es definir eso mismo 🙂

Implementación

namespace ext11 {
    struct echash {
        template <typename enumclass_t>
        std::size_t operator()(enumclass_t&& ec) const {
            using under_type = typename std::underlying_type<typename std::decay<enumclass_t>::type>::type;
            return std::hash<under_type>()(static_cast<under_type>(ec));
        }
    };

Acá ven el struct echash y el operador de hasheo que toma como input la clave y retorna un std::size_t asociado. La declaración de using es larga, pero no tan complicada, solo usa type traits aplicados al typo del enum.
 
std::decay permite remover calificadores const/volatile, rvalue references y todo dato extra del tipo, dejando únicamente la parte esencial. Por ejemplo, std::decay<const volatile unsigned int&&>::type retorna unsigned int.
 
Para entender std::underlying_type hay que saber que todos los enums en C++11 tienen un tipo asociado, un contenedor que es de alguno de los tipos integrales (int, long, unsigned int, etc…). Puede ser explícito o implícito, no importa, si no se define la implementación lo elige por vos. P.E.:

// declaración explícita del tipo subyacente
enum class my_enum : long {
    FIRST=2000000,
    SECOND
};  

// declaración implícita del tipo subyacente
enum class my_other_enum {
    FIRST = 0,
    SECOND
};

Lo que std::underlying_type hace entonces es retornar este tipo subyacente del enum particular, en el caso de my_enum será long y en el otro, my_other_enum, podría ser int.
Finalmente lo que la declaración de using hace es obtener el tipo subyacente del enumerado que se pasa por parámetro.
En la sentencia de retorno simplemente se pasa la responsabilidad de calcular el hash a la implementación de std::hash basado en el tipo subyacente, casteando de manera segura el enumerado de input a este tipo.
 
Lo que además proveo es un alias para unordered_map dentro del namespace ext11 que provee esta función a std::unordered_map solamente cuando es necesario.

template <typename key_t>
    using hash_t = typename std::conditional<std::is_enum<key_t>::value, echash<key_t>, std::hash<key_t>>::type;

    template <typename key_t, 
        typename value_t,
        typename _hasher = hash_t<key_t>,
        typename _eqt = std::equal_to<key_t>,
        typename _alloc = std::allocator<std::pair<const key_t, value_t>>>
    using unordered_map = std::unordered_map<key_t, value_t, _hasher, _eqt, _alloc>;
}

Primero, usando std::is_enum y std::conditional definimos la función de hash que se va a utilizar en base al tipo de la clave. Esto hace que hash_t sea echash para enumerados o std::hash (valor por defecto) para cualquier otro tipo.
 
Luego se declara un nuevo tipo ext11::unordered_map como alias de std::unordered_map con la única diferencia siendo la función de hasheo, teniendo en cuenta la especialización previa. (Las funciones de comparación y allocator se dejan con el valor por defecto pero presentes, para que la interfaz a este nuevo unordered_map sea identica a la del que provee la STL).
 
Espero que haya gustado, esto nos permitió ver varios ejemplos de type traits y definiciones de tipos basadas en SFINAE como std::underlying_type, std::decay, std::conditional y std::is_enum. Como siempre, acá está el código fuente.
 
¡Suerte!
Inicio

Advertisements

Leave a Reply (Deja una respuesta)

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s