hashing de cadena en tiempo de compilación

Question

Necesito usar una cadena como ID para obtener algún objeto. En implementar esto en un tiempo de ejecución, y funciona bien. Pero esto hace imposible la verificación de tipo estático, por razones obvias.

He buscado en Google para el algoritmo para calcular el hash-suma de cadena en el tiempo de compilación: C++ compile-time string hashing with Boost.MPL.

Parece ser la solución perfecta para mi problema, excepto que el sring que es necesario para el algoritmo se debe dividir en pedazos por 4 caracteres, o carácter por carácter, también, por razones obvias.

es decir, en lugar de la habitual registro actual de las identificaciones, voy a tener que escribir de esta manera:

hash_cstring<boost::mpl::string<'obje', 'ct.m', 'etho', 'd'>>::value 

Esto es absolutamente inutilizable.

La cuestión es cómo pasar correctamente la cadena como "object.method" a este algoritmo?

Gracias a todos.

Answer 1

solución con gcc-4.6:

#include <iostream> 
template<size_t N, size_t I=0> 
struct hash_calc { 
    static constexpr size_t apply (const char (&s)[N]) { 
     return (hash_calc<N, I+1>::apply(s)^s[I]) * 16777619u; 
    }; 
}; 

template<size_t N> 
struct hash_calc<N,N> { 
    static constexpr size_t apply (const char (&s)[N]) { 
     return 2166136261u; 
    }; 
}; 

template<size_t N> 
constexpr size_t hash (const char (&s)[N]) { 
    return hash_calc<N>::apply(s); 
} 

int main() { 
    char a[] = "12345678"; 
    std::cout << std::hex << hash(a) << std::endl; 
    std::cout << std::hex << hash("12345678") << std::endl; 
} 

http://liveworkspace.org/code/DPObf

yo estoy feliz!

Answer 2

No sé de una manera de hacer esto con el preprocesador o con plantillas. Sospecho que su mejor opción es crear un paso de precompilación separado (digamos con Perl o similar) para generar las declaraciones hash_cstring de un conjunto de declaraciones fuente. Entonces, al menos, no tiene que dividir las cadenas manualmente cuando agrega nuevas, y la generación es totalmente automática y repetible.

Answer 3

plantillas se pueden crear instancias con cualquier símbolo externo, por lo tanto, esto debería funcionar como se esperaba:

external char const* object_method = "object.method"; 
... = hash_cstring<object_method>::value; 

(dada la plantilla hash_cstring<> es capaz de tratar con valores de puntero).

Answer 4

En caso de que a alguien le interesa, ande en cómo crear un hash tiempo de compilación de Murmur3_32 usando C++ 11 funciones constexpr y plantillas variadic aquí:

http://roartindon.blogspot.sg/2014/10/compile-time-murmur-hash-in-c.html

La mayoría de los ejemplos que he trato visto con hashes que se basan en consumir un caracter de la cadena a la vez. El hash Murmur3_32 es un poco más interesante ya que consume 4 caracteres a la vez y necesita un código de caso especial para manejar los 0, 1, 2 o 3 bytes restantes.