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

Question

Для поддержки пользовательских типов ключей в 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, как для типов, поставляемых вместе с компилятором и библиотекой.После консультации

• Стандарт C ++ Черновик N3242 §20.8.12 [unord.hash] и §17.6.3.4 [hash.requirements],
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• различные связанные вопросы s в переполнении стека

кажется возможным специализироваться 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. Существует ли портативный способсделать это?

Answer 1

Вам явно разрешено добавлять специализаций в пространство имен 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.)

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

Answer 2

Моя ставка будет на аргумент шаблона 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>()
  • любое выражение связывания, удовлетворяющее сигнатуре -

Answer 3

@ 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 является lvalue типа Keyтогда h(u) является допустимым выражением с типом size_t, которое не изменяет u.