A structure that stores its fields by size

Question

I would like to know how can I do the following in C++:

Consider these classes :

C1 < C2 < C3 < ... < Cn, Ci < Cj means sizeof(Ci) < sizeof(Cj)

I want a structure that uses variadic templates as a sequence of Ci's,

OrderBySize<AnySequenceOfCis>, for example : OrderBySize<C1,C2,C3,...,Cn> or OrderBySize<C2,C1,C3,C4,...,Cn> ... all possible combinations

and gives the following structure as a result :

class result{
  Cn elem1;
  Cn-1 elem2;
  .
  .
  .
  C1 elemn;
}

I read this article, it shows how we can define a Tuple<typename ...T>, however, this is different, much more difficult to implement and very useful.

EDIT :

order_by_size<T1, ..., Tn> would contain a tuple of the ordered combination of T1, ..., Tn

However I don't want the user to know that I am ordering the fields, the user would use it like a tuple. And thus, in order to access the fields, the user will use :

template<typename... Tn> get<size_t>(const MyStructure<Tn ...>& m) to get the size_t'th element which is has an other index in the new tuple.

Answer 1

Basically this problem reduces to just sorting a list of types based on a given comparator. Once you have that, everything else follows. So this answer is just the sorting part. We'll start with a typelist:

template <typename...>
struct typelist {
    using type = typelist;
};

I'm going to assume a bunch of metafunctions which are very short (head, tail, concat, size). I will omit them for brevity.

So let's just jump into writing merge sort:

template <typename TL, typename Cmp = LessSize>
struct sort
{
    using left_right = typename split<TL, size<TL>::value/2>::type;
    using left = typename sort<head_t<left_right>, Cmp>::type;
    using right = typename sort<head_t<tail_t<left_right>>, Cmp>::type;

    using type = typename merge<left, right, Cmp>::type;
};

// base case for exactly 1 element
template <typename T, typename Cmp>
struct sort<typelist<T>, Cmp> {
    using type = typelist<T>;
};

// potentially add a base case for exactly 2 elements here?

The general structure here should look familiar. We split our typelist, TL, into two equal parts, sort both, and then merge. Of course, this is metaprogramming, so everything is unnecessarily complicated.

Let's start with split. split takes a typelist and a size, and returns a typelist of two typelists: the first having the given size, and the second being the remainder:

template <typename A, typename B, size_t N>
struct split_impl
    : std::conditional<
        size<A>::value < N,
        split_impl<concat_t<A, typelist<head_t<B>>>, tail_t<B>, N>,
        typelist<A, B>
        >::type
{ };

template <typename TL, size_t N>
struct split
    : split_impl<typelist<>, TL, N>
{ };

So that gives us left and right (at least once we apply head_t<> and head_t<tail_t<>>). All that's left is the merge step. I'm using the Boost MPL idea of what a metafunction class is, so LessSize is:

struct LessSize {
    template <typename A, typename B>
    using apply = std::integral_constant<bool, sizeof(A) < sizeof(B)>;
};

merge just has to walk both typelists and pick the smallest element based on the comparator between the two typelists. First, we'll start with all of our base cases:

template <typename L, typename R, typename Cmp>
struct merge;

// R empty
template <typename... T, typename Cmp>
struct merge<typelist<T...>, typelist<>, Cmp> {
    using type = typelist<T...>;
};

// L empty
template <typename... T, typename Cmp>
struct merge<typelist<>, typelist<T...>, Cmp> {
    using type = typelist<T...>;
};

And then the recursive step, which is somewhat ugly:

template <typename A, typename... As, typename B, typename... Bs, typename Cmp> 
struct merge<typelist<A, As...>, typelist<B, Bs...>, Cmp>
: std::conditional<
        Cmp::template apply<A, B>::value,
        concat_t<typelist<A>, typename merge<typelist<As...>, typelist<B, Bs...>, Cmp>::type>,
        concat_t<typelist<B>, typename merge<typelist<A, As...>, typelist<Bs...>, Cmp>::type>
        >::type
{ };

Basically, given two typelists, {A, As...} and {B, Bs...}, we select the smallest based on Cmp, and that's the side we're popping the element off of. If Cmp::apply<A,B>, then we're concatenating A with the result of merging {As...} with {B, Bs...}. And vice versa.

And that's all she wrote:

template <typename T>
struct TD;

int main()
{
    using T = sort<typelist<int, double, char, float>, LessSize>::type;
    TD<T> r;
}

main.cpp: In function 'int main()':
main.cpp:131:11: error: aggregate 'TD<typelist<char, float, int, double> > r' has incomplete type and cannot be defined
     TD<T> r;
           ^

Once you have the sorted types, making a tuple is straightforward:

template <template <typename...> class C>
struct meta_quote {
    template <typename... T>
    using apply = C<T...>;
};

template <typename F, typename TL>
struct meta_apply;

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

template <typename... T>
struct my_tuple
: meta_apply<meta_quote<std::tuple>,
             typename sort<typelist<T...>>::type
             >::type;
{ 
    using base_tuple = meta_apply<...>;
};

Now just add overloads for get<> on my_tuple<T...>:

template <size_t I, typename... T>
auto get(my_tuple<T...>& t) {
    using type = std::tuple_element_t<I, std::tuple<T...>>;
    return std::get<type>(static_cast<typename my_tuple<T...>::base_type&>(t));
}

Answer 2

This is probably not the most efficient implementation (it uses cyclic permutation of types to determine the one with the largest size), and may contain errors, but the whole idea should be clear. The result is std::tuple with types ordered by descending size. The main function checks if it actually works (and it works on my gcc-4.8.2).

#include <iostream>
#include <tuple>
#include <iomanip>

constexpr std::size_t max (std::size_t x, std::size_t y)
{
   return (x < y) ? y : x;
}

template <typename ... Ts>
struct max_size;

template < >
struct max_size < >
{
       static constexpr std::size_t result = 0;
};

template <typename T, typename ... Ts>
struct max_size <T, Ts...>
{
       static constexpr std::size_t result = max(sizeof(T), max_size<Ts...>::result);
};

template <typename R, typename ... Ts>
struct order_by_size_impl;

template <bool M, typename R, typename ... Ts>
struct order_by_size_helper;

template <typename ... Rs, typename T, typename ... Ts>
struct order_by_size_helper<true, std::tuple<Rs...>, T, Ts...>
    : order_by_size_impl<std::tuple<Rs..., T>, Ts...>
{ };

template <typename ... Rs, typename T, typename ... Ts>
struct order_by_size_helper<false, std::tuple<Rs...>, T, Ts...>
    : order_by_size_impl<std::tuple<Rs...>, Ts..., T>
{ };

template <typename ... Rs, typename T, typename ... Ts>
struct order_by_size_impl<std::tuple<Rs...>, T, Ts...>
    : order_by_size_helper<sizeof(T) >= max_size<Ts...>::result, std::tuple<Rs...>, T, Ts...>
{ };

template <typename ... Rs>
struct order_by_size_impl<std::tuple<Rs...>>
{
       typedef std::tuple<Rs...> result;
};

template <typename ... Ts>
struct order_by_size
    : order_by_size_impl<std::tuple<>, Ts...>
{ };

struct test
{
   std::uint8_t data[128];
};

template <std::size_t I, typename T, typename R>
bool check (R const & r)
{
   return std::is_same<typename std::remove_cv<typename std::remove_reference<decltype(std::get<I>(r))>::type>::type, T>::value;
}

int main ( )
{
   order_by_size<std::uint8_t, std::uint32_t, std::uint16_t, std::uint64_t, test>::result r;
   std::cout << std::boolalpha;
   std::cout << check<0, test>(r) << std::endl;
   std::cout << check<1, std::uint64_t>(r) << std::endl;
   std::cout << check<2, std::uint32_t>(r) << std::endl;
   std::cout << check<3, std::uint16_t>(r) << std::endl;
   std::cout << check<4, std::uint8_t>(r) << std::endl;
}