man*_*ana 6 c++ hashtable c++-concepts c++20
CppCoreGuidelines 声明应为所有模板参数指定概念。（参见：T.10：指定所有模板参数的概念）作为定义概念的实践，我尝试使用为哈希函数和键模板参数定义的概念构建一个哈希表。
\n我希望我的哈希表使用两个模板参数，HashFunc并且Key. HashFunc应该是一个函数对象并且Key应该是该函数对象的参数HashFunc。
也就是说，HashFunc(Key)应该返回一个可转换为的类型size_t。
在cppreference上，有一个定义概念的示例Hashable。我复制了下面的例子：
template<typename T>\nconcept Hashable = requires(T a) {\n { std::hash<T>{}(a) } -> std::convertible_to<std::size_t>;\n};\n这个Hashable概念对于许多用途来说都是有意义的。在这些情况下，类型对象上的哈希函数T是特化的std::hash<T>。然而，就我的目的而言，我不想假设哈希将是std::hash<Key>. 我希望用户能够提供不同的哈希函数。
由于HashFunc和 的Key联系如此紧密，我认为我无法为HashFunc和定义单独的概念Key。那是对的吗？所以我想定义一个概念HashConcept来处理HashFunc和Key。
所以我定义了一个 Hash可以同时处理这两者的概念。我尽力定义这个概念，使其符合此处的命名Hash 要求。那么目标是满足 4 个条件。在此列表下方，我将讨论尝试执行这些条件。
std::size_t.u是左值Key，则不h(u)修改u。h(a)==h(b)“ for的概率a!=b应该接近1.0/std::numeric_limits<std::size_t>::max()。”这个列表看起来完整吗？
\n我不相信概念可以强制执行（4），并且（4）只需要在注释/文档中指出。我相信概念可能能够强制执行（2）和（3），但我不确定如何执行。C++ 范围扩展第 19.5 节定义了概念Callable和RegularCallable，然后说“注意：Callable 和 RegularCallable 之间的区别\nis 纯粹是语义的。\xe2\x80\x94 尾注”，表明不能强制执行 (2)。剩下 (1) 和 (3)。
我定义了一个强制执行（1）的概念。
\ntemplate<typename HashFunc, typename Key>\nconcept Hash = requires(HashFunc h, Key k) {\n { std::invoke(h, k) } -> std::convertible_to<std::size_t>;\n};\n这个概念正确吗？（例如，我应该使用requires或退回bool？）我的概念是否可以扩展到满足哈希函数的其他要求，例如（2）-（4）？
下面是一些使用该概念的示例代码。结果是打印3到std::cout.
#include <functional>\n#include <concepts>\n#include <iostream>\n\ntemplate<typename HashFunc, typename Key>\nconcept HashConcept = requires(HashFunc h, Key k) {\n { std::invoke(h, k) } -> std::convertible_to<std::size_t>;\n};\n\n\nclass HashFunc {\npublic:\n std::size_t operator()(int i) {\n return static_cast<size_t>(i);\n }\n};\n\ntemplate<typename Hash, typename Key>\n requires HashConcept<Hash, Key>\nsize_t HashConceptUser(Hash h, Key k) {\n return h(k);\n}\n\nint main() {\n std::cout << HashConceptUser< HashFunc, int >(HashFunc{}, 3); \n\n}\n这个列表看起来完整吗？
该列表可能缺少哈希函数最重要的一个标准： if a == bthen h(a) == h(b)。
列表中的第四个标准是您想要良好的散列函数的东西，它本身有些不完整 - 您不仅希望碰撞的可能性很小，还希望随机分散。该哈希函数h(i) = i满足第四个标准，但不是一个好的哈希函数。另一方面，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是因为这个概念添加了您想要的语义约束：函数调用是相等的，并且不会修改函数对象或其参数。你也可以这样写：
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部分。