Bagaimana cara mengkhususkan std :: hash <Key> :: operator () untuk tipe yang ditentukan pengguna dalam wadah tak berurutan?

Untuk mendukung jenis kunci yang ditentukan pengguna std::unordered_set<Key>dan std::unordered_map<Key, Value> harus menyediakan operator==(Key, Key)dan fungsi hash:

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;

Akan lebih mudah untuk menulis hanya std::unordered_set<X> dengan hash default untuk tipe X, seperti untuk tipe yang disertakan dengan kompilator dan pustaka. Setelah berkonsultasi

• C ++ Standard Draft N3242 §20.8.12 [unord.hash] dan §17.6.3.4 [hash.requirements],
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• berbagai pertanyaan terkait di Stack Overflow

tampaknya mungkin untuk mengkhususkan 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 
}                                                                             

Mengingat dukungan compiler untuk C ++ 11 masih bersifat eksperimental --- Saya tidak mencoba Clang ---, ini adalah pertanyaan saya:

1. Apakah legal menambahkan spesialisasi seperti itu ke namespace std? Saya memiliki perasaan campur aduk tentang itu.

2. std::hash<X>::operator()Versi manakah , jika ada, yang sesuai dengan standar C ++ 11?

3. Apakah ada cara portabel untuk melakukannya?

Anda secara tegas diizinkan dan didorong untuk menambahkan spesialisasi ke namespace std*. Cara yang benar (dan pada dasarnya hanya) untuk menambahkan fungsi hash adalah ini:

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

(Spesialisasi populer lainnya yang mungkin Anda pertimbangkan untuk didukung adalah std::less, std::equal_todan std::swap.)

_{*) selama salah satu tipe yang terlibat ditentukan oleh pengguna, saya kira.}

Taruhan saya akan berada pada argumen template Hash untuk kelas 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
}

Tentu saja

• hashX juga bisa menjadi fungsi statis global
• dalam kasus kedua, Anda bisa melewati itu
  • objek functor kuno ( struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • ekspresi ikatan apa pun yang memenuhi tanda tangan -

@Kerrek SB telah meliput 1) dan 3).

2) Meskipun g ++ dan VC10 mendeklarasikan std::hash<T>::operator()dengan tanda tangan berbeda, kedua implementasi library tersebut sesuai dengan Standar.

Standar tidak menentukan anggota std::hash<T>. Ini hanya mengatakan bahwa setiap spesialisasi tersebut harus memenuhi persyaratan "Hash" yang sama yang diperlukan untuk argumen template kedua std::unordered_setdan seterusnya. Yaitu:

• Jenis hash Hadalah objek fungsi, dengan setidaknya satu jenis argumen Key.
• H adalah salinan dapat dibangun.
• H dapat dirusak.
• Jika hmerupakan ekspresi tipe Hatau const H, dan kmerupakan ekspresi tipe yang dapat diubah menjadi (mungkin const) Key, maka h(k)ekspresi valid dengan tipe size_t.
• Jika hmerupakan ekspresi tipe Hatau const H, dan umerupakan nilai tipe l Key, maka h(u)ekspresi valid dengan tipe size_tyang tidak dimodifikasi u.