'Concatenating a sequence of std::arrays

Consider the following: (Wandbox)

#include <array>
#include <algorithm>
#include <iostream>

template<typename T, int N, int M>
auto concat(const std::array<T, N>& ar1, const std::array<T, M>& ar2)
{
    std::array<T, N+M> result;
    std::copy (ar1.cbegin(), ar1.cend(), result.begin());
    std::copy (ar2.cbegin(), ar2.cend(), result.begin() + N);
    return result;
}

int main()
{
    std::array<int, 3> ar1 = {1, 2, 3};
    std::array<int, 2> ar2 = {4, 5};
    auto result = concat<int, 3, 2>(ar1, ar2);
    for (auto& x : result)
        std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

Given a sequence of std::array<T, length1>, std::array<T, length2>, ..., std::array<T, lengthK>, how can I generalize the above code and write a function which concatenates the sequence into an std::array<T, sum(lengths)>?

It would be nice if there is a way to write a reusable function which reduces a similar sequence of template classes using a given binary operation, e.g., use concat in the example above, rather than writing a special method (which would have to be re-written each time the binary op changes).

(IIUC, the relevant Standard Library algorithms (accumulate, reduce) only work in case the class of the result of the binary operation is always the same.)

c++arrays c++11 templates

Solution 1:^[1]

Here is a simple C++17 solution via fold expressions:

#include <array>
#include <algorithm>

template <typename Type, std::size_t... sizes>
auto concatenate(const std::array<Type, sizes>&... arrays)
{
    std::array<Type, (sizes + ...)> result;
    std::size_t index{};

    ((std::copy_n(arrays.begin(), sizes, result.begin() + index), index += sizes), ...);

    return result;
}

Example of using:

const std::array<int, 3> array1 = {{1, 2, 3}};
const std::array<int, 2> array2 = {{4, 5}};
const std::array<int, 4> array3 = {{6, 7, 8, 9}};

const auto result = concatenate(array1, array2, array3);

Live demo

Solution 2:^[2]

Given a sequence of std::array<T, length1>, std::array<T, length2>, ..., std::array<T, lengthK>, how can I write a function which concatenates the sequence into an std::array<T, sum(lengths)>?

Here's a C++17 solution. It can very probably be shortened and improved, working on it.

template <std::size_t Last = 0, typename TF, typename TArray, typename... TRest>
constexpr auto with_acc_sizes(TF&& f, const TArray& array, const TRest&... rest)
{
    f(array, std::integral_constant<std::size_t, Last>{});

    if constexpr(sizeof...(TRest) != 0)
    {
        with_acc_sizes<Last + std::tuple_size_v<TArray>>(f, rest...); 
    }
}

template<typename T, std::size_t... Sizes>
constexpr auto concat(const std::array<T, Sizes>&... arrays)
{
    std::array<T, (Sizes + ...)> result{};

    with_acc_sizes([&](const auto& arr, auto offset)
    {
        std::copy(arr.begin(), arr.end(), result.begin() + offset);
    }, arrays...);

    return result;
}

Usage:

std::array<int, 3> ar1 = {1, 2, 3};
std::array<int, 2> ar2 = {4, 5};
std::array<int, 3> ar3 = {6, 7, 8};
auto result = concat(ar1, ar2, ar3);

live wandbox example

Works with both g++7 and clang++5.

Solution 3:^[3]

My first line of reasoning would be to consider converting the array to a tuple of references (a tie), manipulate with tuple_cat and then perform whatever operation is necessary to build the final array (i.e. either move or copy - depending on the arguments originally passed in):

#include <array>
#include <iostream>

namespace detail {
    template<class Array, std::size_t...Is>
    auto array_as_tie(Array &a, std::index_sequence<Is...>) {
        return std::tie(a[Is]...);
    };

    template<class T, class Tuple, std::size_t...Is>
    auto copy_to_array(Tuple &t, std::index_sequence<Is...>) {
        return std::array<T, sizeof...(Is)>
                {
                        std::get<Is>(t)...
                };
    };

    template<class T, class Tuple, std::size_t...Is>
    auto move_to_array(Tuple &t, std::index_sequence<Is...>) {
        return std::array<T, sizeof...(Is)>
                {
                        std::move(std::get<Is>(t))...
                };
    };
}

template<class T, std::size_t N>
auto array_as_tie(std::array<T, N> &a) {
    return detail::array_as_tie(a, std::make_index_sequence<N>());
};


// various overloads for different combinations of lvalues and rvalues - needs some work
// for instance, does not handle mixed lvalues and rvalues yet
template<class T, std::size_t N1, std::size_t N2>
auto array_cat(std::array<T, N1> &a1, std::array<T, N2> &a2) {
    auto tied = std::tuple_cat(array_as_tie(a1), array_as_tie(a2));
    return detail::copy_to_array<T>(tied, std::make_index_sequence<N1 + N2>());
};

template<class T, std::size_t N1, std::size_t N2>
auto array_cat(std::array<T, N1> &&a1, std::array<T, N2> &&a2) {
    auto tied = std::tuple_cat(array_as_tie(a1), array_as_tie(a2));
    return detail::move_to_array<T>(tied, std::make_index_sequence<N1 + N2>());
};

int main() {
    std::array<int, 3> ar1 = {1, 2, 3};
    std::array<int, 2> ar2 = {4, 5};

    auto result = array_cat(ar1, ar2);

    for (auto &x : result)
        std::cout << x << " ";
    std::cout << std::endl;

    // move-construction
    auto r2 = array_cat(std::array<std::string, 2> {"a", "b"},
                        std::array<std::string, 2>{"asdfghjk", "qwertyui"});

    std::cout << "string result:\n";
    for (auto &&x : r2)
        std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

expected results:

1 2 3 4 5 
string result:
a b asdfghjk qwertyui

Solution 4:^[4]

C++14.

template<std::size_t I>
using index_t=std::integral_constant<std::size_t, I>;
template<std::size_t I>
constexpr index_t<I> index{};

template<std::size_t...Is>
auto index_over(std::index_sequence<Is...>){
  return [](auto&&f)->decltype(auto){
    return decltype(f)(f)( index<Is>... );
  };
}
template<std::size_t N>
auto index_upto(index_t<N>={}){
  return index_over(std::make_index_sequence<N>{});
}

this lets us expand parameter packs inline.

template<std::size_t, class T>
using indexed_type=T;

template<class T>
std::decay_t<T> concat_arrays( T&& in ){ return std::forward<T>(in); }
template<class T, std::size_t N0, std::size_t N1 >
std::array<T, N0+N1>
concat_arrays( std::array<T,N0> arr0, std::array<T,N1> arr1 ){
  auto idx0 = index_upto<N0>();
  auto idx1 = index_upto<N1>();
  return idx0( [&](auto...I0s){
    return idx1( [&](auto...I1s)->std::array<T, N0+N1>{
      return {{
        arr0[I0s]...,
        arr1[I1s]...
      }}; 
    })
  });
}

which gets us to two. For N, the easy way is:

template<class T, std::size_t N0, std::size_t N1, std::size_t...Ns >
auto concat_arrays( std::array<T,N0> arr0, std::array<T,N1> arr1, std::array<T, Ns>... arrs ){
  return concat_arrays( std::move(arr0), concat_arrays( std::move(arr1), std::move(arrs)... ) );
}

but it should be possible without recursion.

Code not tested.

Solution 5:^[5]

C++17 solution that is constexpr and works correctly with moveably-only types.

template<class Array>
inline constexpr auto array_size = std::tuple_size_v<std::remove_reference_t<Array>>;

template<typename... Ts>
constexpr auto make_array(Ts&&... values)
{
    using T = std::common_type_t<Ts...>;
    return std::array<T, sizeof...(Ts)>{static_cast<T>(std::forward<Ts>(values))...};
}

namespace detail
{
template<typename Arr1, typename Arr2, std::size_t... is1, std::size_t... is2>
constexpr auto array_cat(Arr1&& arr1, Arr2&& arr2, std::index_sequence<is1...>, std::index_sequence<is2...>)
{
    return make_array(std::get<is1>(std::forward<Arr1>(arr1))...,
        std::get<is2>(std::forward<Arr2>(arr2))...);
}
}

template<typename Arr, typename... Arrs>
constexpr auto array_cat(Arr&& arr, Arrs&&... arrs)
{
    if constexpr (sizeof...(Arrs) == 0)
        return std::forward<Arr>(arr);
    else if constexpr (sizeof...(Arrs) == 1)
        return detail::array_cat(std::forward<Arr>(arr), std::forward<Arrs>(arrs)...,
            std::make_index_sequence<array_size<Arr>>{},
            std::make_index_sequence<array_size<Arrs...>>{});
    else
        return array_cat(std::forward<Arr>(arr), array_cat(std::forward<Arrs>(arrs)...));
}

Solution 6:^[6]

A more concise evolution of @Constructor's C++17 solution with the added benefit that Type is not required to be default constructible

template <typename Type, std::size_t... sizes>
constexpr auto concatenate(const std::array<Type, sizes>&... arrays)
{
    return std::apply(
        [] (auto... elems) -> std::array<Type, (sizes + ...)> { return {{ elems... }}; },
        std::tuple_cat(std::tuple_cat(arrays)...));
}

Solution 7:^[7]

Strictly C++11; not as readable as @Jarod42's, but potentially much more efficient with many arrays if the call-tree isn't fully flattened (in terms of inlining) since only one result object exists rather than multiple temporary, progressively-growing result objects:

namespace detail {
    template<std::size_t...>
    struct sum_sizes_;

    template<std::size_t Acc>
    struct sum_sizes_<Acc> : std::integral_constant<std::size_t, Acc> { };

    template<std::size_t Acc, std::size_t N, std::size_t... Ns>
    struct sum_sizes_<Acc, N, Ns...> : sum_sizes_<Acc + N, Ns...> { };

    template<typename... As>
    using sum_sizes_t = typename sum_sizes_<
        0, std::tuple_size<typename std::decay<As>::type>{}...
    >::type;

    template<std::size_t O, typename A, typename R>
    void transfer(R& ret, typename std::remove_reference<A>::type const& a) {
        std::copy(a.begin(), a.end(), ret.begin() + O);
    }

    template<std::size_t O, typename A, typename R>
    void transfer(R& ret, typename std::remove_reference<A>::type&& a) {
        std::move(a.begin(), a.end(), ret.begin() + O);
    }

    template<std::size_t, typename R>
    void concat(R const&) { }

    template<std::size_t O, typename R, typename A, typename... As>
    void concat(R& ret, A&& a, As&&... as) {
        transfer<O, A>(ret, std::forward<A>(a));
        concat<(O + sum_sizes_t<A>{})>(ret, std::forward<As>(as)...);
    }
}

template<typename... As, typename std::enable_if<(sizeof...(As) >= 2), int>::type = 0>
auto concat(As&&... as)
-> std::array<
    typename std::common_type<typename std::decay<As>::type::value_type...>::type,
    detail::sum_sizes_t<As...>{}
> {
    decltype(concat(std::forward<As>(as)...)) ret;
    detail::concat<0>(ret, std::forward<As>(as)...);
    return ret;
}

Online Demo

Note that this also forwards properly by using the std::move algorithm for rvalues rather than std::copy.

Solution 8:^[8]

This doesn't generalize, but takes advantage of the fact that if we splat two arrays inside a set of braces, we can use that to initialize a new array.

I'm not sure how useful generalizing is, in any case. Given a bunch of arrays of mismatched sizes, just what else is there to do with them but join them all together?

#include <array>
#include <iostream>
#include <utility>

template<typename T, std::size_t L, std::size_t... Ls,
                     std::size_t R, std::size_t... Rs>
constexpr std::array<T, L + R> concat_aux(const std::array<T, L>& l, std::index_sequence<Ls...>,
                                          const std::array<T, R>& r, std::index_sequence<Rs...>) {
    return std::array<T, L + R> { std::get<Ls>(l)..., std::get<Rs>(r)... };
}

template<typename T, std::size_t L, std::size_t R>
constexpr std::array<T, L + R> concat(const std::array<T, L>& l, const std::array<T, R>& r) {
    return concat_aux(l, std::make_index_sequence<L>{},
                      r, std::make_index_sequence<R>{});
}

template<typename T, std::size_t L, std::size_t R, std::size_t... Sizes>
constexpr auto concat(const std::array<T, L>& l,
                      const std::array<T, R>& r,
                      const std::array<T, Sizes>&... arrays) {
    return concat(concat(l, r), arrays...);
}

int main() {
    std::array<int, 5> a1{1, 2, 3, 4, 5};
    std::array<int, 3> a2{6, 7, 8};
    std::array<int, 2> a3{9, 10};

    for (const auto& elem : concat(a1, a2, a3)) {
        std::cout << elem << " ";
    }
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1	Constructor
Solution 2
Solution 3	Richard Hodges
Solution 4	Yakk - Adam Nevraumont
Solution 5	Evg
Solution 6
Solution 7
Solution 8	DrPizza

'Concatenating a sequence of std::arrays

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]

Solution 7:[7]

Solution 8:[8]