カスタムアロケータの basic_string を unordered_map のキーにする方法

問題

カスタムアロケータで特殊化した文字列型を使っていると、そのままでは unordered_map のキーにできません。

using MyString = std::basic_string<
                     char, 
                     std::char_traits<char>,
                     MyAllocator<char>>;

...

std::unordered_map<MyString, int> umap; // エラー！

unordered_map が必要とする std::hash<T> は std::hash<std::string> は定義されていますが、アロケータ特殊化した文字列型の定義がないためです。

対処法

作った型に特殊化した std::hash<MyString> を自分で定義します。

C++17 環境であれば、std::hash<std::string_view> がつかえるので実装は簡単です。

c++17版

template <>
struct std::hash<MyString>
{
    std::size_t operator()(const MyString& k) const
    {
        const std::string_view sv{k.c_str(), k.length()};
        return std::hash<std::string_view>()(sv);
    }
};

C++14 までの場合でも boost が使えるなら boost に頼りましょう。

boost版

#include <boost/functional/hash.hpp>

template <>
struct std::hash<MyString>
{
    std::size_t operator()(const MyString& k) const
    {
        return boost::hash_range(k.begin(), k.end());
    }
};

どちらも使えない場合はハッシュ関数を自作するしかないです。このとき、const char* にして標準の std::hash<T*> を使ってはいけません。std::hash<T*> はポインタのアドレス値だけからハッシュを計算するので、違うアドレスに置かれた同一の文字列が別のハッシュ値になります。

都合の良いことに Stack overflow でほぼ同じ話題があり、そこで Fowler–Noll–Vo hash function が推奨されています。Wikipesia にも The FNV hash was designed for fast hash table and checksum use, not cryptography. と書かれているのでちょうどいいですね。これを使うことにします。

FNV1a-hash版

#if SIZE_MAX == UINT32_MAX
constexpr std::size_t FNV_PRIME = 16777619u;
constexpr std::size_t FNV_OFFSET_BASIS = 2166136261u;
#elif SIZE_MAX == UINT64_MAX
constexpr std::size_t FNV_PRIME = 1099511628211u;
constexpr std::size_t FNV_OFFSET_BASIS = 14695981039346656037u;
#else
#error "size_t must be greater than 32 bits."
#endif

template <>
struct std::hash<MyString>
{
    std::size_t operator()(const MyString& k) const
    {
        std::size_t hash = FNV_OFFSET_BASIS;
        for(auto it = k.begin(); it != k.end(); it++) {
            hash ^= *it;
            hash *= FNV_PRIME;
        }
        return hash;
    }
};

これで unordered_map が使えるようになりました。

参考

Stack overflow のほぼ同じ話題
https://stackoverflow.com/questions/34597260/stdhash-value-on-char-value-and-not-on-memory-address

Wikipedia: Fowler–Noll–Vo hash function
https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Boost の Fowler–Noll–Vo hash function 実装
https://www.boost.org/doc/libs/1_46_1/libs/unordered/examples/fnv1.hpp