unordered_map
整数でペアをマップするを作成しようとしています:
#include <unordered_map>
using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;
Unordered_map
をプライベート メンバーとして宣言したクラスがあります。
しかし、コンパイルしようとすると次のエラーが発生します。
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: 未定義のテンプレート 'std::__1::hash、std::__1::basic_string > >' の暗黙的なインスタンス化
map<pair<string, string>, int>
の代わりに のような通常のマップを使用すると、このエラーは発生しませんunordered_map
。
pair
順序付けられていないマップでキーとして使用することはできませんか?
ベストアンサー1
キーの種類に適したハッシュ関数を提供する必要があります。簡単な例:
#include <unordered_map>
#include <functional>
#include <string>
#include <utility>
// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Mainly for demonstration purposes, i.e. works but is overly simple
// In the real world, use sth. like boost.hash_combine
return h1 ^ h2;
}
};
using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;
int main() {
Unordered_map um;
}
これは動作しますが、ハッシュプロパティは最適ではありません†。次のようなものを見てみるのもいいかもしれません。boost.hash_combine
ハッシュを組み合わせる際に、より高品質な結果を得ることができます。これについては、前述のboostのソリューションを含め、さらに詳しく説明されています。この答え。
実用上: Boostは関数セットも提供しているhash_value
std::pair
は、 およびstd::tuple
ほとんどの標準コンテナのハッシュ関数を既に提供しています。
†より正確に言うと、衝突が多すぎます。たとえば、対称ペアはすべてハッシュ値が 0 になり、順列のみが異なるペアは同じハッシュになります。これはプログラミング演習にはおそらく問題ありませんが、実際のコードのパフォーマンスに深刻な悪影響を与える可能性があります。