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).

Matrass

First you have define way of sorting. How template decide that A must be before B. – Windbound

Interesting question. You could sort them by the types size, but you need something more for types with same size. – Booze

Does it need to literally be the same type, or would it be sufficient to statically know whether two sets of types were the same? – Scabies

please clarify: Are you looking for a predicate that you can use to sort them, or do you need a way to sort them given some prediacte, or both? – Booze

I can see a way of doing this, but only if rather than the classes "all inherit from the same base class", each class can define a unique constexpr identifier, of some sort. Definitely doable, but somewhat long-winded. – Liles

You'll probably need to use std::type_info and std::type_index. std::type_index has constexpr operator< for sorting types. – Skylab

@idclev463035818 I would say: either. If I can find a constexpr predicate I think I would manage to sort them. But I left the question more opened as maybe I'm missing a point and there might be a way to achieve what I'm after without sorting? – Matrass

@MarekR Yes. It doesn't have to be always A before B, as long as it is consistent across a compilation. – Matrass

@Scabies I guess that knowing they are the same would be ok, I could potentially allow the conversion, then. – Matrass

@Matrass you missed the point. I mean how do you express desired order? Note one answer suggest alphabetical order and sorting, my manually defined custom order and compilation error if user of template do not use desired order. Now depending on what exactly you want to achieve one of this answer is good or combination of both or some other alternative. – Windbound

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.

Cushy

This is very impressive. I tried to do something similar and gave up with the sorting. I was thinking of providing an explicit ordering instead of a comparison function, so that the interface could be a bit nicer and this could be a library: Order<A,B,C>::sort<C,B,A>::type; or template<class...Ts> using sorted=typename Order<A,B,C>::sort<Ts...>; MyContainer<sorted<B,C,A>> c. – Virilism

Indeed impressive how readable this is, though templates are still able to confuse code highlighting :). – Booze

Answer 2

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.

Inamorato

can you explain a bit how this is used to sort the parameters, or cause MyContainer<A,B,C> to be the same type as MyContainer<B,A,C>? I don't dont understand what this does – Booze

So long as there are no duplicates it produces an options pack with the same values regardless of the order the options are presented in. This method is really meant for cases where your arguments are meant to fill out a policy type. – Inamorato

Is there a typo after struct do_pack_options;? Don't think it'll compile. – Doralynn

Answer 3

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

Windbound