A structure that stores its fields by size
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 need a structure that uses variational patterns as a sequence Ci
,
OrderBySize<AnySequenceOfCis>
for example: OrderBySize<C1,C2,C3,...,Cn>
or
OrderBySize<C2,C1,C3,C4,...,Cn>
... all possible combinations
and gives the following structure:
class result{
Cn elem1;
Cn-1 elem2;
.
.
.
C1 elemn;
}
I read in this article , it shows how we can define Tuple<typename ...T>
, however this is different, much more difficult to implement and very useful.
EDIT:
order_by_size<T1, ..., Tn>
will contain a tuple of ordered combinationT1, ..., Tn
However, I don't want the user to know that I am ordering the fields, the user will use it as a tuple. Thus, 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 that has a different index in the new one tuple
.
source to share
Basically, this problem boils down to simply sorting a list of types based on a given comparator. After that, everything will follow. So this answer is just sorting. Let's start with a list of types:
template <typename...>
struct typelist {
using type = typelist;
};
I'm going to take a bunch of metafunkov, which are very short ( head
, tail
, concat
, size
). I omit them for brevity.
So let's just move on to the merge sort entry:
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 overall structure should look familiar here. We split our list of types 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 list of types and a size and returns a list of types from two lists of types: the first is of the given size and the second is 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>
{ };
Thus, we get left
and right
(at least once we use head_t<>
and head_t<tail_t<>>
). There is only one step left merge
. I'm using Boost MPL's idea of what a metafunction class is, so LessSize
:
struct LessSize {
template <typename A, typename B>
using apply = std::integral_constant<bool, sizeof(A) < sizeof(B)>;
};
merge
you just have to go through both type lists and select the smallest item based on the comparator between the two type lists. 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 a 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 lists of types {A, As...}
and {B, Bs...}
, we choose the smallest value based on Cmp
and the side we exit from. If Cmp::apply<A,B>
, then we merge A
with the result of merging {As...}
with {B, Bs...}
. And vice versa.
And 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 sorted types, creating a tuple is simple:
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<>
in 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));
}
source to share
This is probably not the most efficient implementation (it uses circular type swapping to determine the one with the largest size) and may contain bugs, but the whole idea should be clear. Result std::tuple
with types in descending order of 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;
}
source to share