Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > string hashing in compile-time

Автор: boostcoder 12.2.2011, 05:12

есть необходимость, в качестве ID`а для получения некоторого объекта, использовать строку. сейчас этот способ работает в run-time, и работает не плохо. но это делает невозможным статическую проверку соответствия типов, по понятным причинам.
гуглением, нашел алгоритм создания хеш-суммы строки в compile-time: http://arcticinteractive.com/2009/04/18/compile-time-string-hashing-boost-mpl/
это кажется идеальное решение моей задачи, за исключением того, что строка необходимая алгоритму, должна разбиваться на части по 4 символа, или посимвольно, так же, по понятным причинам.
т.е., вместо привычной теперешней записи ID`ов, придется писать так:

Код


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

что абсолютно не юзабельно smile

вопрос в том, как строку типа "object.method", корректно передать в этот алгоритм?

всем спасибо.

зы

Код


#include <boost/mpl/string.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/size_t.hpp>
#include <iostream>

template <typename Seed, typename Value>
struct hash_combine {
   typedef boost::mpl::size_t<
      Seed::value ^ (static_cast<std::size_t>(Value::value)
      + 0x9e3779b9 + (Seed::value << 6) + (Seed::value >> 2))
   > type;
};

// Hash any sequence of integral wrapper types
template <typename Sequence>
struct hash_sequence: boost::mpl::fold<Sequence,boost::mpl::size_t<0>,hash_combine<boost::mpl::_1, boost::mpl::_2>>::type
{};

// For hashing std::strings et al that don't include the zero-terminator
template <typename String>
struct hash_string: hash_sequence<String>
{};

// Hash including terminating zero for char arrays
template <typename String>
struct hash_cstring: hash_combine<hash_sequence<String>, boost::mpl::size_t<0>>::type
{};

int main() {
   std::cout << hash_cstring<boost::mpl::string<'1'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'3'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abc'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcd', 'defg'>>::value << std::endl;
}

http://liveworkspace.org/code/b3380d0e18ebffbe522710478202c062

Автор: boostcoder 12.2.2011, 09:56

наверное, правильнее не подстраиваться под имеющуюся реализацию, а написать подходящую, не использующую boost::mpl::string.

Автор: GoldFinch 12.2.2011, 14:43

Цитата(boostcoder @ 12.2.2011, 05:12

)

http://arcticinteractive.com/2009/04/18/co...hing-boost-mpl/

как правильно написано в конце этой статьи, надо ждать constexpr которое уже есть в гцц 4.6 .

также есть вот такой вариант http://2x2is11.blogspot.com/2010/11/c-how-to-calculate-string-hash-at.html
хотя полученные им хеши не константы времени компиляции, фактически они получаются во время компиляции, может это можно как-то использовать.

Автор: boostcoder 13.2.2011, 06:15

Цитата(GoldFinch @ 12.2.2011, 14:43

)

также есть вот такой вариант http://2x2is11.blogspot.com/2010/11/c-how-...ng-hash-at.html

спасибо.
я тоже нагуглил что-то подобное: http://chrissavoie.com/articles-mainmenu-29/15/14-hashing
но в обоих случаях, при таком примере:

Код


enum { hash = HASH("1") };

получаю одинаковые ошибки:

Цитата

../test2/main.cpp: In function ‘int main()’:
../test2/main.cpp:17:16: error: an array reference cannot appear in a constant-expression
../test2/main.cpp:17:16: error: an array reference cannot appear in a constant-expression
../test2/main.cpp:17:16: error: an array reference cannot appear in a constant-expression
../test2/main.cpp:17:16: error: an array reference cannot appear in a constant-expression
../test2/main.cpp:17:16: error: an array reference cannot appear in a constant-expression
...
...

и еще. при тестах: http://arcticinteractive.com/2009/04/18/compile-time-string-hashing-boost-mpl/
обнаружил странные результаты.
в следующем коде, последние пять результатов - разные.
я полагал, что при записи подряд более 4ех символов, последние будут игнорировать. а получается что нет.
кто-то может объяснить такое поведение?

Код


#include <boost/mpl/string.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/size_t.hpp>
#include <iostream>

template <typename Seed, typename Value>
struct hash_combine {
   typedef boost::mpl::size_t<
      Seed::value ^ (static_cast<std::size_t>(Value::value)
      + 0x9e3779b9 + (Seed::value << 6) + (Seed::value >> 2))
   > type;
};

// Hash any sequence of integral wrapper types
template <typename Sequence>
struct hash_sequence: boost::mpl::fold<Sequence,boost::mpl::size_t<0>,hash_combine<boost::mpl::_1, boost::mpl::_2>>::type
{};

// Hash including terminating zero for char arrays
template <typename String>
struct hash_cstring: hash_combine<hash_sequence<String>, boost::mpl::size_t<0>>::type
{};

int main() {
   /** ok */
   std::cout << hash_cstring<boost::mpl::string<'a','b','c','d','e','f','g','h'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcd','efgh'>>::value << std::endl;
   /** ??? */
   std::cout << hash_cstring<boost::mpl::string<'abcdefgh'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcdefghi'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcdefghij'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcdefghijk'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'abcdefghijkl'>>::value << std::endl;
}

http://liveworkspace.org/code/6d3cdaf592c72da2dd84591ef10fa51d

Автор: mes 13.2.2011, 12:59

Цитата(boostcoder @ 13.2.2011, 05:15

)

что при записи подряд более 4ех символов, последние будут игнорировать.

почему последние, а не первые ?

Добавлено через 1 минуту и 37 секунд
подсказка : '....' - это обычное число, и на него распространяются те же правила переполнения..

Автор: boostcoder 13.2.2011, 13:01

Цитата(mes @ 13.2.2011, 12:59

)

почему последние, а не первые ?

упс, запутался smile

Добавлено через 2 минуты и 38 секунд
да. все верно.
у этих строк значения одинаковые:

Код


   std::cout << hash_cstring<boost::mpl::string<'1234'>>::value << std::endl;
   std::cout << hash_cstring<boost::mpl::string<'56781234'>>::value << std::endl;

Автор: mes 13.2.2011, 13:42

Цитата(boostcoder @ 13.2.2011, 05:15

)

...'a','b','c','d','e','f','g','h'...

можно избавиться от ' ', но к сожалению запятая останется...
т.е. строка будет задаваться как STR(a,b,c,d,e,f,g)
при этом будет возможность задать свой алфавит символов...
т.е. например запятую можно будет обозвать как comma..
для этого
1. для каждого символа создается свой тип
2. чтоб не было коллизий, имени типа символа задать общий уникальный префикс
3. определить макрос, который из переданной последовательности символов, создаст последовательность типов..

Добавлено через 9 минут и 58 секунд
вот пример: http://forum.vingrad.ru/forum/topic-268064/anchor-entry1931740/13.html
избавиться от _3 в LIST_OF_CHARS_3 тоже можно посредством эллипсиса..

Автор: boostcoder 13.2.2011, 13:53

Цитата(mes @ 13.2.2011, 13:42

)

1. для каждого символа создается свой тип
2. чтоб не было коллизий, имени типа символа задать общий уникальный префикс
3. определить макрос, который из переданной последовательности символов, создаст последовательность типов..

я тут всерьез подумываю о pre-build-step`е на котором, некоторая утилитка, из вызовов типа ".registry(&t, "type")" и ".on("method", &type::method)", создаст записи типа ".registry(&t, 0xf363e2)" и ".on(0x552a6b3, &type::method)" соответственно.
или, привязать пользователей к gcc-4.6 smile

ну не вижу я другого решения...

Автор: mes 13.2.2011, 13:55

Цитата

#define char_a

это естественно менятся на что то типа : struct char_a { enum { value = 'a'}; };

Автор: boostcoder 13.2.2011, 14:01

но ни один из вариантов хорошим не назовешь, ибо оба через одно место...

Цитата(boostcoder @ 13.2.2011, 13:53

)

или, привязать пользователей к gcc-4.6

по переписке разработчиков выяснил, что ориентировочная дата выхода релиза - осень этого года smile

в репозитариях его нет. т.е. остается либо собирать самому, либо искать чьи-то сборки.

Добавлено через 28 секунд

Цитата(mes @ 13.2.2011, 13:55

)

это естественно менятся на что то типа : struct char_a { enum { value = 'a'}; };

да. я понял.

Автор: mes 13.2.2011, 14:08

Цитата(boostcoder @ 13.2.2011, 12:53

)

или, привязать пользователей к gcc-4.6
ну не вижу я другого решения...

для этого для начала нужно представлять концепцию..
а вариантов куча, вот например еще один :

Код

// proto.inc
 (user), (join),(part),(quit) 

// any.h
namespace proto {
DY_DECLARE_ALPHABET(
 #include "proto.inc"
)}

struct any {
    void on_user ();
    void on_join ();
    void on_part ();
    void on_quit ();

    any () {
      _table.register
          (proto::user, any::on_user)
          (proto::join, any::on_join)
          (proto::part, any::on_part)
          (proto::quit, any::on_quit);
   }
   dy::table _table;
};

// any.cpp
namespace proto {
DY_DEFINE_ALPHABET(
 #include "proto.inc"
)}
...

Автор: boostcoder 13.2.2011, 14:17

Цитата(mes @ 13.2.2011, 14:08

)

(user), (join),(part),(quit)

этого очень не хочется... smile

Цитата(mes @ 13.2.2011, 14:08

)

    any () {
      _table.register
          (proto::user, any::on_user)
          (proto::join, any::on_join)
          (proto::part, any::on_part)
          (proto::quit, any::on_quit);
   }
   dy::table _table;

этого сейчас тоже нет.
выглядит так:

Код



struct any {
    void on_user ();
    void on_join ();
    void on_part ();
    void on_quit ();
    any () {
        reg = distributor.registry(this, "any");
        reg->on("on_user", &any::on_user)
              ->on("on_join", &any::on_join)
              ->on("on_part", &any::on_part)
              ->on("on_quit", &any::on_quit);
    }

    registry<any> reg;
};

для каждого обработчика требуется объект регистратор, время жизни которого, определяет время действительности регистрации.
но сейчас нет статической проверки типов. потому и вожусь... хотя работает.
может забить на проверку типов... реализовать когда gcc-4.6 выйдет..

Автор: mes 13.2.2011, 16:37

Цитата(boostcoder @ 13.2.2011, 13:17

)

но сейчас нет статической проверки типов.

для того чтоб была статическая проверка, надо будет все равно определить тип...
тем более что, тип используется минимум в двух (при отправке и приеме)..

вот что к примеру мешает сейчас добавить макрос, для такого использования :

Код



DY_TYPE(f, "f", (std::string) ) 
//или 
//DY_TYPE(f, (std::string) );

...
 reg (f, &any::f)

Автор: boostcoder 13.2.2011, 16:43

Цитата(mes @ 13.2.2011, 16:37

)

вот что к примеру мешает сейчас добавить макрос, для такого использования?

ничего не мешает. просто я стремился избавиться от макросов и другой кодогенерации. и сейчас нет ни одного макроса. хотелось бы чтоб так и осталось smile

Автор: mes 13.2.2011, 16:44

Цитата(boostcoder @ 13.2.2011, 15:43

)

ничего не мешает. просто я стремился избавиться от макросов и другой кодогенерации

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

Добавлено через 14 минут и 8 секунд
макросы, в принципе, можно реализовать так, чтоб их присутствие не было в хидерах пользователя..

Автор: mes 13.2.2011, 17:02

например отделить рантайм представление ид от типа ...
http://liveworkspace.org/code/ac0bac3f7199e62fea8cefe173170975

Автор: boostcoder 13.2.2011, 17:03

отвечу в нашей мегатеме.
а то к этой теме это отношения уже не имеет...

Автор: boostcoder 13.2.2011, 22:53

Цитата(GoldFinch @ 12.2.2011, 14:43

)

надо ждать constexpr

вы не могли бы показать пример этого? я что-то не въезжаю smile

Автор: GoldFinch 14.2.2011, 00:48

boostcoder, просто помечаете функцию как constexpr и она работает в compile-time
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2235.pdf
(на самом деле есть ограничения, впрочем всеравно надо ждать гцц4.6 чтобы проверить)

Автор: boostcoder 14.2.2011, 00:53

Цитата(GoldFinch @ 14.2.2011, 00:48

)

просто помечаете функцию как constexpr и она работает в compile-time

про constexpr я понял.
я не помял что мне это даст.

Код


template<typename T>
struct type {
   template<typename R, typename Args...>
   void(R(T::*m)(const Args...), const char* id) { <<<<<<<<<<<<< ???
   }
};

как constexpr мне поможет использовать алгоритм mpl-hash в данном случае?

Добавлено через 1 минуту и 55 секунд

Цитата(GoldFinch @ 14.2.2011, 00:48

)

всеравно надо ждать гцц4.6 чтобы проверить

я могу проверить и сейчас. знать бы что проверять.

Автор: GoldFinch 14.2.2011, 00:56

сомнительное это дело, писать код вслепую %)

Добавлено через 5 минут и 4 секунды
вобщем циклов там нет, рекурсии нет.
зато там наверное можно сделать

Код


constexpr f(int i) { return ("some string")[i]; }

если да - то это можно использовать в том http://2x2is11.blogspot.com/2010/11/c-how-to-calculate-string-hash-at.html

Добавлено через 6 минут и 5 секунд

Цитата(boostcoder @ 14.2.2011, 00:53

)

я могу проверить и сейчас. знать бы что проверять.

работу со строковыми литералами надо проверять, что еще %)

Автор: mes 14.2.2011, 01:06

Цитата(GoldFinch @ 13.2.2011, 23:56

)

, рекурсии нет.

а рекурсии почему нет то ?

Автор: GoldFinch 14.2.2011, 01:10

mes, потому что Струструп так сказал

Цитата

constexpr int fac(int x)
{ return x > 2 ? x * fac(x - 1) : 1; } // error: fac() not defined
// before use

We (still) prohibit recursion in all its form in constant expressions. That is not
strictly necessary because an implementation limit on recursion depth in constant
expression evaluation would save us from the possibility of the compiler recursing
forever. However, until we see a convincing use case for recursion, we don’t
propose to allow it.

Автор: mes 14.2.2011, 01:11

Цитата(boostcoder @ 13.2.2011, 23:53

)

знать бы что проверять.

ну вот это для начала :

Код


template <size_t N>
constexpr size_t test (char str[N])
{
   return N;
}
int a[test("string")];

int main () {
  std::cout << sizeof (a);
}

Автор: boostcoder 14.2.2011, 01:13

Цитата(GoldFinch @ 14.2.2011, 00:56

)

сомнительное это дело, писать код вслепую %)

вы о том, что у вас нет gcc-4.6 ?
пожалуйста: rghost.ru/4342609
вчерашняя сборка из SVN.

Автор: GoldFinch 14.2.2011, 01:17

boostcoder, при проверках надо учитывать что constexpr код может быть и динамически выполняемым:

Цитата

A constant-expression constructor may be invoked with non-constant expression
arguments — the resulting initialization may then be dynamic.

массивы могут не подойти, т.к. может сработать расширение С99
лучше шаблоны или switch

Код


constexpr foo() { ... }
int main()
{
  switch(1)
 {
 case foo(): ;
 } 
}

Автор: boostcoder 14.2.2011, 01:18

mes, сейчас проверю.

Автор: GoldFinch 14.2.2011, 01:19

Цитата(boostcoder @ 14.2.2011, 01:13

)

вы о том, что у вас нет gcc-4.6 ?

у меня никакого гцц нет)
ок, попробуем..

Автор: boostcoder 14.2.2011, 01:23

Цитата(boostcoder @ 14.2.2011, 01:13

)

пожалуйста: rghost.ru/4342609
вчерашняя сборка из SVN.

забыл уточнить: это mingw.

Добавлено через 4 минуты и 45 секунд
mes, ваш код скомпилился только после такой поправки:

Код


#include <iostream>

template <size_t N>
constexpr size_t test(const char (&str)[N])
{
   return N;
}

int a[test("string")];

int main () {
  std::cout << sizeof (a);
}

результат - 28. правильно.

иначе такая ошибка:

Цитата

C:\>g++ -omain main.cpp -std=c++0x
main.cpp:8:20: error: no matching function for call to 'test(const char [7])'
main.cpp:8:20: note: candidate is:
main.cpp:4:40: note: template<unsigned int N> constexpr size_t test(const char*)

Автор: GoldFinch 14.2.2011, 01:28

Код


template<long N>
constexpr long test(const char (&str)[N])
{
   return N;
}

template<long N> struct identity { static const long value = N; };

int main()
{
    return identity<test("123")>::value;
}

работает

Автор: boostcoder 14.2.2011, 01:32

Цитата(GoldFinch @ 14.2.2011, 01:28

)

const char (&str)[N]

значит я правильно понял что mes имел ввиду.

Автор: mes 14.2.2011, 01:32

Цитата(GoldFinch @ 14.2.2011, 00:10

)

потому что Струструп так сказал

спс

Цитата(boostcoder @ 14.2.2011, 00:23

)

ваш код скомпилился только после такой поправки:

а ну да.. но для первого раза пойдет.. ну как терь сделать hash функцию нашли ?

Автор: GoldFinch 14.2.2011, 01:32

ну вот, осталось хеш сделать....

Автор: boostcoder 14.2.2011, 01:34

Цитата(mes @ 14.2.2011, 01:32

)

ну как терь сделать hash функцию нашли ?

есть идеи. буду пробовать smile

Цитата(GoldFinch @ 14.2.2011, 01:32

)

ну вот, осталось хеш сделать....

угу.
и привязать пользователей к будущему стандарту smile

Автор: GoldFinch 14.2.2011, 01:34

время позднее, ничего умнее макроса который будет раскрываться в копипасту мне на ум не приходит.

Добавлено через 2 минуты и 53 секунды
хотя есть вариант передавать строку как значение...

Автор: mes 14.2.2011, 01:42

Цитата(boostcoder @ 14.2.2011, 00:34

)

и привязать пользователей к будущему стандарту

тут два вопроса возникают..
1. до сих пор не вижу как защитит типизацию Вас компил-тайм хэш..
2. что мешает, для остальных компилятор использовать более неудобное представление ?

Автор: GoldFinch 14.2.2011, 01:50

Код


typedef unsigned long size_t;

struct hash
{
    static constexpr unsigned f(unsigned prevHash, char nextChar) // FNV1-a
    { 
        return nextChar ? unsigned((prevHash ^ nextChar) * 16777619u) : prevHash;
    }

    template <size_t N>
    static constexpr unsigned calc(const char (&s)[N])
    {
        return f(f(f(f( f(f(f(f( 2166136261u
            , s[0]), s[1]), s[2]), s[3]), s[4]), s[5]), s[6]), s[7])
            ;
    }    
};

#define HASH(str) hash::calc(str "\0\0\0\0" "\0\0\0\0")

template <unsigned N> struct identity { static const unsigned value = N; };

int main()
{
    return (int)identity<HASH("123")>::value;
}

слава копипасте...

Добавлено через 4 минуты и 5 секунд

Цитата(boostcoder @ 14.2.2011, 01:34

)

и привязать пользователей к будущему стандарту smile

для меня он уже настоящий
(правда в пределах MSVC2010 =\ )

Автор: boostcoder 14.2.2011, 02:10

GoldFinch, а есть идеи, как избавиться от макроса?

Автор: GoldFinch 14.2.2011, 02:14

нормальных - пока нету

Автор: boostcoder 14.2.2011, 02:16

хватит на сегодня. спать. всем спасибо и сн.

Автор: GoldFinch 14.2.2011, 02:25

просто считайте что его там нет.
(наверное это самое эффективное решение)

Автор: boostcoder 14.2.2011, 02:39

GoldFinch, а в микрософтстудии constexpr реализован?

Автор: GoldFinch 14.2.2011, 02:43

boostcoder, неа, там вообще мало что реализовано,
лямбды, auto, decltype, r-value references

Автор: mes 14.2.2011, 02:55

Цитата(boostcoder @ 14.2.2011, 01:10

)

как избавиться от макроса

Код


template <size_t N>
constexpr size_t f() { return N *  f<N-1>(); }

template <>
constexpr size_t f<0>() { return 1; }


int main()
{
   std::cout << f<6>();
}

этот код работает ? тогда можно используя рекурсию шаблонов, создать хэш-итератор..
smile

Автор: boostcoder 14.2.2011, 03:00

Цитата(mes @ 14.2.2011, 02:55

)

этот код работает ?

да

Цитата(mes @ 14.2.2011, 02:55

)

тогда можно используя рекурсию шаблонов, создать хэш-итератор..

можно подробнее? ;)

Добавлено через 1 минуту и 18 секунд
расширил возможность использовать до 64ех символов.
вроде длинее быть не должно smile

Код


#include <iostream>

struct hash {
   static constexpr size_t f(size_t prevHash, char nextChar) { // FNV1-a 
      return nextChar ? size_t((prevHash ^ nextChar) * 16777619u) : prevHash;
   }
   template <size_t N>
   static constexpr size_t calc(const char (&s)[N]) {
      static_assert(N<130, "maximum 64 symbols allowed!");
      return
         f(f(f(f
            (f(f(f(f
               (f(f(f(f
                  (f(f(f(f(
                     f(f(f(f(
                        f(f(f(f
                           (f(f(f(f
                              (f(f(f(f(
                                 f(f(f(f(
                                    f(f(f(f
                                       (f(f(f(f
                                          (f(f(f(f
                                             (f(f(f(f
                                                (f(f(f(f(
                                                   f(f(f(f(
                                                      f(f(f(f(2166136261u
                                                      , s[0]), s[1]), s[2]), s[3])
                                                      , s[4]), s[5]), s[6]), s[7])
                                                      , s[8]), s[9]), s[10]), s[11])
                                                      , s[12]), s[13]), s[14]), s[15])
                                                      , s[16]), s[17]), s[18]), s[19])
                                                      , s[20]), s[21]), s[22]), s[23])
                                                      , s[24]), s[25]), s[26]), s[27])
                                                      , s[28]), s[29]), s[30]), s[31])
                                                      , s[32]), s[33]), s[34]), s[35])
                                                      , s[36]), s[37]), s[38]), s[39])
                                                      , s[40]), s[41]), s[42]), s[43])
                                                      , s[44]), s[45]), s[46]), s[47])
                                                      , s[48]), s[49]), s[50]), s[51])
                                                      , s[52]), s[53]), s[54]), s[55])
                                                      , s[56]), s[57]), s[58]), s[59])
                                                      , s[60]), s[61]), s[62]), s[63])
      ;
   }    
};

#define HASH(str) \
   hash::calc(str \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
   )
template <size_t N>
struct identity {
   static const size_t value = N;
};
int main() {
   std::cout << identity<HASH("1")>::value << std::endl;
   std::cout << identity<HASH("11")>::value << std::endl;
   std::cout << identity<HASH("111")>::value << std::endl;
   std::cout << identity<HASH("1111")>::value << std::endl;

   std::cout << identity<HASH("11111")>::value << std::endl;
   std::cout << identity<HASH("111111")>::value << std::endl;
   std::cout << identity<HASH("1111111")>::value << std::endl;
   std::cout << identity<HASH("11111111")>::value << std::endl;

   std::cout << identity<HASH("111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111")>::value << std::endl;

   std::cout << identity<HASH("1111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111")>::value << std::endl;

   std::cout << identity<HASH("11111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("1111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("11111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("1111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("11111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("11111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111111111111111111111")>::value << std::endl;

   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("11111111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("111111111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
   std::cout << identity<HASH("1111111111111111111111111111111111111111111111111111111111111111")>::value << std::endl;
}

Добавлено через 12 минут

Цитата(mes @ 14.2.2011, 02:55

)

этот код работает ?

забыл сказать, результат - 720

Добавлено через 12 минут и 59 секунд

Цитата(mes @ 14.2.2011, 02:55

)

тогда можно используя рекурсию шаблонов, создать хэш-итератор..

в смысле, чтоб избавиться от баяна чаров? вариант.

Автор: mes 14.2.2011, 16:33

Цитата(boostcoder @ 14.2.2011, 02:00

)

можно подробнее? ;)

вот примерно:

Код


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

допиливайте smile

Автор: mes 14.2.2011, 21:36

Цитата(boostcoder @ 14.2.2011, 02:00

)

static_assert(N<130, "maximum 64 symbols allowed!"...

нельзя ли прокомментировать, откуда взялось 130 ?! smile

Добавлено через 1 минуту и 13 секунд

Цитата(boostcoder @ 14.2.2011, 02:00

)

чтоб избавиться от баяна чаров?

а кто такой "баян" в данном контексте ?

Автор: boostcoder 14.2.2011, 21:47

Цитата(mes @ 14.2.2011, 21:36

)

нельзя ли прокомментировать, откуда взялось 130 ?!

не уверен, но полагаю, что это из-за нулевого символа добавляемого в конец хешируемой строки, и того = 129. или что?

Цитата(mes @ 14.2.2011, 21:36

)

а кто такой "баян" в данном контексте ?

вот. ну чем не баян? ;)

Цитата(boostcoder @ 14.2.2011, 03:00

)

      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \

Автор: mes 14.2.2011, 21:59

Цитата(boostcoder @ 14.2.2011, 20:47

)

не уверен, но полагаю,

все дошло.. я "баян" забыл посчитать.. smile

Добавлено через 1 минуту и 7 секунд
а пример тремя постами выше с шаблонной рекурсией подошел ? или еще не пробовали ?

Автор: boostcoder 14.2.2011, 22:03

Цитата(mes @ 14.2.2011, 21:59

)

или еще не пробовали ?

завтра буду пробовать. сегодня повод, как ни как smile

Добавлено через 11 минут и 55 секунд
вот.
проверил.
ничего не пришлось допиливать smile

Код


#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[] = "1234";
   std::cout << std::hex << hash(a) << std::endl;
   std::cout << std::hex << hash("1234") << std::endl;
}

Автор: GoldFinch 14.2.2011, 22:17

кстати да, FNV1-a не лучший хеш для этой задачи, надо бы поискать что получше

Автор: boostcoder 14.2.2011, 22:19

Цитата(GoldFinch @ 14.2.2011, 22:17

)

FNV1-a не лучший хеш для этой задачи

гугл меня вчера завел на какой-то сайт, и там была куча его разновидностей, и букв. потому не осилил smile

Добавлено через 5 минут и 58 секунд
тему переименовал. не теряйтесь smile

Автор: Abyx 16.2.2011, 01:29

нда.. похоже что кроме как генерацией кучи шаблонов, циклов для constexpr не получить.

насчет хеширования строк:
http://bretm.home.comcast.net/~bretm/hash/7.html - если верить этой статье, Bob Jenkins' hash достаточно хорош для строк (а crc32 очень плох)
надо будет попробовать реализовать его для constexpr.

код: http://burtleburtle.net/bob/c/lookup3.c

Автор: Abyx 16.2.2011, 13:11

также надо бы подумать о надежном применении хешей для switch
как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e
можно также потребовать чтобы коллизий не было во всей единице трансляции, это слишком строгое требование, но возможно его проще реализовать

Автор: mes 16.2.2011, 20:10

Цитата(Abyx @ 16.2.2011, 12:11

)

как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e

ну switch, насколько я знаю, просто напросто не нужен.. а для проверки коллизий, можно использовать карту соответствий, которая так и так составляется.. исхожу из ранее приведенных boostcoder`ом данных.
smile

Автор: boostcoder 16.2.2011, 20:15

Цитата(Abyx @ 16.2.2011, 13:11

)

как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e

не понимаю в чем проблема... если коллизия произойдет, компилятор вам об этом скажет:

Цитата

error: duplicate case value
error: previously used here

Автор: Abyx 16.2.2011, 20:28

хм.. действительно