How to pass reference type to std::hash

Question

I am creating a Template Cache library in C++-11 where I want to hash the keys. I want to use default std::hash for primitive/pre-defined types like int, std::string, etc. and user-defined hash functions for user-defined types. My code currently looks like this:

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);
            ...
        }
};

My main function looks like this:

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

On compiling the code above, I get the below error:

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

Can anyone please help me out here and point out what am I missing or doing it incorrectly?

Answer 1

In this call you provide the constructor of std::hash<Key> with key:

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

You want to use it's member function, size_t operator()(const Key&) const;:

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

---

Some notes: Hashing and caching are used to provide fast lookup and having a std::function object for this may slow it down a bit. It comes with some overhead:

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

The same goes for the check in getHash() that is done every time you use it:

if(t_hash == nullptr) {

It would probably be better to add a template parameter for what type of hasher that is needed. For types with std::hash specializations, that could be the default. Otherwise size_t(*)(const Key&) could be the default. A user could still override the default and demand that the hash function is a std::function<size_t(const Key &)> if that's really wanted.

If a hash function is to be used, I recommend requiring the user to supply it when a Cache is constructed. That way you can skip the if(t_hash == nullptr) check every time the hash function is used.

First a small type trait to check if std::hash<Key> exists:

#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;
};

The added template parameter in Cache could then be conditionally defaulted to either std::hash<Key> or size_t(*)(const Key&) and you could disallow constructing a Cache with only a size when a pointer to a hash function is needed:

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;
};

The usage would be the same as before, except you can't construct a Cache without a hasher:

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
}