C++17/C++2a 编译时的哈希类型

Question

考虑以下代码：

#include <iostream>
#include <type_traits>

template <class T>
constexpr std::size_t type_hash(T) noexcept 
{
    // Compute a hash for the type
    // DO SOMETHING SMART HERE
}

int main(int argc, char* argv[])
{
    auto x = []{};
    auto y = []{};
    auto z = x;
    std::cout << std::is_same_v<decltype(x), decltype(y)> << std::endl; // 0
    std::cout << std::is_same_v<decltype(x), decltype(z)> << std::endl; // 1
    constexpr std::size_t xhash = type_hash(x);
    constexpr std::size_t yhash = type_hash(y);
    constexpr std::size_t zhash = type_hash(z);
    std::cout << (xhash == yhash) << std::endl; // should be 0
    std::cout << (yhash == zhash) << std::endl; // should be 1
    return 0;
}

我希望 type_hash 函数在编译时 return 该类型唯一的散列键。有没有办法在 C++17 或 C++2a 中做到这一点（理想情况下只依赖标准而不依赖编译器内在函数）？

Answer 1

我不知道如何获取哈希的 std::size_t。

但是如果你接受指向某物的指针，也许你可以在模板中获取静态成员的地址 class。

我的意思是...如下

#include <iostream>
#include <type_traits>

template <typename>
struct type_hash
 {
   static constexpr int          i     { };
   static constexpr int const *  value { &i };
 };

template <typename T>
static constexpr auto type_hash_v = type_hash<T>::value;


int main ()
 {
   auto x = []{};
   auto y = []{};
   auto z = x;
   std::cout << std::is_same_v<decltype(x), decltype(y)> << std::endl; // 0
   std::cout << std::is_same_v<decltype(x), decltype(z)> << std::endl; // 1
   constexpr auto xhash = type_hash_v<decltype(x)>;
   constexpr auto yhash = type_hash_v<decltype(y)>;
   constexpr auto zhash = type_hash_v<decltype(z)>;
   std::cout << (xhash == yhash) << std::endl; // should be 0
   std::cout << (xhash == zhash) << std::endl; // should be 1
 } // ...........^^^^^  xhash, not yhash

如果您真的想要 type_hash 作为一个函数，我想您可以简单地创建一个 return 接收到的 type_hash_v<T> 类型的函数。

Answer 2

我认为这是不可能的。 "hash key unique to the type" 听起来您正在寻找完美的散列（无冲突）。即使我们忽略 size_t 具有有限数量的可能值，通常我们也无法知道所有类型，因为共享库之类的东西。

你需要它在运行之间持续存在吗？如果没有，可以设置一个注册方案。

Answer 3

我怀疑纯粹使用标准 C++ 是否可行。

但是有一个解决方案适用于大多数主要编译器（至少是 GCC、Clang 和 MSVC）。您可以散列由以下函数返回的字符串：

template <typename T> constexpr const char *foo()
{
    #ifdef _MSC_VER
    return __FUNCSIG__;
    #else
    return __PRETTY_FUNCTION__;
    #endif
}

Answer 4

基于答案，一个 constexpr 模板变量，它是一种类型的散列的（天真的）实现：

template <typename T>
constexpr std::size_t Hash()
{
    std::size_t result{};

#ifdef _MSC_VER
#define F __FUNCSIG__
#else
#define F __PRETTY_FUNCTION__
#endif

    for (const auto &c : F)
        (result ^= c) <<= 1;

    return result;
}

template <typename T>
constexpr std::size_t constexpr_hash = Hash<T>();

可以如下图使用：

constexpr auto f = constexpr_hash<float>;
constexpr auto i = constexpr_hash<int>;

检查 godbolt 这些值确实是在编译时计算的。

Answer 5

我同意其他答案，即在标准 C++ 中通常 as-stated 尚不可能，但我们可以解决问题的受限版本。

因为这都是 compile-time 编程，我们不能有可变状态，所以如果你愿意为每个状态变化使用一个新变量，那么这样的事情是可能的：

hash_state1 = 散列(type1)
hash_state2 = hash(type2, hash_state1)
hash_state3 = hash(type3, hash_state2)

其中“hash_state”实际上只是我们迄今为止散列的所有类型的唯一类型列表。它还可以提供 size_t 值作为散列新类型的结果。如果我们寻求散列的类型已经存在于类型列表中，我们 return 该类型的索引。

这需要相当多的样板文件：

确保类型在类型列表中是唯一的：我在这里使用@Deduplicator 的回答：
在唯一类型列表中查找类型
使用 if constexpr 检查类型是否在类型列表中 (C++17)

Live Demo

第 1 部分：独特的类型列表：

同样，这部分的所有功劳都归功于。由于依靠 tuple-cat.

的实现，以下代码通过在 O(log N) 时间内查找类型列表来节省 compile-time 性能

代码的编写几乎令人沮丧，但它的优点是它允许您使用任何通用类型列表（tuple、variant、自定义的东西）。

namespace detail {
    template <template <class...> class TT, template <class...> class UU, class... Us>
    auto pack(UU<Us...>)
    -> std::tuple<TT<Us>...>;

    template <template <class...> class TT, class... Ts>
    auto unpack(std::tuple<TT<Ts>...>)
    -> TT<Ts...>;

    template <std::size_t N, class T>
    using TET = std::tuple_element_t<N, T>;

    template <std::size_t N, class T, std::size_t... Is>
    auto remove_duplicates_pack_first(T, std::index_sequence<Is...>)
    -> std::conditional_t<(... || (N > Is && std::is_same_v<TET<N, T>, TET<Is, T>>)), std::tuple<>, std::tuple<TET<N, T>>>;

    template <template <class...> class TT, class... Ts, std::size_t... Is>
    auto remove_duplicates(std::tuple<TT<Ts>...> t, std::index_sequence<Is...> is)
    -> decltype(std::tuple_cat(remove_duplicates_pack_first<Is>(t, is)...));

    template <template <class...> class TT, class... Ts>
    auto remove_duplicates(TT<Ts...> t)
    -> decltype(unpack<TT>(remove_duplicates<TT>(pack<TT>(t), std::make_index_sequence<sizeof...(Ts)>())));
}

template <class T>
using remove_duplicates_t = decltype(detail::remove_duplicates(std::declval<T>()));

接下来，我声明我自己的自定义类型列表以使用上述代码。大多数人以前见过的非常简单的空结构：

template<class...> struct typelist{};

第 2 部分：我们的“hash_state”

"hash_state"，我称之为 hash_token:

template<size_t N, class...Ts>
struct hash_token
{
    template<size_t M, class... Us>
    constexpr bool operator ==(const hash_token<M, Us...>&)const{return N == M;}
    constexpr size_t value() const{return N;}
};

简单地封装了一个size_t作为哈希值（你也可以通过value()函数访问）和一个比较器来检查两个hash_tokens是否相同（因为你可以有两个不同类型的列表，但散列值相同。例如，如果您对 int 进行散列以获取令牌，然后将该令牌与您散列的令牌进行比较（int、float、 char, int)).

第 3 部分：`type_hash` 函数

最后是我们的 type_hash 函数：

template<class T, size_t N, class... Ts>
constexpr auto type_hash(T, hash_token<N, Ts...>) noexcept
{
    if constexpr(std::is_same_v<remove_duplicates_t<typelist<Ts..., T>>, typelist<Ts...>>)
    {
        return hash_token<detail::index_of<T, Ts...>(), Ts...>{};
    }
    else
    {
        return hash_token<N+1, Ts..., T>{};
    }
}

template<class T>
constexpr auto type_hash(T) noexcept
{
    return hash_token<0, T>{};
}

第一个重载是针对一般情况；您已经“散列”了多种类型，并且还想散列另一种类型。它会检查您正在散列的类型是否已被散列，如果是，它 return 是唯一类型列表中该类型的索引。

为了在类型列表中获取类型的索引，我使用了简单的模板扩展来保存一些编译时模板实例化（避免递归查找）：

// find the first index of T in Ts (assuming T is in Ts)
template<class T, class... Ts>
constexpr size_t index_of()
{
    size_t index = 0;
    size_t toReturn = 0;
    using swallow = size_t[];
    (void)swallow{0, (void(std::is_same_v<T, Ts> ? toReturn = index : index), ++index)...};
    
    return toReturn;
}

type_hash 的第二个重载用于创建从 0 开始的初始 hash_token。

用法：

int main()
{
    auto x = []{};
    auto y = []{};
    auto z = x;
    std::cout << std::is_same_v<decltype(x), decltype(y)> << std::endl; // 0
    std::cout << std::is_same_v<decltype(x), decltype(z)> << std::endl; // 1
 
    constexpr auto xtoken = type_hash(x);
    constexpr auto xytoken = type_hash(y, xtoken);
    constexpr auto xyztoken = type_hash(z, xytoken);
    std::cout << (xtoken == xytoken) << std::endl; // 0
    std::cout << (xtoken == xyztoken) << std::endl; // 1
}

结论：

在很多代码中并不是很有用，但这可能有助于解决一些受限的 meta-programming 问题。

C++17/C++2a 编译时的哈希类型

Hashing types at compile-time in C++17/C++2a

c++

hash

template-meta-programming

c++17

c++20

Live Demo

第 1 部分：独特的类型列表：

第 2 部分：我们的“hash_state”

第 3 部分：`type_hash` 函数

用法：

结论：

C++17/C++2a 编译时的哈希类型

Hashing types at compile-time in C++17/C++2a

第 1 部分：独特的类型列表：

第 2 部分：我们的“hash_state”

第 3 部分：type_hash 函数

用法：

结论：

第 3 部分：`type_hash` 函数