Is there a way to consistently sort type template parameters?

Question

I have a class taking several template parameters :

template<typename... ELEMENTS>
class MyContainer;

By definition, MyContainer<A, B, C> is a different type than MyContainer<B, A, C>.

But in this case, I would like to avoid this: MyContainer<B, A, C> should be considered the same than MyContainer<A, B, C>.

So I thought that one way to "ignore" the order would be to standardize the order of the parameters. Have some template metaprogramming magic that would transform <B, A, C> or C, A, B> into <A, B, C>.

But I can't find any way to achieve this. Can you think of a clever trick to achieve that?

• The ELEMENTS passed as template parameters all inherit from the same base class, so I can add whatever static member I want there.
• But the codebase I'm working on doesn't have RTTI enabled, so I can't use typeid (although I think that it's not constexpr anyway).

Answer 1

As mentioned in the comments, to sort the types, you need a constexpr predicate. This could be manually assigning each type a static constexpr value which you can then compare. If that's not good enough, and you are using GCC, Clang or MSVC, you can use this to get a constexpr comparable value for a type.

Using that as a comparator, and a constexpr merge-sort, I was able to get this to work (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>>);

Note that MyContainer is an alias that sorts its parameters and instantiates MyActualContainer with the sorted parameters, rather than the container itself.