15
\$\begingroup\$

Given a typelist, return a typelist of all the permutations of it. For example:

using Types = typelist<char, int, double>;
using Permutations = typelist<
    typelist<char, int, double>,
    typelist<char, double, int>,
    typelist<int, char, double>,
    typelist<int, double, char>,
    typelist<double, char, int>,
    typelist<double, int, char>
    >;

static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

There are two different ways of writing metafunction "overloads": partial specialization or function overloading. I'm still unsure of which is "better", and in this solution I ended up using both, which strikes me as questionable.

The algorithm here is: the permutations of a list is the concatenation of (each element in the list prepended to all the permutations of the list with that element removed).

template <class...> struct typelist { };
template <class T> struct tag { using type=T; };

// remove first instance of type from a typelist
template <class T, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<T, Ts...>, typelist<Rs...>)
    -> tag<typelist<Rs..., Ts...>>;

template <class T, class F, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<F, Ts...>, typelist<Rs...>)
    -> decltype(remove_first(tag<T>{}, typelist<Ts...>{}, typelist<Rs..., F>{}));

template <class T, class TL>
using remove_first_t = typename decltype(remove_first(tag<T>{}, TL{}, typelist<>{}))::type;

// concatenate lots of typelists into one typelist
template <class TL>
auto concat(TL ) -> tag<TL>;

template <class... A, class... B, class... Cs>
auto concat(typelist<A...>, typelist<B...>, Cs... cs)
    -> decltype(concat(typelist<A..., B...>{}, cs...));

template <class... Ts>
using concat_t = typename decltype(concat(Ts{}...))::type;

// prepend a type onto a typelist of typelists
template <class T, class... TLs>
auto prepend(tag<T>, typelist<TLs...>)
    -> tag<typelist<concat_t<typelist<T>, TLs>...>>;

template <class T, class TL>
using prepend_t = typename decltype(prepend(tag<T>{}, TL{}))::type;

// get all the permutations of a typelist
template <class T, class=void>
struct permute : tag<typelist<T>> { };

template <class T>
using permute_t = typename permute<T>::type;

template <class... Ts>
struct permute<typelist<Ts...>, std::enable_if_t<(sizeof...(Ts)>1)>>
    : tag<
        concat_t<
            prepend_t<
                Ts,
                permute_t<remove_first_t<Ts, typelist<Ts...>>>
            >...
        >
    >
{ };
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Out of curiosity: what are the uses of doing this? \$\endgroup\$ Commented Nov 21, 2015 at 19:30
  • \$\begingroup\$ I don't have a compiler at hand, but I think you could also use a compile time "random number generator", and generate just one permutation of the typelist (unless you really want all permutations, I don't know). For this, I'd use the idea of Neves and Araujo, see Fig. 3 and the discussion after it. Is this helpful? \$\endgroup\$
    – Juho
    Commented Nov 26, 2015 at 12:59
  • \$\begingroup\$ @Quuxplusone Thanks! I have no idea how that happened, I thought I just copy/pasted the code in ::shrug:: \$\endgroup\$
    – Barry
    Commented Jan 5, 2016 at 18:31
  • \$\begingroup\$ Do you allow types in type-list to be non-unique? \$\endgroup\$
    – Jan Korous
    Commented Jun 10, 2016 at 20:48

1 Answer 1

3
\$\begingroup\$

You might have some bug in the algorithm.

"testdata"

struct A {};
struct B {};
struct C {};
struct D {};

using Types = typelist<A, B, C, D>;
using Permutations = typelist<
    typelist<A,B,C,D>,
    typelist<A,B,D,C>,
    typelist<A,C,B,D>,
    typelist<A,C,D,B>,
    typelist<A,D,B,C>,
    typelist<A,D,C,B>,
    typelist<B,A,D,C>,
    typelist<B,A,C,D>,
    typelist<B,C,D,A>,
    typelist<B,C,A,D>,
    typelist<B,D,C,A>,
    typelist<B,D,A,C>,
    typelist<C,A,B,D>,
    typelist<C,A,D,B>,
    typelist<C,B,A,D>,
    typelist<C,B,D,A>,
    typelist<C,D,A,B>,
    typelist<C,D,B,A>,
    typelist<D,A,C,B>,
    typelist<D,A,B,C>,
    typelist<D,B,C,A>,
    typelist<D,B,A,C>,
    typelist<D,C,B,A>,
    typelist<D,C,A,B>
>;
static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

results in:

prog.cpp:90:1: error: static assertion failed: !
 static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");
 ^
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.