std::unordered_map<tuple<int, int>, string>箱から出してすぐに動作しないのはなぜですか? のハッシュ関数を定義しなければならないのは面倒ですtuple<int, int>。
template<> struct do_hash<tuple<int, int>>
{ size_t operator()(std::tuple<int, int> const& tt) const {...} };
タプルをキーとして順序付けされていないマップを構築する(Matthieu M.) は、これを自動化する方法を示していますboost::tuple。可変個引数テンプレートを使用せずに c++0x タプルに対してこれを行う方法はありますか?
確かにこれは標準にあるはずです:(
これは gcc 4.5 で機能し、標準のハッシュ可能な型を含むすべての c++0x タプルを
追加の手間をかけずunordered_mapにメンバーにすることができます。unordered_set(コードをヘッダー ファイルに入れ、インクルードするだけです。)
関数は、引数依存の名前検索 (ADL) によって取得されるように、std 名前空間に存在する必要があります。
もっと簡単な解決策はありますか？
#include <tuple>
namespace std{
namespace
{
// Code from boost
// Reciprocal of the golden ratio helps spread entropy
// and handles duplicates.
// See Mike Seymour in magic-numbers-in-boosthash-combine:
// http://stackoverflow.com/questions/4948780
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl
{
static void apply(size_t& seed, Tuple const& tuple)
{
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, std::get<0>(tuple));
}
};
}
template <typename ... TT>
struct hash<std::tuple<TT...>>
{
size_t
operator()(std::tuple<TT...> const& tt) const
{
size_t seed = 0;
HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
return seed;
}
};
}
Yakk は、std 名前空間での特殊化は実際には未定義の動作であると指摘しています。標準に準拠したソリューションが必要な場合は、このコードをすべて独自の名前空間に移動し、ADL が適切なハッシュ実装を自動的に見つけるという考えを放棄する必要があります。それ以外の ：
unordered_set<tuple<double, int> > test_set;
必要なもの:
unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;
hash_tupleではなく、独自の名前空間ですstd::。
hash_tupleこれを行うには、まず名前空間内でハッシュの実装を宣言する必要があります。これにより、タプル以外のすべての型が に転送されますstd::hash。
namespace hash_tuple{
template <typename TT>
struct hash
{
size_t
operator()(TT const& tt) const
{
return std::hash<TT>()(tt);
}
};
}
hash_combine呼び出しhash_tuple::hashではないことを確認してくださいstd::hash
namespace hash_tuple{
namespace
{
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
}
次に、他のすべての前のコードを含めますが、内部に入れnamespace hash_tupleずに入れますstd::
namespace hash_tuple{
namespace
{
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl
{
static void apply(size_t& seed, Tuple const& tuple)
{
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple,0>
{
static void apply(size_t& seed, Tuple const& tuple)
{
hash_combine(seed, std::get<0>(tuple));
}
};
}
template <typename ... TT>
struct hash<std::tuple<TT...>>
{
size_t
operator()(std::tuple<TT...> const& tt) const
{
size_t seed = 0;
HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
return seed;
}
};
}
#include <boost/functional/hash.hpp>
#include <tuple>
namespace std
{
template<typename... T>
struct hash<tuple<T...>>
{
size_t operator()(tuple<T...> const& arg) const noexcept
{
return boost::hash_value(arg);
}
};
}
私の C++0x ドラフトで20.8.15は、ハッシュは組み込み型 (ポインターを含むが、それらの逆参照を意味するものではないようです) に特化していると述べています。またerror_code、bitset<N>、unique_ptr<T, D>、shared_ptr<T>、typeindex、string、u16string、u32string、wstring、vector<bool, Allocator>およびに特化しているようthread::idです。（魅力的なリスト！）
私は C++0x の可変引数を使用していないので、私の書式設定はおそらくかなりずれていますが、これらの行に沿った何かがすべてのタプルで機能する可能性があります。
size_t hash_combiner(size_t left, size_t right) //replacable
{ return left + 0x9e3779b9 + (right<<6) + (right>>2);}
template<int index, class...types>
struct hash_impl {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
hash_impl<index-1, types...> next;
size_t b = std::hash<nexttype>()(std::get<index>(t));
return next(hash_combiner(a, b), t);
}
};
template<class...types>
struct hash_impl<0, types...> {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
size_t b = std::hash<nexttype>()(std::get<0>(t));
return hash_combiner(a, b);
}
};
template<class...types>
struct tuple_hash<std::tuple<types...>> {
size_t operator()(const std::tuple<types...>& t) {
const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
return hash_impl<begin, types...>()(0, t);
}
}
Yakk は、ユーザー定義型に依存しない宣言を使用して標準ライブラリ テンプレートを特殊化しているため、std::hash直接特殊化することは技術的に許可されていないことに気付きました。