Define tuple recursively

Question

I am using GCC8.2 and I would like to define a hierarchical tuple like this:

std::tuple<std::array<double,N>,
           std::array<double,N/2>,
           std::array<double,N/4>,
           ...,
           std::array<double,2> > v ;

And then I have an algorithm to fill those arrays with the following specification:

template <int N>
std::array<double,N> get_array()

How can I write a generic algorithm to declare the tuple and fill it at compile time for any N?

Answer 1

Are you sure that your sequence in

std::tuple<std::array<double,N>,
           std::array<double,N/2>,
           std::array<double,N/4>,
           ...,
           std::array<double,2> > v ;

ends with 2?

Supposing that you want to end with 2 or 1, I suppose you can use the following custom type traits to get the wanted index sequence

template <std::size_t N, std::size_t ... Is>
struct divSequence : public divSequence<(N>>1u), Is..., (N>>1u)>
 { };

template <std::size_t ... Is>
struct divSequence<2u, Is...> : public std::index_sequence<Is...>
 { };

template <std::size_t ... Is>
struct divSequence<1u, Is...> : public std::index_sequence<Is...>
 { };

So you only need the following make function (with helper)

template <std::size_t ... Is>
std::tuple<std::array<double, Is>...>
   getDivTupleHelper (std::index_sequence<Is...> const &)
 { return { get_array<Is>()... }; }

template <std::size_t N>
auto getDivTuple ()
 { return getDivTupleHelper(divSequence<N>{}); }

The following is a full compiling C++14 example

#include <array>
#include <tuple>
#include <utility>

template <std::size_t N>
std::array<double,N> get_array ()
 { return {{ }}; }

template <std::size_t N, std::size_t ... Is>
struct divSequence : public divSequence<(N>>1u), Is..., (N>>1u)>
 { };

template <std::size_t ... Is>
struct divSequence<2u, Is...> : public std::index_sequence<Is...>
 { };

template <std::size_t ... Is>
struct divSequence<1u, Is...> : public std::index_sequence<Is...>
 { };

template <std::size_t ... Is>
std::tuple<std::array<double, Is>...>
   getDivTupleHelper (std::index_sequence<Is...> const &)
 { return { get_array<Is>()... }; }

template <std::size_t N>
auto getDivTuple ()
 { return getDivTupleHelper(divSequence<N>{}); }


int main ()
 {
   using t0 = decltype( getDivTuple<15u>() );
   using t1 = std::tuple<std::array<double, 7u>,
                         std::array<double, 3u>,
                         std::array<double, 1u>>;
   using t2 = decltype( getDivTuple<16u>() );
   using t3 = std::tuple<std::array<double, 8u>,
                         std::array<double, 4u>,
                         std::array<double, 2u>>;

   static_assert( std::is_same<t0, t1>::value, "!");
   static_assert( std::is_same<t2, t3>::value, "!");
 }

If you need a C++11 solution... well... instead of std::index_sequence you can use a custom trivial substitute as

template <std::size_t ...>
struct myIndexSequence
 { }

and you need rewrite getDivTuple() to explicit the return type using decltype(); something as

template <std::size_t N>
decltype(getDivTupleHelper(divSequence<N>{})) getDivTuple ()
 { return getDivTupleHelper(divSequence<N>{}); }

Answer 2

Without recursion, you might do something like:

template <std::size_t N>
std::array<double, N> get_array() { return {{}}; }

namespace detail
{

    constexpr std::size_t log2(std::size_t n)
    {
        std::size_t res = 0;
        while (n != 0) {
            n /= 2;
            ++res;
        }
        return res;
    }

    template <std::size_t N, std::size_t ...Is>
    auto make_array_tuple_impl(std::index_sequence<Is...>)
    {
        return make_tuple(get_array<(N >> Is)>()...);
    }

}

template <std::size_t N>
auto make_array_tuple()
{
    return detail::make_array_tuple_impl<N>(std::make_index_sequence<detail::log2(N) - 1>());
}

Demo

Answer 3

This feels a bit involved, maybe there's a simpler solution.

// Pack of values
template <auto...>
struct vpack { };

// Concatenating two packs
template <class, class>
struct vpack_cat_;

template <auto... lhs, auto... rhs>
struct vpack_cat_<vpack<lhs...>, vpack<rhs...>> {
    using type = vpack<lhs..., rhs...>;
};

template <class Lhs, class Rhs>
using vpack_cat = typename vpack_cat_<Lhs, Rhs>::type;

// Building a decreasing exp scale...
template <int N>
struct exp_scale_ {
    using type = vpack_cat<
        vpack<N>,
        typename exp_scale_<N / 2>::type
    >;
};

// ... stopping at 2
template <>
struct exp_scale_<2> {
    using type = vpack<2>;
};

template <int N>
using exp_scale = typename exp_scale_<N>::type;

// Building the tuple's type from the scale
template <class ScalePack>
struct exp_tuple_;

template <auto... Scale>
struct exp_tuple_<vpack<Scale...>> {
    using type = std::tuple<std::array<double, Scale>...>;
};

template <class Scale>
using exp_tuple = typename exp_tuple_<Scale>::type;

// The known get_array() function
template <int N>
std::array<double,N> get_array() { return {}; }

// Initializing the tuple
template <auto... Scale>
auto get_tuple(vpack<Scale...>) {
    return exp_tuple<vpack<Scale...>>{
        get_array<Scale>()...
    };
}

template <int N>
auto get_tuple() {
    return get_tuple(exp_scale<N>{});
}

See it live on Coliru