Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

問題

カスタムアロケータで特殊化した文字列型を使っていると、そのままでは 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

nakat-t
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした