Como especializar std :: hash :: operator () para o tipo definido pelo usuário em contêineres não ordenados?

Para suportar tipos de chaves definidos pelo usuário em std::unordered_set e std::unordered_map é necessário fornecer operator==(Key, Key) e um functor 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()(x.id); } }; std::unordered_set s; 

Seria mais conveniente escrever apenas std::unordered_set com um hash padrão para o tipo X , como para os tipos que vêm junto com o compilador e a biblioteca. Depois de consultar

  • Esboço Padrão C32 N3242 §20.8.12 [unord.hash] e §17.6.3.4 [hash.requirements],
  • Boost.Unordered
  • g ++ include\c++\4.7.0\bits\functional_hash.h
  • VC10 include\xfunctional
  • várias questões relacionadas no Stack Overflow

parece possível especializar std::hash::operator() :

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

Dado suporte ao compilador para C + + 11 ainda é experimental — Eu não tentei Clang —, estas são as minhas perguntas:

  1. É legal adicionar essa especialização ao namespace std ? Eu tenho sentimentos mistos sobre isso.

  2. Qual das versões std::hash::operator() , se houver, é compatível com o padrão C ++ 11?

  3. Existe uma maneira portátil de fazer isso?

    Você está expressamente autorizado e incentivado a adicionar especializações ao namespace std *. A maneira correta (e basicamente única) de adicionar uma function hash é esta:

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

    (Outras especializações populares que você pode considerar como suporte são std::less , std::equal_to e std::swap .)

    *) desde que um dos tipos envolvidos seja definido pelo usuário, suponho.

    Minha aposta seria no argumento do template Hash para as classs unordered_map / unorder_set / …:

     #include  #include  struct X { int x, y; std::size_t gethash() const { return (x*39)^y; } }; typedef std::unordered_set Xunset; typedef std::unordered_set > 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 } 

    Claro

    • O hashX também poderia ser uma function estática global
    • no segundo caso, você poderia passar isso
      • o object functor antiquado ( struct Xhasher { size_t operator(const X&) const; }; )
      • std::hash()
      • qualquer expressão de binding satisfazendo a assinatura –

    @Kerrek SB cobriu 1) e 3).

    2) Mesmo que g + + e VC10 declarem std::hash::operator() com assinaturas diferentes, ambas as implementações da biblioteca são compatíveis com o padrão.

    O padrão não especifica os membros de std::hash . Apenas diz que cada especialização deve satisfazer os mesmos requisitos de “Hash” necessários para o segundo argumento de modelo de std::unordered_set e assim por diante. Nomeadamente:

    • Hash tipo H é um object de function, com pelo menos um tipo de argumento Key .
    • H é cópia construtível.
    • H é destrutível.
    • Se h é uma expressão do tipo H ou const H , k é uma expressão de um tipo convertível para (possivelmente const ) Key , então h(k) é uma expressão válida com o tipo size_t .
    • Se h é uma expressão do tipo H ou const H , e u é um lvalue do tipo Key , então h(u) é uma expressão válida com o tipo size_t que não modifica u .