Как специализировать std :: hash <Key> :: operator () для пользовательского типа в неупорядоченных контейнерах?

101

Для поддержки ключевых типов , определяемых пользователем в std::unordered_set<Key>и std::unordered_map<Key, Value> один должен обеспечивать operator==(Key, Key)и хэш - функтор:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

Было бы удобнее писать просто std::unordered_set<X> с хешем по умолчанию для типа X, как для типов, поставляемых вместе с компилятором и библиотекой. После консультации

кажется возможным специализироваться std::hash<X>::operator():

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
  // or
  // hash<X>::operator()(X x) const { return hash<int>()(x.id); }     // works for g++ 4.7, but not for VC10 
}                                                                             

Учитывая, что компилятор поддерживает C ++ 11, пока что экспериментальный --- я не пробовал Clang ---, вот мои вопросы:

  1. Законно ли добавлять такую ​​специализацию в пространство имен std? У меня смешанные чувства по этому поводу.

  2. Какая из std::hash<X>::operator()версий, если таковые имеются, соответствует стандарту C ++ 11?

  3. Есть ли портативный способ сделать это?

Рене Рихтер
источник
С gcc 4.7.2 я должен был предоставить глобалoperator==(const Key, const Key)
Виктор Любославский
Обратите внимание, что специализация std::hash(в отличие от других вещей в stdпространстве имен) не поощряется руководством по стилю Google ; воспринимайте это с недоверием.
Франклин Ю,

Ответы:

128

Вам прямо разрешено и рекомендуется добавлять специализации в пространство имен std*. Правильный (и в основном единственный) способ добавить хеш-функцию таков:

namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

(Другими популярными специализациями, которые вы можете поддержать, являются std::less, std::equal_toи std::swap.)

*) полагаю, если один из задействованных типов определяется пользователем.

Керрек С.Б.
источник
3
хотя это возможно, вы бы в целом порекомендовали это сделать? Я бы предпочел unorder_map<eltype, hash, equality>вместо этого создание экземпляра , чтобы не испортить кому-то день забавным ADL-бизнесом. ( Отредактируйте совет Пита Беккера по этой теме )
см.
2
@sehe: Если у вас есть хеш-функтор, который, возможно, может быть сконструирован по умолчанию, но почему? (Равенство проще, поскольку вы просто реализуете member- operator==.) Моя общая философия заключается в том, что если функция является естественной и по существу единственно «правильной» (например, сравнение лексикографических пар), я добавляю ее к std. Если это что-то особенное (например, сравнение неупорядоченных пар), я делаю это специфичным для типа контейнера.
Kerrek SB
3
Я не возражаю, но где в стандарте нам разрешено и рекомендуется добавлять специализации в std?
razeh 02
3
@Kerrek, я согласен, но я надеялся на ссылку в главе и стихе на место в стандарте. Я нашел формулировку, разрешающую инъекцию в 17.6.4.2.1, где говорится, что это не разрешено «если не указано иное», но я не смог найти «иначе определенную» часть среди 4000+ страниц спецификации.
razeh 02
3
@razeh здесь вы можете прочитать: «Программа может добавить специализацию шаблона для любого шаблона стандартной библиотеки в пространство имен std, только если объявление зависит от определенного пользователем типа, а специализация соответствует требованиям стандартной библиотеки для исходного шаблона и не запрещена явно. . ". Так что это решение в порядке.
Marek R
7

Я бы сделал ставку на аргумент шаблона Hash для классов unordered_map / unorder_set / ...:

#include <unordered_set>
#include <functional>

struct X 
{
    int x, y;
    std::size_t gethash() const { return (x*39)^y; }
};

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;

int main()
{
    auto hashX = [](const X&x) { return x.gethash(); };

    Xunset  my_set (0, hashX);
    Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef
}

Конечно

  • hashX также может быть глобальной статической функцией
  • во втором случае вы можете передать это
    • старомодный объект-функтор ( struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • любое выражение привязки, удовлетворяющее подписи -
sehe
источник
Я ценю, что вы можете написать что-то, что не имеет конструктора по умолчанию, но я всегда нахожу, что требовать от каждой конструкции карты запоминать дополнительный аргумент - это немного обременительно - на мой вкус, это слишком большая нагрузка. Я согласен с явным аргументом о шаблоне, хотя специализация std::hashпо-прежнему является
лучшим
на помощь приходят определяемые пользователем типы :-) А если серьезно, я надеюсь, что мы ударили бы их по запястьям уже на этапе, когда их класс содержит char*!
Kerrek SB
Хм ... у вас есть пример, как hashспециализация мешает через ADL? Я имею в виду, это вполне правдоподобно, но мне сложно придумать проблемный случай.
Kerrek SB
Это все развлечения и игры, пока вам не понадобится, std::unordered_map<Whatever, Xunset>и это не работает, потому что ваш Xunsetтип хешера не может быть сконструирован по умолчанию.
Брайан Гордон
4

@Kerrek SB рассмотрел пункты 1) и 3).

2) Несмотря на то, что g ++ и VC10 объявляются std::hash<T>::operator()с разными подписями, обе реализации библиотеки соответствуют стандарту.

Стандарт не определяет членов std::hash<T>. Он просто говорит, что каждая такая специализация должна удовлетворять тем же требованиям «хеширования», которые необходимы для второго аргумента шаблона std::unordered_setи так далее. А именно:

  • Тип хэша H- это объект функции, по крайней мере, с одним типом аргумента Key.
  • H копирует конструкцию.
  • H разрушаемо.
  • Если h- выражение типа Hили const H, а kвыражение типа, конвертируемого в (возможно const) Key, то h(k)является допустимым выражением с типом size_t.
  • Если hявляется выражением типа Hили const H, и uявляется l-значением типа Key, то h(u)является допустимым выражением с типом, size_tкоторый не изменяется u.
Aschepler
источник
Нет, ни одна из реализаций не соответствует стандартам, поскольку они пытаются специализироваться, std::hash<X>::operator()а не std::hash<X>в целом, а сигнатура std::hash<T>::operator()определяется реализацией.
ildjarn
@ildjarn: Уточнено - я говорил о реализациях библиотеки, а не о предпринятых специализациях. Не уверен, что именно ОП хотел спросить.
aschepler