有没有一种方法可以一致地对类型模板参数进行排序？

Question

我有一个 class 有几个模板参数：

template<typename... ELEMENTS>
class MyContainer;

根据定义，MyContainer<A, B, C> 是不同于 MyContainer<B, A, C> 的类型。

但在这种情况下，我想避免这种情况：MyContainer<B, A, C> 应被视为与 MyContainer<A, B, C> 相同。

所以我认为“忽略”顺序的一种方法是标准化参数的顺序。有一些模板元编程魔法可以 将 <B, A, C> 或 C, A, B> 转换为 <A, B, C>.

但我找不到任何方法来实现这一目标。 你能想出一个巧妙的技巧来实现它吗？

作为模板参数传递的 ELEMENTS 都继承自相同的基础 class，所以我可以在那里添加我想要的任何静态成员。
但是我正在处理的代码库没有启用 RTTI，所以我不能使用 typeid（尽管我认为它不是 constexpr）。

Answer 1

如评论中所述，要对类型进行排序，您需要一个 constexpr 谓词。这可能是手动为每种类型分配一个 static constexpr 值，然后您可以比较该值。如果这还不够好，并且您使用的是 GCC、Clang 或 MSVC，则可以使用 this 获取类型的 constexpr 可比值。

使用它作为比较器和 constexpr 合并排序，我能够让它工作 (compiler explorer):

#include <type_traits>
#include <string_view>

template <typename T>
constexpr auto type_name() noexcept {
  std::string_view name = "Error: unsupported compiler", prefix, suffix;
#ifdef __clang__
  name = __PRETTY_FUNCTION__;
  prefix = "auto type_name() [T = ";
  suffix = "]";
#elif defined(__GNUC__)
  name = __PRETTY_FUNCTION__;
  prefix = "constexpr auto type_name() [with T = ";
  suffix = "]";
#elif defined(_MSC_VER)
  name = __FUNCSIG__;
  prefix = "auto __cdecl type_name<";
  suffix = ">(void) noexcept";
#else
  static_assert(false, "Unsupported compiler!");
#endif
  name.remove_prefix(prefix.size());
  name.remove_suffix(suffix.size());
  return name;
}

template <class... Ts>
struct list;

template <template <class...> class Ins, class...> struct instantiate;

template <template <class...> class Ins, class... Ts> 
struct instantiate<Ins, list<Ts...>> {
    using type = Ins<Ts...>;
};

template <template <class...> class Ins, class... Ts> 
using instantiate_t = typename instantiate<Ins, Ts...>::type;


template <class...> struct concat;

template <class... Ts, class... Us>
struct concat<list<Ts...>, list<Us...>>
{
    using type = list<Ts..., Us...>;
};

template <class... Ts>
using concat_t = typename concat<Ts...>::type;

template <int Count, class... Ts>
struct take;

template <int Count, class... Ts>
using take_t = typename take<Count, Ts...>::type;

template <class... Ts>
struct take<0, list<Ts...>> {
    using type = list<>;
    using rest = list<Ts...>;
};

template <class A, class... Ts>
struct take<1, list<A, Ts...>> {
    using type = list<A>;
    using rest = list<Ts...>;
};

template <int Count, class A, class... Ts>
struct take<Count, list<A, Ts...>> {
    using type = concat_t<list<A>, take_t<Count - 1, list<Ts...>>>;
    using rest = typename take<Count - 1, list<Ts...>>::rest;
};

template <class... Types>
struct sort_list;

template <class... Ts>
using sorted_list_t = typename sort_list<Ts...>::type;

template <class A>
struct sort_list<list<A>> {
    using type = list<A>;
};

template <class Left, class Right>
static constexpr bool less_than = type_name<Left>() < type_name<Right>();

template <class A, class B>
struct sort_list<list<A, B>> {
    using type = std::conditional_t<less_than<A, B>, list<A, B>, list<B, A>>;
};

template <class...>
struct merge;

template <class... Ts>
using merge_t = typename merge<Ts...>::type;

template <class... Bs>
struct merge<list<>, list<Bs...>> {
    using type = list<Bs...>;
};

template <class... As>
struct merge<list<As...>, list<>> {
    using type = list<As...>;
};

template <class AHead, class... As, class BHead, class... Bs>
struct merge<list<AHead, As...>, list<BHead, Bs...>> {
    using type = std::conditional_t<less_than<AHead, BHead>, 
        concat_t<list<AHead>, merge_t<list<As...>, list<BHead, Bs...>>>, 
        concat_t<list<BHead>, merge_t<list<AHead, As...>, list<Bs...>>>
    >;
};

template <class... Types>
struct sort_list<list<Types...>> {
    static constexpr auto first_size = sizeof...(Types) / 2;
    using split = take<first_size, list<Types...>>;
    using type = merge_t<
        sorted_list_t<typename split::type>, 
        sorted_list_t<typename split::rest>>;
};

template <class... Ts>
struct MyActualContainer {

};

template <class... Ts>
using MyContainer = instantiate_t<MyActualContainer, sorted_list_t<list<Ts...>>>;

struct a {
};
struct b {
};
struct c {
};

static_assert(std::is_same_v<
    MyContainer<a, b, c, c, c>, 
    MyContainer<c, b, c, a, c>>);

请注意，MyContainer 是一个别名，它对其参数进行排序并使用排序后的参数实例化 MyActualContainer，而不是容器本身。

Answer 2

我已经通过选项包完成了这个：

struct empty_option {};

template<bool FlagValue>
struct flag1
{
  template<typename Base>
  struct pack : Base
  {
    static constexpr bool const flag1 = FlagValue;
  };
};
template<bool FlagValue>
struct flag2
{
  template<typename Base>
  struct pack : Base
  {
    static constexpr bool const flag2 = FlagValue;
  };
};

template<typename ... Types>
struct pack_options;

typename<typename ... Types>
struct do_pack_options;
template<typename First, typename ... Types>
{
  using type = First::template pack<pack_options<Types...>;
};
template<typename First>
struct do_pack_options<First>
{
  using type = First::template pack<empty_option>;
}

template<typename ... Types>
struct pack_options
{
  using type = do_pack_options<Types...>::type;
};

using options = pack_options<Flag1<true>, Flag2<false>>;

请注意，boost 在中有一个用于执行此操作的类型，但我不关心它如何获取副本的最后一个实例而不是第一个实例。也就是说，如果您有： pack_options flag1 将为假。

Answer 3

C++17 可能的解决方案，其中所需的类型顺序表示为类型定义：

template <typename ...Args>
class TypeOrder
{
public:
    template<typename T>
    static constexpr bool has() noexcept {
        return (... || std::is_same_v<Args, T>);
    }

    template<typename T>
    static constexpr size_t index() noexcept {
        size_t i = 0;
        (... && (++i, !std::is_same_v<Args, T>));
        return i - 1;
    }

    template<typename A, typename B>
    static constexpr bool in_order() noexcept {
        return index<A>() < index<B>();
    }

    template<typename Front, typename ...Back>
    static constexpr bool all_in_order() noexcept {
        if constexpr (sizeof...(Back) == 0) {
            return true;
        } else {
            return (... && in_order<Front, Back>()) && all_in_order<Back...>();
        }
    }
};

这可以提供给 static_assert 因此，如果有人使用不正确的类型顺序或无效类型，则会引发编译错误。

Demo

有没有一种方法可以一致地对类型模板参数进行排序？

Is there a way to consistently sort type template parameters?

c++

templates

template-meta-programming