Мой std::hash для std::tuples Есть улучшения?

Некоторые могли заметить, что std::hash не поддерживает кортежи. Поэтому я добавил перегрузку, которая кажется «лучше», чем решение, которое я видел до сих пор. У кого-нибудь есть идеи по дальнейшему сокращению этого кода? Обратите внимание, что это убийца компилятора! Единственным, кто смог его скомпилировать, был "Clang 3.2"... Компилятор Intel 13.1 не получает специализации и продолжает говорить "Стандарт C++ не поддерживает хэш-блабла". И нам не нужно говорить об оригинальном компиляторе Microsoft, не так ли?

Кстати, мое решение поддерживает рекурсивные кортежи, такие как std::tuple<std::tuple<int,int>,int>, поэтому я не уверен, относится ли это также к существующим решениям, которые я видел сегодня.

namespace std
{
    template<typename... TTypes>
    class hash<std::tuple<TTypes...>>
    {
    private:
        typedef std::tuple<TTypes...> Tuple;

        template<int N>
        size_t operator()(Tuple value) const { return 0; }

        template<int N, typename THead, typename... TTail>
        size_t operator()(Tuple value) const
        {
            constexpr int Index = N - sizeof...(TTail) - 1;
            return hash<THead>()(std::get<Index>(value)) ^ operator()<N, TTail...>(value);
        }

    public:
        size_t operator()(Tuple value) const
        {
            return operator()<sizeof...(TTypes), TTypes...>(value);
        }
    };
}

person thesaint    schedule 27.02.2013    source источник
comment
gcc может скомпилировать это (по крайней мере, gcc 4.7)   -  person nmikhailov    schedule 27.02.2013
comment
В кортеже Boost уже есть правильная реализация. Я бы просто скопировал это.   -  person Kerrek SB    schedule 27.02.2013
comment
Технически, я думаю, вы на самом деле объявляете новый шаблон с параметрами template‹typename... TTypes›, а не специализируете существующий шаблон с параметрами template‹T›... что было технически недопустимо для стандартных шаблонов в C+ +03, насколько я понимаю... так что возможно, что это не соответствует требованиям, если вы оставите его в пространстве имен std... хотя я не уверен, что это все еще так в С++ 11   -  person Stephen Lin    schedule 27.02.2013
comment
См. раздел с предостережениями здесь: en.wikibooks.org/wiki/More_C% 2B%2B_Idioms/Non-throwing_swap (о std::swap, но должно применяться и к std::hash)   -  person Stephen Lin    schedule 27.02.2013
comment
@Kerrek: Boost, к сожалению, имеет привычку делать вещи намного сложнее, чем они есть на самом деле, потому что у них есть этот старый багаж компилятора, который нужно носить с собой. Я хочу, чтобы это было как можно короче и милее.   -  person thesaint    schedule 27.02.2013
comment
@StephenLin: На самом деле не читал, но взглянул. Поскольку GCC 4.7 и Clang 3.2, кажется, компилируют это, я думаю, все должно быть в порядке, поскольку Clang, как известно, чрезвычайно соответствует стандарту, он должен по крайней мере выдавать предупреждение, если что-то необычное. Кроме того, я не хочу взорвать его, я хочу сократить код, если что.   -  person thesaint    schedule 27.02.2013
comment
На самом деле хэш - это функтор, а не функция, поэтому, возможно, это другое. Во всяком случае, я только что задал новый вопрос об этом, если вам любопытно ... в любом случае, это, вероятно, не то, что мешает вашему шаблону скомпилироваться на всех компиляторах, поэтому я не стал ссылаться на это.   -  person Stephen Lin    schedule 27.02.2013
comment
Хорошо, по-видимому, это незаконно, если вам небезразличны такие вещи: D (вы всегда можете поместить его в другое пространство имен и указать его явно)   -  person Stephen Lin    schedule 27.02.2013
comment
@thesaint: Нет, я обычно копировал пятистрочный hash_combine Boost и использовал для хэширования всевозможные вещи. Это очень прямолинейно. Я думаю, что это просто было забыто в стандарте.   -  person Kerrek SB    schedule 27.02.2013
comment
@KerrekSB, это не было забыто, это было предложено для TR1, но предложение не было достаточно зрелым, и когда cplusplus.github.com/LWG/lwg-closed.html#1317 был предложен для C++0x, было слишком поздно для новых функций, поэтому мы проголосовали за него NAD Future   -  person Jonathan Wakely    schedule 27.02.2013
comment
@StephenLin, это специализация, а не новый шаблон, имя шаблона класса - это идентификатор шаблона в форме hash<tuple<TTypes...>>, поэтому это должна быть (частичная) специализация, также это должна быть специализация, а не специализация. новый шаблон, потому что вы не можете перегружать шаблоны классов. Это недопустимо, потому что не связано с пользовательским типом.   -  person Jonathan Wakely    schedule 27.02.2013
comment
@thesaint, XOR - не лучший способ объединить хэш-значения   -  person Jonathan Wakely    schedule 27.02.2013
comment
@JonathanWakely: Ну, это довольно бесполезное утверждение. Если что-нибудь укажите причины, ссылки на то, почему, а также то, что вы бы порекомендовали. Кроме того, XOR стабилен. Если вы используете хорошие хэш-функции, такие как первые 64 бита SHA-160, то XOR — это идеальный способ смешивания хеш-значений. Таким образом, ваш комментарий определенно заслуживает уточнения... Для обычных глупых хэш-функций поворот влево около индекса * 13 бит или около того перед XOR может быть лучшим выбором.   -  person thesaint    schedule 27.02.2013
comment
@JonathanWakely ааа, хорошо, моя ошибка   -  person Stephen Lin    schedule 27.02.2013
comment
@thesaint любой кортеж с четным количеством одинаковых элементов, независимо от их значений, всегда будет хешироваться до всех 0 за одно.   -  person Stephen Lin    schedule 27.02.2013
comment
(Кроме того, одни и те же значения в другом порядке будут хешироваться одинаково.)   -  person Stephen Lin    schedule 27.02.2013
comment
@JonathanWakely: Интересно. Почему его не считали достаточно зрелым? Это похоже на довольно простой алгоритм...?   -  person Kerrek SB    schedule 27.02.2013
comment
@StephenLin: Хорошо, это может быть проблемой, в зависимости от приложения. Поворот влево-XOR должен позаботиться об этом...   -  person thesaint    schedule 28.02.2013
comment
@thesaint, просто XOR не является хорошей хеш-функцией, потому что, например, {1,2,3,4} сталкивается с {4,3,2,1}   -  person Jonathan Wakely    schedule 28.02.2013
comment
Вышеупомянутый план является неопределенным поведением. Вы можете специализировать template только в namespace std на пользовательских типах или типах, которые зависят от пользовательских типов. Вышеприведенное не проходит этот тест.   -  person Yakk - Adam Nevraumont    schedule 14.05.2014


Ответы (1)


Совершенно очевидно, как только вы это видели:

template<int N, typename THead, typename... TTail>
size_t operator()(Tuple value) const
{
  constexpr int Index = N - sizeof...(TTail) - 1;
  return hash<THead>()(std::get<Index>(value)) ^ operator()<N, TTail...>(value);
}
person Daniel Frey    schedule 27.02.2013
comment
LOL, да, спасибо .. Вот что происходит, если вы готовите решение, пока оно не сработает. Я применил это выше! - person thesaint; 28.02.2013
comment
Еще один: вы должны взять параметр как const Tuple& value вместо того, чтобы постоянно создавать копии во всех трех местах. - person Daniel Frey; 28.02.2013
comment
Смотря как. Но, наверное, и в этом случае не помешает. C++11 имеет новую идиому, позволяющую избежать const& и вместо этого использовать передачу по значению. Хм, ход-семантика. LOL Я не знаю, почему больше. Семантика перемещения, похоже, тоже не решает эту проблему. Похоже на комбинацию. Семантика перемещения для RValues ​​и внутренняя оптимизация компилятора для LValues. Мне использование const& кажется преждевременной оптимизацией, если только вам не нужно наследование. - person thesaint; 28.02.2013
comment
Нет, ваш приведенный выше код (Tuple value) ничего не перемещает, когда ваши функции вызывают друг друга. Он создает копии. Ваша единственная надежда - это оптимизатор, и я бы не стал полагаться на это. - person Daniel Frey; 28.02.2013
comment
Я согласен с вами, семантика заключается в копировании... Но люди часто склонны недооценивать сегодняшние компиляторы. Я оптимизирую O(1) только тогда, когда мне об этом говорит профайлер ;). Конечно, автор библиотеки STD должен думать иначе. - person thesaint; 28.02.2013
comment
Вышеприведенный симметричный хэш означает, что make_tuple( 0, 0 ) и make_tuple( 1, 1 ) имеют хэш 0. Во-вторых, специализация hash в std для std::tuple< Ts... > является неопределенным поведением, поскольку вы можете специализировать template в namespace std только для пользовательских типов или типов, которые зависят от пользовательских типов. - person Yakk - Adam Nevraumont; 14.05.2014
comment
@Yakk Вы правы насчет симметричной части, которую можно легко улучшить, используя некоторый код (hash_combine) из этого ответа, который я дал на другой вопрос. Для части неопределенного поведения: нет, определяемое пользователем не означает, что оно находится за пределами пространства имен std, это просто означает, что это класс. См. комментарии к ответу, который я связал. - person Daniel Frey; 14.05.2014
comment
@DanielFrey, вы утверждали, что типы (например, std::vector) в пространстве имен std являются UDT, но я не видел, чтобы это обсуждалось. Просто утверждал. Кажется, вы думаете, что user-defined type означает non-fundamental type, и я не могу найти для этого оправдания в стандарте. Я только что искал его (текущий черновик) для «определяемого пользователем типа» и «определяемого пользователем» и не нашел пункта, который подразумевал бы, что std::vector является типом, определяемым пользователем. Каждое использование «определяемого пользователем типа», кажется, имеет смысл, если оно относится только к типам, которые определяют пользователи (а std:: не является пользователем). Я что-то пропустил? - person Yakk - Adam Nevraumont; 14.05.2014
comment
@DanielFrey Задал вопрос по этой проблеме здесь - person Yakk - Adam Nevraumont; 14.05.2014