编译时间string散列
我已经阅读了几个不同的地方，使用C ++ 11的新string文字，可能在编译时计算string的哈希值。 然而，似乎没有人愿意出来说这将是可能的或将如何完成。
- 这可能吗？
- 运营商会是什么样子？
我特别感兴趣的使用这种情况。
void foo( const std::string& value ) { switch( std::hash(value) ) { case "one"_hash: one(); break; case "two"_hash: two(); break; /*many more cases*/ default: other(); break; } } 注意：编译时散列函数不必像我写的那样精确。 我尽我所能去猜测最终的解决scheme是什么样的，但meta_hash<"string"_meta>::value也可能是一个可行的解决scheme。
这有点迟，但是我成功地使用了constexpr来实现一个编译时CRC32函数。 它的问题是，在编写本文时，它只适用于GCC而不是MSVC或英特尔编译器。
这里是代码片段：
// CRC32 Table (zlib polynomial) static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, ... }; template<size_t idx> constexpr uint32_t crc32(const char * str) { return (crc32<idx-1>(str) >> 8) ^ crc_table[(crc32<idx-1>(str) ^ str[idx]) & 0x000000FF]; } // This is the stop-recursion function template<> constexpr uint32_t crc32<size_t(-1)>(const char * str) { return 0xFFFFFFFF; } // This doesn't take into account the nul char #define COMPILE_TIME_CRC32_STR(x) (crc32<sizeof(x) - 2>(x) ^ 0xFFFFFFFF) enum TestEnum { CrcVal01 = COMPILE_TIME_CRC32_STR("stack-overflow"), };
CrcVal01等于0x335CC04A
希望对你有帮助！
至less通过我阅读§7.1.5/ 3和§5.19，以下可能是合法的：
unsigned constexpr const_hash(char const *input) { return *input ? static_cast<unsigned int>(*input) + 33 * const_hash(input + 1) : 5381; }
这似乎遵循§7.1.5/ 3中的基本规则：
- forms是：“返回expression式”
- 它唯一的参数是一个指针，它是一个标量types，因此是一个文字types。
- 它的返回值是无符号整数，这也是标量（因此是文字）。
- 没有隐式转换到返回types。
有一些问题， *input是否包含一个非法的左值和右值的转换，我不确定是否理解了§5.19/ 2/6/2 1和§4.1中的规则。
从实际的angular度来看，这个代码被（例如）g ++接受，至less早在g ++ 4.7.1。
用法如下所示：
switch(std::hash(value)) { case const_hash("one"): one(); break; case const_hash("two"): two(); break; // ... default: other(); break; }
为了符合§5.19/ 2/6/2的要求，您可能需要这样做：
// one of the `constexpr`s is probably redundant, but I haven't figure out which. char constexpr * constexpr v_one = "one"; // .... case const_hash(v_one): one(); break;
- 我正在使用额外的“斜线”数字来引用未编号的项目符号点，所以这是如果第5.19 / 2条中的第六个项目符号点内部的第二个项目符号点。 我想我可能不得不和Pete Becker谈谈是否可以在层次结构中添加某种数字/字母/罗马数字来识别这样的片段…
这是尽可能准确地解决OP问题的尝试。
namespace my_hash { template<class>struct hasher; template<> struct hasher<std::string> { std::size_t constexpr operator()(char const *input)const { return *input ? static_cast<unsigned int>(*input) + 33 * (*this)(input + 1) : 5381; } std::size_t operator()( const std::string& str ) const { return (*this)(str.c_str()); } }; template<typename T> std::size_t constexpr hash(T&& t) { return hasher< typename std::decay<T>::type >()(std::forward<T>(t)); } inline namespace literals { std::size_t constexpr operator "" _hash(const char* s,size_t) { return hasher<std::string>()(s); } } } using namespace my_hash::literals; void one() {} void two() {} void other() {} void foo( const std::string& value ) { switch( my_hash::hash(value) ) { case "one"_hash: one(); break; case "two"_hash: two(); break; /*many more cases*/ default: other(); break; } }
活的例子 。
注意主要的区别 – std::hash不能用，因为我们不能控制std::hash的algorithm，为了在编译的时候评估它，我们必须将它重新实现为constexpr 。 另外， std中没有“透明”散列，所以你不能（不创build一个std::string ）将一个原始字符缓冲区作为std::string散列。
我将std::string自定义hasher（使用透明const char*支持）插入到my_hash命名空间中，所以如果需要一致性，可以将其存储在std::unordered_map 。
基于@ JerryCoffin的优秀答案和下面的评论线索，但是试图用当前的C ++ 11最佳实践（而不是预期它们）来编写它。
请注意，对switch语句使用“raw hash”是很危险的。 之后你会想做一个==比较来确认它的工作。
这个片段基于Clement JACOB的一个。 但也与铿锵作品。 编译应该更快（它只有一个recursion调用，而不是像原来的文章那样）。
#include <iostream> #include <string> #include <vector> static constexpr unsigned int crc_table[256] = { 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d }; template<int size, int idx = 0, class dummy = void> struct MM{ static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF) { return MM<size, idx+1>::crc32(str, (prev_crc >> 8) ^ crc_table[(prev_crc ^ str[idx]) & 0xFF] ); } }; // This is the stop-recursion function template<int size, class dummy> struct MM<size, size, dummy>{ static constexpr unsigned int crc32(const char * str, unsigned int prev_crc = 0xFFFFFFFF) { return prev_crc^ 0xFFFFFFFF; } }; // This don't take into account the nul char #define COMPILE_TIME_CRC32_STR(x) (MM<sizeof(x)-1>::crc32(x)) template<unsigned int crc> void PrintCrc() { std::cout << crc << std::endl; } int main() { PrintCrc<COMPILE_TIME_CRC32_STR("HAH")>(); }
在这里看到概念validation
请注意，此处显示的表单未被接受到标准中，如下所述。
编译时间string处理被猜测成为可能通过N2765中提出的用户定义文字 。
正如我已经提到的，我不知道任何编译器，目前实现它，没有编译器的支持，只能猜测工作。
草案 §2.13.7.3和4中有以下内容：
否则（S包含一个文字操作符模板），L被视为表单的调用
运算符“”X <'c1'，'c2'，…，'ck'>（）其中n是源字符序列c1c2 … ck。 [注意：序列c1c2 … ck只能包含来自基本源字符集的字符。 – 注意]
结合constexpr ，我们应该编译时间string处理。
更新：我忽略了我读错了段落，这种forms是允许用户定义的整数文字和 – 浮动文字，但显然不是为string（§2.13.7.5）。
这部分提案似乎还没有被接受。
话虽如此，我有限的瞥见在C + + 0x，它可能看起来像这样（我最有可能出错）：
template<char c, char... str> struct hash { static const unsigned result = c + hash<str...>::result; }; template<char c> struct hash { static const unsigned result = c; }; template<char... str> constexpr unsigned operator "" _hash() { return hash<str>::result; } // update: probably wrong, because the above // form is not allowed for string-literals: const unsigned h = "abcd"_hash;
如果Jerrys方法有效，那么下面的方法应该可以工作：
constexpr unsigned operator "" _hash(const char* s, size_t) { return const_hash(s); }
以下在GCC 4.6.1中有效，你可以在开关块中使用hash或pack 。
/* Fast simple string hash (Bernstein?) */ constexpr unsigned int hash(const char *s, int off = 0) { return !s[off] ? 5381 : (hash(s, off+1)*33) ^ s[off]; } /* Pack the string into an unsigned int * Using 7 bits (ascii) it packs 9 chars into a uint64_t */ template <class T = uint64_t, unsigned int Bits = 7> constexpr T pack(const char *s, unsigned int off = 0) { return (Bits*off >= CHAR_BIT*sizeof(T) || !s[off]) ? 0 : (((T)s[off] << (Bits*off)) | pack(s,off+1)); }
GCC似乎（？）不允许recursion调用，我们通过s+1传递一个指针，这就是为什么我使用offvariables。
另一种基于Clement JACOB的解决scheme是使用C ++ 11 constexpr（而不是扩展的C ++ 14），但只有一个recursion。
namespace detail { // CRC32 Table (zlib polynomial) static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... } template<size_t idx> constexpr uint32_t combine_crc32(const char * str, uint32_t part) { return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF]; } template<size_t idx> constexpr uint32_t crc32(const char * str) { return combine_crc32<idx>(str, crc32<idx - 1>(str)); } // This is the stop-recursion function template<> constexpr uint32_t crc32<size_t(-1)>(const char * str) { return 0xFFFFFFFF; } } //namespace detail template <size_t len> constexpr uint32_t ctcrc32(const char (&str)[len]) { return detail::crc32<len - 2>(str) ^ 0xFFFFFFFF; }
一些解释
- 我们正在使用一个recursion，所以即使对于较长的string，该函数也能正常工作。
- 额外的函数
combine_crc32允许我们将recursion的结果存储在一个可变part并使用它两次。 这个函数是C ++ 11限制不允许局部variables声明的一个解决scheme。 -
ctcrc32函数需要一个string，它是以const char (&)[len]forms传递的。 这样我们可以将string长度作为模板参数，而不必依赖macros。
这是一个很好的问题。
根据Jerry Coffin的回答，我创build了另一个与Visual Studio 2017的std :: hash兼容的程序。
#include <functional> #include <cassert> using namespace std; constexpr size_t cx_hash(const char* input) { size_t hash = sizeof(size_t) == 8 ? 0xcbf29ce484222325 : 0x811c9dc5; const size_t prime = sizeof(size_t) == 8 ? 0x00000100000001b3 : 0x01000193; while (*input) { hash ^= static_cast<size_t>(*input); hash *= prime; ++input; } return hash; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ auto a = cx_hash("test"); hash<string> func; auto b = func("test"); assert(a == b); return 0; }
