0

我正在 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);

谁能在这里帮助我并指出我遗漏了什么或做错了什么？

4

1 回答 1

0

在此调用中，您提供std::hash<Key>with的构造函数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 &)>如果确实需要，用户仍然可以覆盖默认值并要求哈希函数为 a 。

如果要使用散列函数，我建议在Cache构造 a 时要求用户提供它。这样，您可以在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>or size_t(*)(const Key&)，并且当需要指向散列函数的指针时，您可以禁止构造Cache仅具有大小的 a ：

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没有哈希器的情况下构造 a ：

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
}
于 2022-01-03T15:44:54.813 回答