Хеширование строк во время компиляции

по крайней мере, по моему прочтению §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:

1. форма: "return выражение;"
2. его единственным параметром является указатель, который является скалярным типом и, следовательно, литеральным типом.
3. его возвращением является unsigned int, который также является скалярным (и, следовательно, литеральным).
4. нет никакого неявного преобразования к возвращению тип.

есть ли какой-то вопрос *inputS включает незаконное преобразование lvalue в rvalue, и я не уверен, что понимаю правила в §5.19/2/6/2¹ и §4.1 достаточно хорошо, чтобы быть уверенным, что.

С практической точки зрения этот код принят (для одного примера) g++, по крайней мере, еще в 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;

1. Я использую дополнительные номера "косой черты" для обозначения ненумерованных точек маркера, так что это вторая точка маркера внутри, если шестая точка маркера под §5.19/2. Я думаю, что мне, возможно, придется поговорить с Питом Беккером о том, можно ли добавить какие-то цифры/буквы/римские цифры вниз по иерархии, чтобы идентифицировать такие части...

это попытка решить проблему ОП как можно точнее.

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алгоритм, а мы должны переопределите его как constexpr для того чтобы оценить его во время компиляции. Кроме того, нет никаких "прозрачных" хэшей в std, так что вы не можете (без создания std::string) хэш-буфер необработанных символов как std::string.

я вставил std::string custom hasher (с прозрачным const char* поддержка) в my_hash пространство имен, так что вы можете хранить его в std::unordered_map если вам нужна последовательность.

основанный на отличном ответе @JerryCoffin и потоке комментариев под ним, но с попыткой написать его с текущими рекомендациями C++11 (в отличие от их ожидания!).

обратите внимание, что использование "сырого хэша" для switch сообщении case - это опасно. Вы хочу сделать == сравнение впоследствии, чтобы подтвердить, что это сработало.

этот фрагмент основан на Климент Джейкоб один. Но работает и с clang тоже. И это должно быть быстрее при компиляции (у него есть только один рекурсивный вызов, а не два, как в исходном сообщении).

#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")>();
}

см. доказательство концепции здесь

обратите внимание, что форма, показанная здесь, не в стандарт, как указано ниже.

предполагается, что обработка строки времени компиляции станет возможной через пользовательские литералы предложенные в N2765.
Как я уже говорил, я не знаю ни одного компилятора, который в настоящее время реализует его и без поддержки компилятора может быть только догадка.

В §2.13.7.3 и 4 проект у нас есть следующее:

В противном случае (S содержит шаблон литерального оператора), L рассматривается как вызов формы
оператор ""X() где n - исходная последовательность символов c1c2...ck. [Примечание: последовательность c1c2...ck может содержат только символы из базового исходного набора символов. -конец Примечание]

в сочетании с constexpr и мы должны иметь время компиляции обработке строк.

обновление: я пропустил это я читал неправильный абзац, эта форма разрешена для определяемых пользователем целочисленных литералов и плавающих литералов, но, по-видимому, не для строковых литералов (§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);
}

другое решение, основанное на Clement JACOB's one, используя C++11 constexpr (не расширенный C++14), но имеющий только одну рекурсию.

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;
}

объяснение

• мы используем одну рекурсию, так что функция хорошо работает даже для более длинных строк.
• дополнительные функции combine_crc32 позволяет хранить результат рекурсии под переменной part и использовать его дважды. Эта функция является walkaround на языке C++11 limitaton оставить без удовлетворения объявления локальных переменных.
• The ctcrc32 функция ожидает строковый литерал, который передается как const char (&)[len]. Таким образом, мы можем получить длину строки в качестве параметра шаблона и не должны полагаться на макросы.

следующие работы в 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 по-видимому(?) не позволяет рекурсивные вызовы, где мы проходим на s+1 С s указатель, поэтому я использую off переменной.

вот еще одна реализация C++11 (на основе ответа @CygnusX1), которая работает как с массивами символов constexpr, так и со строками времени выполнения:

namespace detail {

    // CRC32 Table (zlib polynomial)
    static constexpr uint32_t crc_table[256] = { 0x00000000L, 0x77073096L, ... };

    constexpr uint32_t combine_crc32(size_t idx, const char * str, uint32_t part) {
        return (part >> 8) ^ crc_table[(part ^ str[idx]) & 0x000000FF];
    }

    constexpr uint32_t crc32(size_t idx, const char * str) {
        return idx == size_t(-1) ? 
            0xFFFFFFFF : combine_crc32(idx, str, crc32(idx - 1, str));
    }
}

uint32_t ctcrc32(std::string const& str) {
    size_t len = str.size() + 1;
    return detail::crc32(len - 2, str.c_str()) ^ 0xFFFFFFFF;
}

template <size_t len>
constexpr uint32_t ctcrc32(const char (&str)[len]) {
    return detail::crc32(len - 2, str) ^ 0xFFFFFFFF;
}

вам нужно str.size() + 1, потому что len во второй перегрузке это strlen(str) + 1 из-за нулевого символа в конце.

Я не добавлял перегрузку для const char * потому что это испортит вторую перегрузку - вы можете легко добавить перегрузки для const char *, size_t или std::string_view.

Это хороший вопрос.

основываясь на ответе Джерри Коффина, я создал еще один, совместимый с 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;
}

https://github.com/manuelgustavo/cx_hash