如何将引用类型传递给 std::hash

Question

我正在用 C++-11 创建一个模板缓存库，我想在其中散列键。我想对 int, std::string, etc. 等 primitive/pre-defined 类型使用默认 std::hash，对用户定义类型使用用户定义的哈希函数。我的代码目前看起来像这样：

template<typename Key, typename Value>
class Cache
{
    typedef std::function<size_t(const Key &)> HASHFUNCTION;
    private:
        std::list< Node<Key, Value>* > m_keys;
        std::unordered_map<size_t, typename std::list< Node<Key, Value>* >::iterator> m_cache;
        size_t m_Capacity;
        HASHFUNCTION t_hash;

        size_t getHash(const Key& key) {
            if(t_hash == nullptr) {
                return std::hash<Key>(key);  //Error line
            }
            else
                return t_hash(key);
        }

    public:
        Cache(size_t size) : m_Capacity(size) {
            t_hash = nullptr;
        }

        Cache(size_t size, HASHFUNCTION hash) : m_Capacity(size), t_hash(hash) {}        void insert(const Key& key, const Value& value) {
            size_t hash = getHash(key);
            ...
        }
        bool get(const Key& key, Value& val) {
            size_t hash = getHash(key);
            ...
        }
};

我的主要功能如下所示：

int main() {
    Cache<int, int> cache(3);
    cache.insert(1, 0);
    cache.insert(2, 0);
    int res;
    cache.get(2, &res);
}

编译上面的代码时，出现以下错误：

error: no matching function for call to ‘std::hash<int>::hash(const int&)’
             return std::hash<Key>(key);

谁能帮我指出我遗漏了什么或做错了什么？

Answer 1

在此调用中，您为 std::hash<Key> 的构造函数提供 key:

return std::hash<Key>(key);

您想使用它的成员函数，size_t operator()(const Key&) const;:

return std::hash<Key>{}(key);

一些注意事项：散列和缓存用于提供快速查找，为此使用 std::function 对象可能会减慢速度。它带有一些开销：

typedef std::function<size_t(const Key &)> HASHFUNCTION;

每次使用时都会在 getHash() 中进行检查：

if(t_hash == nullptr) {

为所需的哈希器类型添加一个模板参数可能会更好。对于具有 std::hash 特化的类型，这可能是默认值。否则 size_t(*)(const Key&) 可能是默认值。如果确实需要，用户仍然可以覆盖默认值并要求散列函数是 std::function<size_t(const Key &)>。

如果要使用哈希函数，我建议要求用户在构造 Cache 时提供它。这样你就可以在每次使用散列函数时跳过 if(t_hash == nullptr) 检查。

首先检查 std::hash<Key> 是否存在的小类型特征：

#include <functional>
#include <type_traits>
#include <utility>

template <class T>
struct has_std_hash {
    static std::false_type test(...); // all types for which the below test fails

    template <class U>
    static auto test(U u) -> decltype(std::declval<std::hash<U>>()(u),
                                      std::true_type{});

    static constexpr bool value = decltype(test(std::declval<T>()))::value;
};

Cache 中添加的模板参数然后可以有条件地默认为 std::hash<Key> 或 size_t(*)(const Key&) 并且您可以禁止构造只有一个大小的 Cache需要指向散列函数的指针：

template <
    typename Key, typename Value,
    class HASHFUNCTION = typename std::conditional<
        has_std_hash<Key>::value, std::hash<Key>, size_t(*)(const Key&)>::type>
class Cache {
public:
    // a bool that tells if HASHFUNCTION is a pointer type
    static constexpr bool hash_fptr = std::is_pointer<HASHFUNCTION>::value;

    Cache(size_t size) : m_Capacity(size) {
        static_assert(!hash_fptr, "must supply hash function pointer");
    }

    Cache(size_t size, HASHFUNCTION hash) : m_Capacity(size), t_hash(hash) {}

private:
    // No `if` is needed in getHash() - in fact, this function isn't needed.
    // You could just do `t_hash(key)` where you need it.
    size_t getHash(const Key& key) const { return t_hash(key); }

    HASHFUNCTION t_hash;
};

用法和以前一样，除了你不能在没有散列器的情况下构造一个Cache：

struct Foo {};

size_t hashit(const Foo&) { return 0; }

int main() {
    Cache<int, int> cache(3);          // ok, HASHFUNCTION is std::hash<int>
    Cache<Foo, int> c2(3, hashit);     // ok, HASHFUNCTION is size_t(*)(const Foo&)
    // Cache<Foo, int> c3(3);          // error: must supply hash function pointer
}

如何将引用类型传递给 std::hash

How to pass reference type to std::hash

c++

std

c++11

stdhash