如何将引用类型传递给std：：散列

Question

我正在C++-11中创建一个模板缓存库，在这里我想散列键。我想对原始/预定义的类型(如std::hash )使用默认的int, std::string, etc.，对于用户定义的类型使用用户定义的哈希函数。我的代码当前如下所示：

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

在这个调用中，您使用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) {

最好为所需的类型的hasher添加一个模板参数。对于具有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;
};

其用法将与以前相同，除非您不能在没有hasher的情况下构造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
}