Expand two parameter packs

Question

Consider following piece of code:

static constexpr size_t Num {2};
struct S {
    std::array<size_t, Num> get () { return {1, 2}; }
};

struct S1 : S {};
struct S2 : S {};

struct M {
    template <typename T>
    typename std::enable_if<std::is_same<T, S1>::value, S1>::type get () const { 
        return S1 {}; 
    }

    template <typename T>
    typename std::enable_if<std::is_same<T, S2>::value, S2>::type get () const { 
        return S2 {}; 
    }
};

I want to have a function which merges two or more std::arrays making one std::array.

So far I ended with something like this:

template <typename Mode, typename... Rs, size_t... Ns>
std::array<size_t, sizeof... (Rs)*Num> get_array (const Mode& mode, Sequence::Sequence<Ns...>) {
    return {std::get<Ns> (mode.template get<Rs...> ().get ())...};
}

I want to have that the following code

M m;
auto x = get_array<M, S1, S2> (m, Sequence::Make<2> {});

produces std::array<size_t, 4> filled with {1, 2, 1, 2}.

Where Sequence::Sequence and Sequence::Make are described here.

I know that placing ... of Rs is incorrect in this context (If sizeof... (Rs) is 1 then it is fine, std::array<size_t, 2> with {1, 2} is returned) but I have no idea where to put it to make expansion which looks like this:

std::get<0> (mode.template get<Rs[0]> ().get ()), 
std::get<1> (mode.template get<Rs[0]> ().get ()),
std::get<0> (mode.template get<Rs[1]> ().get ()), 
std::get<1> (mode.template get<Rs[1]> ().get ());

Of course Rs[0] I mean first type from parameter pack.

Is it even possible?

@AndyG unfortunately in the place where I need this I have only access to C++11 compiler, sad but true — Artur Pyszczuk, Sep 22 '17 at 16:15

score 4 · Answer 1 · edited Jun 20 '20 at 09:12

Assuming that we're using Xeo's index sequence implementation, we can do something like this:

First create a function for concatenating two arrays. It receives the arrays, plus an index sequence for each one (detail::seq is the index_sequence type)

template<class T, size_t N, size_t M, size_t... I, size_t... J>
std::array<T, N + M> concat(const std::array<T, N>& arr1, const std::array<T, M>& arr2, detail::seq<I...>, detail::seq<J...>)
{
     return {arr1[I]..., arr2[J]...};
}

Next, call this function from your get_array function, except we're going to double the seq that we received from the call in main:

template<class MODE, class... T, size_t... I>
auto get_array(MODE m, detail::seq<I...>) ->decltype(concat(m.template get<T>().get()..., detail::seq<I...>{}, detail::seq<I...>{})){
    return concat(m.template get<T>().get()..., detail::seq<I...>{}, detail::seq<I...>{});
}

The call in main looks just like it did in your code:

M m;
auto x = get_array<M, S1, S2>(m, detail::gen_seq<2>{});

Where detail::gen_seq is the implementation of make_index_sequence that Xeo had.

Live Demo

Note that I replaced unsigned with size_t in Xeo's index sequence impl.

In C++14 we don't need to implement seq or gen_seq, and we also wouldn't need a trailing -> decltype() after our function.

In C++17 it would be even easier to generalize our concatenation for an arbitrary number of arrays, using fold expressions.

I suspect the user was aware aware of this, but it involves default constructing and then copying, not so good for non trivial types and requires default constructible which shouldn't be necessary. — Nir Friedman, Sep 22 '17 at 15:40
@NirFriedman: I see... So I suppose we'll need something like [this](https://wandbox.org/permlink/EtaYvHVU6OpPjlQh), only we need to replicate index_sequence in C++11 like OP did — AndyG, Sep 22 '17 at 15:48
@NirFriedman: Oh, I see you beat me to it :-) Nice code. I'll upvote yours and delete mine. — AndyG, Sep 22 '17 at 16:00
Nah yours has some more relevant details, don't delete it! Leave both up :-). — Nir Friedman, Sep 22 '17 at 16:03
@AndyG Thanks, the solution works, but only for two arrays, right? I need also more arrays to be involved. — Artur Pyszczuk, Sep 24 '17 at 17:17

Nir Friedman · Answer 2 · 2017-09-22T16:05:40.620

Yes, this can be done, with the standard index_sequence tricks:

template <class T, std::size_t N1, std::size_t N2, std::size_t ... Is, std::size_t ... Js>
std::array<T, N1 + N2> merge_impl(const std::array<T, N1>& a1,
                                  const std::array<T, N2>& a2, 
                                  std::index_sequence<Is...>,
                                  std::index_sequence<Js...>) {
    return {a1[Is]..., a2[Js]...};
}

template <class T, std::size_t N1, std::size_t N2>
std::array<T, N1 + N2> merge(const std::array<T, N1>& a1, const std::array<T, N2>& a2) {
    return merge_impl(a1, a2,
                      std::make_index_sequence<N1>{}, 
                      std::make_index_sequence<N2>{});
}

index_sequence is only in the 14 standard, but can be easily implemented in 11; there are many resources (including on SO) that describe how to do so (edit: it's basically equivalent to your Sequence stuff, may as well get used to the standard names for them). Live example: http://coliru.stacked-crooked.com/a/54dce4a695357359.

Fine, but it is still for merging two arrays, what about merging arbitrary number of arrays? — Artur Pyszczuk, Sep 24 '17 at 17:29

score 2 · Accepted Answer · answered Sep 22 '17 at 20:40

To start with, this is basically asking to concatenate an arbitrary number of arrays. Which is very similar to concatenate an arbitrary number of tuples, for which there is a standard library function, even in C++11: std::tuple_cat(). That gets us almost there:

template <class... Ts, class M>
auto get_array(M m) -> decltype(std::tuple_cat(m.template get<Ts>()...)) {
    return std::tuple_cat(m.template get<Ts>()...);
}

Note that I flipped the template parameters, so this is just get_array<T1, T2>(m) instead of having to write get_array<M, T1, T2>(m).

Now the question is, how do we write array_cat? We'll just use tuple_cat and convert the resulting tuple to an array. Assume an implementation of index_sequence is available (which is something you'll want in your collection anyway):

template <class T, class... Ts, size_t... Is>
std::array<T, sizeof...(Ts)+1> to_array_impl(std::tuple<T, Ts...>&& tup,
                                             std::index_sequence<Is...> ) {
    return {{std::get<Is>(std::move(tup))...}};
}

template <class T, class... Ts>
std::array<T, sizeof...(Ts)+1> to_array(std::tuple<T, Ts...>&& tup) {
    return to_array_impl(std::move(tup), std::index_sequence_for<T, Ts...>());
}

template <class... Tuples>
auto array_cat(Tuples&&... tuples) -> decltype(to_array(std::tuple_cat(std::forward<Tuples>(tuples)...))) {
    return to_array(std::tuple_cat(std::forward<Tuples>(tuples)...));
}

And that gives you:

template <class... Ts, class M>
auto get_array(M m) -> decltype(array_cat(m.template get<Ts>()...)) {
    return array_cat(m.template get<Ts>()...);
}

which handles arbitrarily many types.

`tuple_cat` is allowed but not required to handle non-`std::tuple` tuple-like types, such as `std::array`. — T.C., Sep 24 '17 at 11:00
Thank you, even though other solutions were in my opinion easier than yours, this one works with arbitrary number of arrays, so that is what I wanted. — Artur Pyszczuk, Sep 24 '17 at 19:16
Barry, do you know if tuple_cat creates the new tuple purely in place? I.e. it does not create any intermediate tuples? If so, I need to see how it does it. I cannot think how I would pass a variadic number of integer sequence packs... — Nir Friedman, Sep 24 '17 at 20:19
@NirFriedman Have I got the blog post for you! http://ericniebler.com/2014/11/13/tiny-metaprogramming-library/ — Barry, Sep 24 '17 at 20:36

score 1 · Answer 4 · answered Sep 24 '17 at 22:00

So here's for an arbitrary number of same-type arrays. We are basically implementing a highly restrictive version of tuple_cat, made substantially easier because the number of elements in the arrays is the same. I make use of a couple C++14 and 17 library features that are all readily implementable in C++11.

template<class, size_t> struct div_sequence;
template<size_t...Is, size_t Divisor>
struct div_sequence<std::index_sequence<Is...>, Divisor>
{
   using quot = std::index_sequence<Is / Divisor...>;
   using rem = std::index_sequence<Is % Divisor...>;
};


template<class T, size_t...Ns, size_t...Is, class ToA>
std::array<T, sizeof...(Ns)> array_cat_impl(std::index_sequence<Ns...>,
                                            std::index_sequence<Is...>,
                                            ToA&& t) 
{
    // NB: get gives you perfect forwarding; [] doesn't.
    return {std::get<Is>(std::get<Ns>(std::forward<ToA>(t)))... }; 
}

template<class Array, class... Arrays,
         class VT = typename std::decay_t<Array>::value_type,
         size_t S = std::tuple_size<std::decay_t<Array>>::value,
         size_t N = S * (1 + sizeof...(Arrays))>
std::array<VT, N> array_cat(Array&& a1, Arrays&&... as) 
{
     static_assert(std::conjunction_v<std::is_same<std::decay_t<Array>,
                                                   std::decay_t<Arrays>>...
                                      >, "Array type mismatch");

     using ind_seq = typename div_sequence<std::make_index_sequence<N>, S>::rem;
     using arr_seq = typename div_sequence<std::make_index_sequence<N>, S>::quot;
     return array_cat_impl<VT>(arr_seq(), ind_seq(), 
                               std::forward_as_tuple(std::forward<Array>(a1),
                                                     std::forward<Arrays>(as)...)
                               );
}

We can also reuse the tuple_cat machinery, as in @Barry's answer. To sidestep potential QoI issues, avoid depending on extensions and also extra moves, we don't want to tuple_cat std::arrays directly. Instead, we transform the array into a tuple of references first.

template<class TupleLike, size_t... Is>
auto as_tuple_ref(TupleLike&& t, std::index_sequence<Is...>)
    -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<TupleLike>(t))...))
{
    return std::forward_as_tuple(std::get<Is>(std::forward<TupleLike>(t))...);
}

template<class TupleLike,
         size_t S = std::tuple_size<std::decay_t<TupleLike>>::value >
auto as_tuple_ref(TupleLike&& t)
    -> decltype(as_tuple_ref(std::forward<TupleLike>(t), std::make_index_sequence<S>()))
{
    return as_tuple_ref(std::forward<TupleLike>(t), std::make_index_sequence<S>());
}

We can then transform the tuple_cat'd references back into an array:

template <class R1, class...Rs, size_t... Is>
std::array<std::decay_t<R1>, sizeof...(Is)> 
   to_array(std::tuple<R1, Rs...> t, std::index_sequence<Is...>) 
{
   return { std::get<Is>(std::move(t))... };
}

template <class R1, class...Rs>
std::array<std::decay_t<R1>, sizeof...(Rs) + 1> to_array(std::tuple<R1, Rs...> t) 
{
   static_assert(std::conjunction_v<std::is_same<std::decay_t<R1>, std::decay_t<Rs>>...>,
                 "Array element type mismatch");
   return to_array(t, std::make_index_sequence<sizeof...(Rs) + 1>());
}

Finally, array_cat itself is just

template <class... Arrays>
auto array_cat(Arrays&&... arrays) 
    -> decltype(to_array(std::tuple_cat(as_tuple_ref(std::forward<Arrays>(arrays))...))) 
{
    return to_array(std::tuple_cat(as_tuple_ref(std::forward<Arrays>(arrays))...));
}

Any decent optimizer should have little difficulty optimizing the intermediate tuples of references away.

That's cool, I wish I would like to understand something from this :P. Anyway, maybe for some people who knows better all this template-magic poem, this will be helpful :) — Artur Pyszczuk, Sep 26 '17 at 18:47

Expand two parameter packs

4 Answers4

Live Demo