115

でユーザー定義のキータイプをサポート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. それを行うためのポータブルな方法はありますか？

4

3 に答える 3

145

名前空間*に特殊化を追加することが明示的に許可され、推奨されています。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です。)

*) 関連する型の 1 つがユーザー定義である限り、私はそう思います。

于 2011-11-16T20:07:56.610 に答える
7

私の賭けは、unordered_map/unorder_set/... クラスの Hash テンプレート引数にあります。

#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 は、グローバルな静的関数でもかまいません
  • 2番目のケースでは、それを渡すことができます
    • 昔ながらのファンクター オブジェクト ( struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • 署名を満たす任意のバインド式 -
于 2011-11-16T20:36:29.343 に答える
4

@Kerrek SBは1）と3）をカバーしています。

2）g ++とVC10std::hash<T>::operator()は異なる署名で宣言しますが、両方のライブラリ実装は標準に準拠しています。

標準では、のメンバーは指定されていませんstd::hash<T>。このような各特殊化は、の2番目のテンプレート引数に必要な同じ「ハッシュ」要件を満たさなければならないというだけですstd::unordered_set。すなわち：

  • ハッシュ型Hは関数オブジェクトであり、少なくとも1つの引数型がありKeyます。
  • Hコピー構築可能です。
  • H破壊可能です。
  • hがタイプHまたはの式const Hであり、が（おそらく）にk変換可能なタイプの式である場合、はタイプが有効な式です。constKeyh(k)size_t
  • hが型Hまたはの式const Hであり、uが型の左辺値である場合Key、はを変更しないh(u)型の有効な式です。size_tu
于 2011-11-16T20:24:50.677 に答える