Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> string hashing in compile-time, хеш 
V
    Опции темы
boostcoder
Дата 12.2.2011, 05:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



есть необходимость, в качестве ID`а для получения некоторого объекта, использовать строку. сейчас этот способ работает в run-time, и работает не плохо. но это делает невозможным статическую проверку соответствия типов, по понятным причинам.
гуглением, нашел алгоритм создания хеш-суммы строки в compile-time: http://arcticinteractive.com/2009/04/18/co...hing-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/b3380d0e18eb...22710478202c062

Это сообщение отредактировал(а) boostcoder - 14.2.2011, 22:25
PM WWW   Вверх
boostcoder
Дата 12.2.2011, 09:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



наверное, правильнее не подстраиваться под имеющуюся реализацию, а написать подходящую, не использующую boost::mpl::string.
PM WWW   Вверх
GoldFinch
Дата 12.2.2011, 14:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26



Цитата(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-...ng-hash-at.html
хотя полученные им хеши не константы времени компиляции, фактически они получаются во время компиляции, может это можно как-то использовать.
PM MAIL ICQ   Вверх
boostcoder
Дата 13.2.2011, 06:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



Цитата(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/co...hing-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/6d3cdaf592c7...d84591ef10fa51d

Это сообщение отредактировал(а) boostcoder - 13.2.2011, 06:25
PM WWW   Вверх
mes
Дата 13.2.2011, 12:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата(boostcoder @  13.2.2011,  05:15 Найти цитируемый пост)
 что при записи подряд более 4ех символов, последние будут игнорировать.

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

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



--------------------
PM MAIL WWW   Вверх
boostcoder
Дата 13.2.2011, 13:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



Цитата(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;

PM WWW   Вверх
mes
Дата 13.2.2011, 13:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата(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...1931740/13.html
избавиться от _3 в LIST_OF_CHARS_3 тоже можно посредством эллипсиса.. 




--------------------
PM MAIL WWW   Вверх
boostcoder
Дата 13.2.2011, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



Цитата(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 
ну не вижу я другого решения...
PM WWW   Вверх
mes
Дата 13.2.2011, 13:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата

#define char_a  

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



--------------------
PM MAIL WWW   Вверх
boostcoder
Дата 13.2.2011, 14:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



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

Цитата(boostcoder @  13.2.2011,  13:53 Найти цитируемый пост)
или, привязать пользователей к gcc-4.6

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

Добавлено через 28 секунд
Цитата(mes @  13.2.2011,  13:55 Найти цитируемый пост)
это естественно менятся на  что то типа : struct char_a { enum { value = 'a'}; };

да. я понял.
PM WWW   Вверх
mes
Дата 13.2.2011, 14:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата(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"
)}
...



--------------------
PM MAIL WWW   Вверх
boostcoder
Дата 13.2.2011, 14:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



Цитата(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 выйдет..

Это сообщение отредактировал(а) boostcoder - 13.2.2011, 15:01
PM WWW   Вверх
mes
Дата 13.2.2011, 16:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата(boostcoder @  13.2.2011,  13:17 Найти цитируемый пост)
но сейчас нет статической проверки типов. 

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

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

Код


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

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

?



--------------------
PM MAIL WWW   Вверх
boostcoder
Дата 13.2.2011, 16:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110



Цитата(mes @  13.2.2011,  16:37 Найти цитируемый пост)
вот что к примеру мешает сейчас добавить макрос, для такого использования?

ничего не мешает. просто я стремился избавиться от макросов и другой кодогенерации. и сейчас нет ни одного макроса. хотелось бы чтоб так и осталось smile 
PM WWW   Вверх
mes
Дата 13.2.2011, 16:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250



Цитата(boostcoder @  13.2.2011,  15:43 Найти цитируемый пост)
ничего не мешает. просто я стремился избавиться от макросов и другой кодогенерации

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

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



Это сообщение отредактировал(а) mes - 13.2.2011, 16:47


--------------------
PM MAIL WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »


 




[ Время генерации скрипта: 0.0959 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.