How can I arbitrarily sort a tuple's types?

Question

One thing that really annoys me about C++ is that an empty struct/class takes up space.

So, I have this idea that std::tuple (or some variant, since it's (and the compiler's) implementation is highly implementation dependent) might be able to save the day, which it sort of does, but there are issues due to packing and alignment. Because of how compilers will align the items in the struct, having a empty next to a non-empty next to an empty next to a non-empty will be larger than 2 empties next to 2 non-empties.

Because of this, I need a way to reorder the types based on some criteria. Sorting the entire list based on size isn't necessary (and may in some cases be detrimental) so I need some generic way to reorder the tuple's type list but still access it as if the type list was in the original order.

I looked around a bit and haven't found anything like this and I'm at a loss. Ideas on how to accomplish this?

Example

struct A{};
struct B{};
 // Need to be reordered based on some criteria.
std::tuple<A, int, B, float> x;
// In this case move all of the empty objects together like:
//   std::tuple<A, B, int, float> x;
// but still have get<1>(x) return the `int` and get<2>(x) return `B`.
static_assert(std::is_same<decltype(get<0>()), A>::value,     "0 should be type A");
static_assert(std::is_same<decltype(get<1>()), int>::value,   "1 should be type int");
static_assert(std::is_same<decltype(get<2>()), B>::value,     "2 should be type float");
static_assert(std::is_same<decltype(get<3>()), float>::value, "3 should be type B");

The reason this cannot be done by hand is that this could be part of a template and the elements in tuple may be empty or not, based on the parameters:

template <typename A, typename B, typename C, typename D>
class X
{
    // Need to have this auto arranged given some criteria
    // like size or move all of the empties together.
    tuple<A, B, C, D> x;
  public:
    template<int i>
    auto get() -> typename std::tuple_element<i, decltype(x)>
    {
      return get<i>(x);
    }
};
// What are these types?  Who knows.  This could be buried in some
// template library somewhere.
X<T1, T2, T3, T4> x;

Answer 1

Building on what Barry did.

So from here I'd need a mapping meta-function to use the original indices, how would I do that?

First, some helpers to facilitate index mapping. And because I'm lazy, I modified typelist slightly.

template <typename... Args>
struct typelist { 
    static constexpr std::size_t size = sizeof...(Args);
};

template<class T, std::size_t OldIndex, std::size_t NewIndex>
struct index_map_leaf {
    using type = T;
    static constexpr std::size_t old_index = OldIndex;
    static constexpr std::size_t new_index = NewIndex;
};

template<class... Leaves>
struct index_map : Leaves... {};

Given a properly built index_map, converting from old index to new index is simple, leveraging template argument deduction and overload resolution:

template<std::size_t OldIndex, std::size_t NewIndex, class T>
index_map_leaf<T, OldIndex, NewIndex> 
    do_convert_index(index_map_leaf<T, OldIndex, NewIndex>);

template<std::size_t OldIndex, class IndexMap>
using converted_index_t = decltype(do_convert_index<OldIndex>(IndexMap()));

converted_index_t<OldIndex, IndexMap>::new_index is, well, the new index.

To build the index map, we do it in in three steps. We start by transforming the types into type-index pairs.

template<class... Ts, std::size_t... Is>
typelist<index_map_leaf<Ts, Is, 0>...>
    do_build_old_indices(typelist<Ts...>, std::index_sequence<Is...>);

template<class TL>
using build_old_indices =
    decltype(do_build_old_indices(TL(),  std::make_index_sequence<TL::size>()));

Next, we partition the pairs. We need a metafunction that applies another metafunction to its arguments' nested typedef type rather than the arguments themselves.

// Given a metafunction, returns a metafunction that applies the metafunction to
// its arguments' nested typedef type.
template<class F>
struct project_type {
    template<class... Args>
    using apply = typename F::template apply<typename Args::type...>;
};

Given this, partitioning a typelist of index_map_leafs is simply partition_t<LeafList, project_type<F>>.

Finally, we transform the partitioned list, adding the new indices.

template<class... Ts, std::size_t... Is, std::size_t...Js>
typelist<index_map_leaf<Ts, Is, Js>...> 
    do_build_new_indices(typelist<index_map_leaf<Ts, Is, 0>...>,
                         std::index_sequence<Js...>);

template<class TL>
using build_new_indices =
   decltype(do_build_new_indices(TL(), std::make_index_sequence<TL::size>()));

Bringing it all together,

template<class TL, class F>
using make_index_map = 
    apply_t<quote<index_map>, build_new_indices<partition_t<build_old_indices<TL>, 
                                                            project_type<F>>>>;

---

With a little utility to convert the arguments of an arbitrary template to a type list:

template<template<class...> class T, class... Args>
typelist<Args...> do_as_typelist(typelist<T<Args...>>);

template<class T>
using as_typelist = decltype(do_as_typelist(typelist<T>()));

We can do the partitioning only once, by constructing the reordered tuple type directly from the index_map.

template<class Tuple, class F>
struct tuple_partitioner {
    using map_type = make_index_map<as_typelist<Tuple>, F>;
    using reordered_tuple_type = apply_t<project_type<quote<std::tuple>>,
                                         as_typelist<map_type>>;
    template<std::size_t OldIndex>
    using new_index_for = 
        std::integral_constant<std::size_t,
                               converted_index_t<OldIndex, map_type>::new_index>;
};

For example, given

using original_tuple = std::tuple<int, double, long, float, short>;
using f = quote<std::is_integral>;
using partitioner = tuple_partitioner<original_tuple, f>;

The following assertions hold:

static_assert(partitioner::new_index_for<0>() == 0, "!");
static_assert(partitioner::new_index_for<1>() == 3, "!");
static_assert(partitioner::new_index_for<2>() == 1, "!");
static_assert(partitioner::new_index_for<3>() == 4, "!");
static_assert(partitioner::new_index_for<4>() == 2, "!");
static_assert(std::is_same<partitioner::reordered_tuple_type,
                           std::tuple<int, long, short, double, float>>{}, "!");

Demo.

---

P.S. Here's my version of filter:

template<typename A, typename F>
using filter_one = std::conditional_t<F::template apply<A>::value,
                                      typelist<A>, typelist<>>;

template<typename F, typename... Args>
concat_t<filter_one<Args, F>...> do_filter(typelist<Args...>);

template <typename TL, typename F>
using filter_t = decltype(do_filter<F>(TL()));

Answer 2

First, let's start with the basics. We need a way to turn a template template (std::tuple) into a metafunction class:

template <template <typename...> class Cls>
struct quote {
    template <typename... Args>
    using apply = Cls<Args...>;
};

And a typelist:

template <typename... Args>
struct typelist { };

And something to go between them:

template <typename F, typename TL>
struct apply;

template <typename F, typename... Args>
struct apply<F, typelist<Args...>> {
    using type = typename F::template apply<Args...>;
};

template <typename F, typename TL>
using apply_t = typename apply<F, TL>::type;

So that given some typelist, we can just have:

using my_tuple = apply_t<quote<std::tuple>, some_typelist>;

Now, we just need a partitioner on some criteria:

template <typename TL, typename F>
struct partition {
    using type = concat_t<filter_t<TL, F>,
                          filter_t<TL, not_t<F>>
                          >;
};

Where concat:

template <typename... Args>
struct concat;

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

template <typename... A1, typename... A2, typename... Args>
struct concat<typelist<A1...>, typelist<A2...>, Args...> {
    using type = concat_t<typelist<A1..., A2...>, Args...>;
};

template <typename TL>
struct concat<TL> {
    using type = TL;
};

filter:

template <typename TL, typename F>
struct filter;

template <typename TL, typename F>
using filter_t = typename filter<TL, F>::type;

template <typename F>
struct filter<typelist<>, F> {
    using type = typelist<>;
};

template <typename A, typename... Args, typename F>
struct filter<typelist<A, Args...>, F> {
    using type = concat_t<
                     std::conditional_t<F::template apply<A>::value,
                                        typelist<A>,
                                        typelist<>>,
                     filter_t<typelist<Args...>, F>
                     >;
};

And not_:

template <typename F>
struct not_ {
    template <typename Arg>
    using apply = std::conditional_t<F::template apply<Args>::value,
                                     std::false_type,
                                     std::true_type>;
};

Which, given some_typelist of types that you want to put in your tuple becomes:

using my_tuple = apply_t<
    quote<std::tuple>, 
    partition_t<
        some_typelist,
        some_criteria_metafunc_class
    >>;