Is there a way to consistently sort type template parameters?

user_1898722 0
Viewed 180

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).
template-meta-programming templates c++
3 Answers

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.

user_7781170

I have accomplished this through option packs:

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>>;

Note that boost has a type for doing this in <boost/intrusive/pack_options.hpp> but I don't care for how it takes the last instance of a duplicate rather than the first. That is, if you have: pack_options<Flag1, Flag1> flag1 will be false.

user_75947110

C++17 possible solution, where desired order of types is expressed as type definition:

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...>();
        }
    }
};

this can be feed to static_assert so if someone uses incorrect order of types or invalid type, compilation error is raised.

Demo

user_13874380
Related