Parameter Pack Sorting (Or Equivalent Behavior)-CodePudding

I want:

template<class ... T>
auto foo()
{
  // ✨ magic ✨
}

Such that:

(foo<int, char, bool>() == foo<char, int, bool>()) // True
(foo<int>() == foo<char>()) // False

In other words, I want foo to return a unique id for the combination of types passed to it rather than the permutation of types passed to it.

My first idea was that there might be some way to sort the parameter pack at compile time, though I'm not sure how exactly that would work.

My current solution is this:

// Precondition: Client must pass the parameters in alphabetical order to ensure the same result each time
template<class ... T>
std::type_index foo()
{
  return std::make_type_index(typeid(std::tuple<T ... >));
}

The problem with this is that it doesn't work if the client is using type aliases. For example:

using my_type = char;
(foo<bool, int, my_type>() == foo<bool, char, int>()) // False

One idea I had is to assign a new prime number as an id for every new type that the function handles. Then I could assign a unique id for a particular combination of types by multiplying their prime number ids together. For example:

id of int = 2
id of bool = 3
id of char = 5
id of <int, bool, char> = 2 * 3 * 5 = 30
id of <bool, int, char> = 3 * 2 * 5 = 30

Only problem is how I'm going to assign unique prime number ids to each type without incurring a runtime penalty.

CodePudding user response：

Using Boost.Hana:

#include <boost/hana/set.hpp>
#include <boost/hana/type.hpp>

template<typename... T>
constexpr auto foo() {
    return boost::hana::make_set(boost::hana::type_c<T>...);
}

using my_type = char;
static_assert(foo<bool, int, my_type>() == foo<bool, char, int>());

CodePudding user response：

You can use the gcc extension __PRETTY_FUNCTION__ to get the name of each type and save them into std::array of std::string_view, then generate the unique combination of the current type list by sorting the array.

constexpr auto names = [] {
  std::array<std::string_view, sizeof...(Ts)> names{type_name<Ts>()...};
  std::ranges::sort(names);
  return names;
}();

But since std::arrays of different sizes cannot be compared, we can create a new type to save the string information of the flattened std::array, and overload operator== for it:

template<char...>
struct unique_id {};

template<char... As, char... Bs>
constexpr bool operator==(unique_id<As...>, unique_id<Bs...>) {
  if constexpr (sizeof...(As) == sizeof...(Bs))
    return ((As == Bs) && ...);
  else
    return false;
}

Next, just flatten the std::array and convert it to the new type we defined, then this type can be used as the unique id of the current type list:

constexpr auto flatten = [names] {
  constexpr auto size = std::accumulate(
    names.begin(), names.end(), 0, [](auto x, auto y) { return x   y.size(); });
  std::array<char, size> flatten{};
  std::ranges::copy(names | std::views::join, flatten.begin());
  return flatten;
}();

constexpr auto id = [flatten]<std::size_t... Is>(std::index_sequence<Is...>) {
  return unique_id<flatten[Is]...>{};
}(std::make_index_sequence<flatten.size()>{});

Demo.

CodePudding user response：

With Boost.Mp11:

template <typename T>
constexpr std::string_view type_name() {
    return __PRETTY_FUNCTION__; // close enough
}

template <typename T, typename U>
using type_less = mp_bool<type_name<T>() < type_name<U>()>;

template <typename... Ts>
constexpr auto foo() {
    return type_name<mp_sort<mp_list<Ts...>, type_less>>();
}

static_assert(foo<int, char>() == foo<char, int>());