Хеширование типов во время компиляции в C++17/C++2a

Question

Хеширование типов во время компиляции в C++17/C++2a

Рассмотрим следующий код:

#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 функция для возврата ключа хеша, уникального для типа, во время компиляции. Есть ли способ сделать это в C++17 или в C++2a (в идеале, полагаясь только на стандарт и не полагаясь на встроенные функции компилятора)?

10

c++ hash c++17 c++20 template-meta-programming

Источник

user882932 24 май '19 в 11:50

6 ответов

Решение

Я сомневаюсь, что это возможно с чисто стандартным C++.

Но есть решение, которое будет работать на большинстве основных компиляторов (по крайней мере, GCC, Clang и MSVC). Вы можете хешировать строки, возвращаемые следующей функцией:

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

9

Источник

user2752075 24 май '19 в 23:48

Основываясь на ответе HolyBlackCat, 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, что значения действительно вычисляются во время компиляции.

3

Источник

user499359 27 май '19 в 12:39

Я согласен с другими ответами о том, что это, как правило, пока невозможно, как указано в стандарте C++, но мы можем решить ограниченную версию проблемы.

Поскольку это все программирование во время компиляции, у нас не может быть изменяемого состояния, поэтому, если вы готовы использовать новую переменную для каждого изменения состояния, то возможно что-то вроде этого:

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

Где "hash_state" на самом деле просто уникальный список типов всех типов, которые мы хэшировали до сих пор. Это может также обеспечить size_t значение в результате хеширования нового типа. Если тип, который мы ищем, уже присутствует в списке типов, мы возвращаем индекс этого типа.

Это требует довольно много шаблонного:

Обеспечение уникальности типов в списке типов: я использовал ответ @Deduplicator здесь: /questions/48421138/kak-opredelit-variantx-y-z-izvlecheniya-podtipov-parametra-shablona/48421162#48421162
Поиск типа в уникальном списке типов
С помощью if constexpr проверить, есть ли тип в списке типов (C++ 17)

Live Demo

Часть 1: уникальный список типов:

Опять же, все заслуги перед ответом @Deduplicator здесь, в этой части. Следующий код сохраняет производительность во время компиляции, выполняя поиск по списку типов за O(log N), благодаря использованию tuple-cat.

Код написан почти досадно, но приятно то, что он позволяет работать с любым универсальным списком типов (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>{};
}

Первая перегрузка для общего случая; Вы уже "хэшировали" несколько типов, и вы хотите хэшировать еще один. Он проверяет, хеширован ли уже тип, который вы хэшируете, и, если это так, возвращает индекс типа в списке уникальных типов.

Чтобы добиться получения индекса типа в списке типов, я использовал простое расширение шаблона, чтобы сохранить некоторые экземпляры шаблона времени компиляции (избегая рекурсивного поиска):

// 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 для создания начального hash_token начинается с 0,

Заключение:

Не очень полезен во многих кодах, но это может помочь решить некоторые ограниченные проблемы метапрограммирования.

2

Источник

user27678 29 май '19 в 15:51

Я хотел бы улучшить ответ @max66 (кстати, он абсолютно блестящий и простой, мне жаль, что я не подумал об этом)

<TL;DR>

Помещатьinlineна статические переменные в ответе max66, и он будет следить за тем, чтобы одно и то же статическое значение присутствовало во всех единицах перевода.

</TL;DR>

Если у вас есть несколько единиц перевода, то, как правило, будет создано несколько экземпляров статической переменной (в случае max66), изменяя значение хэша, это может быть проблемой, скажем, у меня есть функцияgetHashкоторый я хочу использовать, чтобы проверить, совпадают ли два типа

      #include <iostream>
#include <type_traits>
#include <memory>

// <From max66's answer>


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;


// </From max66's answer>

struct AnyBase {
    using PointerType = std::unique_ptr<AnyBase>;
    constexpr virtual bool equal(const PointerType& other) const noexcept = 0;
    constexpr virtual const int* typeHash() const noexcept = 0;
};

template<typename ParameterType>
struct Any : public AnyBase
{
    using BasePointerType = std::unique_ptr<AnyBase>;
    using Type = ParameterType;
    Type value;
    constexpr Any(Type value) noexcept : value(value) {}
    constexpr virtual bool equal(const BasePointerType& other) const noexcept final
    {
        if(other->typeHash() == typeHash()) {
            const auto unwrapped = dynamic_cast<const Any<Type>*>(other.get()); 
            return unwrapped->value == value;
        }
        return false;
    }
    constexpr virtual const int* typeHash() const noexcept final {
        return type_hash_v<Type>;
    }

};

using AnyType = std::unique_ptr<AnyBase>;

template<typename ParameterType>
AnyType makeAny(auto... initializationValues) {
    return static_cast<AnyType>(std::make_unique<Any<ParameterType>>(initializationValues...));
}

int main()
{
    AnyType any0 = makeAny<int>(4);
    AnyType any1 = makeAny<int>(2);
    AnyType any2 = makeAny<int>(4);
    AnyType any3 = makeAny<char>('A');
    std::cout << "Hash Codes: " 
            << any0->typeHash() << "\n"
            << any1->typeHash() << "\n"
            << any2->typeHash() << "\n"
            << any3->typeHash() << "\n";
    std::cout 
            << "any0 == any1? " << any0->equal(any1) << "\n" // False within translation unit
            << "any0 == any2? " << any0->equal(any2) << "\n" // True within translation unit
            << "any0 == any3? " << any0->equal(any3) << "\n"; // False within translation unit
    return 0;
}

Если я создам два экземпляра в двух разных единицах перевода, они могут иметь два разных хэша, потому чтоiявляется статическим и, вероятно, имеет разные адреса в единицах перевода, поэтому, когда я пытаюсь сравнитьAny<int>произойдет сбой, даже если они имеют одинаковый тип и значение.

Из презентации Дейзи Холлман на CppNow (слайды здесь) я узнал, что стандарт C++ гарантирует одно постоянное создание экземпляра объекта в единицах перевода.

К сожалению, то, как она печатает регистрацию в начале презентации, не соответствует действительности.constexprв состоянии, потому что он опирается наstaticизменяемая переменная внутри функции. Однако, используя эти знания, мы можем настроить подход max66, давайте изменим исходный код.

      #include <iostream>
#include <type_traits>
#include <memory>
#include <bit>

template<typename ParameterType>
struct Registrar
{
    constexpr inline static const uintptr_t getHash() { // ACCORDING TOO C++ STANDARD INLINE GUARANTEES ONE COPY ACROSS ALL TRANSLATION UNITS
        return std::bit_cast<uintptr_t>(&hashObject);
    }
    protected: 
        constinit inline static const size_t hashObject = 0; // ACCORDING TOO C++ STANDARD INLINE GUARANTEES ONE COPY ACROSS ALL TRANSLATION UNITS
};




struct AnyBase {
    using PointerType = std::unique_ptr<AnyBase>;
    constexpr virtual bool equal(const PointerType& other) const noexcept = 0;
    constexpr virtual const uintptr_t typeHash() const noexcept = 0;
};

template<typename ParameterType>
struct Any : public AnyBase
{
    using BasePointerType = std::unique_ptr<AnyBase>;
    using Type = ParameterType;
    Type value;
    constexpr Any(Type value) noexcept : value(value) {}
    constexpr virtual bool equal(const BasePointerType& other) const noexcept final
    {
        if(other->typeHash() == typeHash()) {
            const auto unwrapped = dynamic_cast<const Any<Type>*>(other.get()); 
            return unwrapped->value == value;
        }
        return false;
    }
    constexpr virtual const uintptr_t typeHash() const noexcept final {
        return Registrar<Type>::getHash();
    }

};

using AnyType = std::unique_ptr<AnyBase>;

template<typename ParameterType>
AnyType makeAny(auto... initializationValues) {
    return static_cast<AnyType>(std::make_unique<Any<ParameterType>>(initializationValues...));
}

int main()
{
    AnyType any0 = makeAny<int>(4);
    AnyType any1 = makeAny<int>(2);
    AnyType any2 = makeAny<int>(4);
    AnyType any3 = makeAny<char>('A');
    std::cout << "Hash Codes: " 
            << any0->typeHash() << "\n"
            << any1->typeHash() << "\n"
            << any2->typeHash() << "\n"
            << any3->typeHash() << "\n";
    std::cout 
            << "any0 == any1? " << any0->equal(any1) << "\n" // False GUARANTEED across translation units
            << "any0 == any2? " << any0->equal(any2) << "\n" // True GUARANTEED across translation units
            << "any0 == any3? " << any0->equal(any3) << "\n"; // False GUARANTEED across translation units
    return 0;
}

Теперь наш хэш гарантирован во всех единицах перевода (как я уже сказал, все заглавными буквами :) )

Спасибо @max66 и Дейзи Холлман

И примечание, я думаю, вы могли бы далееstatic_castкsize_tили что-то, если вы хотите отuintptr_t, оба примера компилируются с помощью gcc 12.2 с-std=c++23

1

Источник

user1212887 23 окт '22 в 15:27

Я не думаю, что это возможно. "ключ хеша, уникальный для типа" звучит так, как будто вы ищете идеальный хеш (без коллизий). Даже если мы игнорируем, что size_t имеет конечное число возможных значений, в общем, мы не можем знать все типы из-за таких вещей, как разделяемые библиотеки.

Вы нуждаетесь в этом, чтобы сохраняться между пробегами? Если нет, вы можете настроить схему регистрации.

1

Источник

user1082038 24 май '19 в 23:42

Другие вопросы по тегам c++ hash c++17 c++20 template-meta-programming

user6022656 24 май '19 в 12:43 2019-05-24 12:43 · Accepted Answer · 2019-05-24 12:43

Я не знаю способ получить std::size_t для хэша.

Но если вы принимаете указатель на что-то, возможно, вы можете взять адрес статического члена в шаблонном классе.

Я имею в виду... что-то следующее

#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 как функция, я полагаю, вы могли бы просто создать функцию, которая возвращает type_hash_v<T> типа полученного.

Хеширование типов во время компиляции в C++17/C++2a

6 ответов

Live Demo

Часть 1: уникальный список типов:

Часть 2: наше "hash_state"

Часть 3: type_hash функция

Заключение:

Часть 3: `type_hash` функция