c++ - 为哈希函数定义 c++20 概念

Question

CppCoreGuidelines 声明应该为所有模板参数指定概念。 (请参阅: T.10: Specify concepts for all template arguments )作为定义概念的实践，我正在尝试使用为 Hash 函数和 Key 模板参数定义的概念构建一个哈希表。
我希望我的哈希表使用两个模板参数， HashFunc 和 Key 。 HashFunc 应该是一个函数对象， Key 应该是函数对象 HashFunc 的参数。
也就是说， HashFunc(Key) 应该返回一个可转换为 size_t 的类型。
在 cppreference 上，有一个定义概念 Hashable 的示例。我复制了下面的例子:

template<typename T>
concept Hashable = requires(T a) {
    { std::hash<T>{}(a) } -> std::convertible_to<std::size_t>;
};

这个 Hashable 概念对许多用途都有意义。在这些情况下， T 类型的对象上的哈希函数是 std::hash<T> 的特化。但是，出于我的目的，我不想假设 Hash 将是 std::hash<Key> 。我希望用户能够提供不同的哈希函数。
由于 HashFunc 和 Key 的关系如此紧密，我认为我无法为 HashFunc 和 Key 定义单独的概念。 对吗？ 所以我想定义一个概念 HashConcept 来同时处理 HashFunc 和 Key。
所以我定义了一个概念 Hash 来处理两者。我尽力定义这个概念，使其与 Hash here 的命名要求相匹配。那么目标是满足4个条件。在此列表下方，我将讨论尝试强制执行这些条件。

返回类型可转换为 std::size_t 。

散列函数显示相等性保持(h(k1) == h(k1) 在程序运行期间。参见 C++ Extensions for Ranges 部分 19.1.1)

如果 u 是左值 Key ，则 h(u) 不会修改 u 。

"h(a)==h(b) 的 a!=b 概率应该接近 1.0/std::numeric_limits<std::size_t>::max() 。"

此列表是否完整？
我不相信概念可以强制执行 (4)，而 (4) 只需要在评论/文档中指出。我相信这些概念可能能够强制执行 (2) 和 (3)，但我不确定如何执行。 C++ Extensions for Ranges 第 19.5 节定义了 Callable 和 RegularCallable 的概念，然后说“注意:Callable 和 RegularCallable 的区别
纯粹是语义。 — 尾注”，暗示 (2) 不能执行。剩下 (1) 和 (3)。
我定义了一个强制执行(1)的概念。

template<typename HashFunc, typename Key>
concept Hash = requires(HashFunc h, Key k) {
    { std::invoke(h, k) } -> std::convertible_to<std::size_t>;
};

这个概念正确吗？ (例如，我应该使用 requires 还是返回 bool ？)我的概念是否可以扩展以解决散列函数的其他要求，例如 (2)-(4)？
下面是一些使用该概念的示例代码。结果是将 3 打印到 std::cout 。

#include <functional>
#include <concepts>
#include <iostream>

template<typename HashFunc, typename Key>
concept HashConcept = requires(HashFunc h, Key k) {
    { std::invoke(h, k) } -> std::convertible_to<std::size_t>;
};


class HashFunc {
public:
    std::size_t operator()(int i) {
        return static_cast<size_t>(i);
    }
};

template<typename Hash, typename Key>
    requires HashConcept<Hash, Key>
size_t HashConceptUser(Hash h, Key k) {
    return h(k);
}

int main() {
    std::cout << HashConceptUser< HashFunc, int >(HashFunc{}, 3); 

}

Answer 1

Does this list appear complete?

该列表缺少可以说是散列函数最重要的一个标准:如果 a == b然后 h(a) == h(b) .
列表中的第 4 条标准是您想要的良好散列函数的标准，它本身有些不完整 - 您不仅希望碰撞的可能性很小，还希望随机分散。哈希函数 h(i) = i满足第 4 条标准，但不是一个好的哈希函数。另一方面， h(i) = 0是一个糟糕的散列函数，但应该被认为是有效的。

也就是说，C++ 语言概念不能强制执行任何这些事情——你不能强制哈希函数是相等的，你不能强制它不修改它的输入，你不能强制任何关于其结果分布的东西。这些就是我们所说的语义约束而不是句法约束(C++ 标准说，如果满足句法约束，则满足概念，如果满足句法和语义约束，则对概念进行建模)。语义约束是文档化的需求(在评论中，或者只是文档中)而不是编码的需求。
最好的语法就是验证散列函数是否可调用并为您提供一个整数:

template <typename F, typename T>
concept HashFor = std::regular_invocable<F, T>
               && std::convertible_to<std::invoke_result_t<F, T>, size_t>;

我正在使用 regular_invocable这里是因为 that concept添加您想要的语义约束:函数调用是相等的并且不会修改函数对象或其参数。你也可以这样写:

template <typename F, typename T>
concept HashFor = std::regular_invocable<F, T>
    && requires(F f, T t) {
        { std::invoke(f, t) } -> std::convertible_to<size_t>;
    };

但我会保留 regular_invocable部分。