Concatenating a sequence of std::arrays

Question

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.)

Caxton

We have std::tuple_cat. One option is simply writing the conversion from the resulting tuple to an array. – Ladylike

@Ladylike That's neat, didn't know that function. However as I wrote above it would be nice to have a solution which just applies any given templated binary operation to a sequence of objects of different classes (of course the operation should be associative and valid for applying on all the mid-results) – Caxton

Answer 1

You may do the following:

template <typename F, typename T, typename T2>
auto func(F f, T&& t, T2&& t2)
{
    return f(std::forward<T>(t), std::forward<T2>(t2));
}

template <typename F, typename T, typename T2, typename ... Ts>
auto func(F f, T&& t, T2&& t2, Ts&&...args)
{
    return func(f, f(std::forward<T>(t), std::forward<T2>(t2)), std::forward<Ts>(args)...);
}

With usage

struct concatenater
{
    template<typename T, std::size_t N, std::size_t M>
    auto operator()(const std::array<T, N>& ar1, const std::array<T, M>& ar2) const
    {
        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;
    }
};

and

auto result = func(concatenater{}, ar1, ar2, ar3, ar4);

C++14 Demo
C++11 Demo

Earleneearley

That's beautiful. – Caxton

I believe this is c++14, right? – Chirr

@Yakk-AdamNevraumont: indeed, missing trailing return type to be C++11. Demo added. – Earleneearley

@Earleneearley Hmm. For some reason I thought this was a constexpr question. Ignore me. – Chirr

std::copy is not constexpr until C++20... ;-) – Earleneearley

Answer 2

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

Columella

Beautiful! Any ideas for using a fold expression for a generic version (for an arbitrary binary op)? – Caxton

@Caxton Generic version wouldn't be so efficient in this case. – Columella

Pretty nice. An underrated answer. – Patrica

Beautiful indeed! Can this be constexpr in any sense? On a more general note: are array algorithms unraveled at compile time? – Filiano

@HyperBoar, yes, since C++20 algorithms like std::copy_n() are constexpr. The methods of std::array class are constexpr even earlier. So the example mentioned in my answer successfully compiles using the modern versions of g++ and clang++ compilers and the compiler key -std=c++20: Live demo. – Columella

Answer 3

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.

Diphthongize

Here's mine. Feel free to use any part: melpon.org/wandbox/permlink/arkvF7HpZGr4LKOa. The only reason I didn't use std::copy was to keep it constexpr, since that seemed kind of fitting. – Ladylike

@chris: that's a pretty cool solution - I think you should post it as an answer. – Diphthongize

It's pretty fine where it is considering the OP tagged the question C++11. Because of that, I'd rather keep C++17 improvements in one place. – Ladylike

My C++17 contribution: perfect forwarding, moving from rvalue inputs instead of copying: melpon.org/wandbox/permlink/5O1X7JTAfJ7d40sT BTW your concat technically causes UB since no template parameters can ever satisfy constexpr requirements (the constexpr needs to go because std::copy is never constexpr). – Incorruption

@VittorioRomeo Why do you call f this way f(array, std::integral_constant<std::size_t,Las>{}) and not just f(array,Last)? Is it to enable constexpr evaluation of f? – Bushing

@Bushing : Since the callable will be passed an integral_constant rather than a size_t, it can then use the value in constant expressions (e.g. as a template argument) if desired. – Incorruption

@Incorruption Yes but C++17 implement constexpr lambda, so after inlining, I was thinking that the generated code would be the exact same. On the other side if their is no inlining of the operator() of the lambda, using Last in the type produces generation of as many operator() as their are array size which could lead to code bloat and will certainly slow down execution since calling multiple time a unique function is really cpu friendly. I have doubts so I am wondering if this is a good pattern or an anti-pattern. – Bushing

@Bushing : Function arguments are never constexpr; this is why it's important to encode the desired value into the type (integral_constant in this case). Whether or not the lambda is constexpr is 100% orthogonal as to whether or not it might need the value passed to it as a function argument in a constant context. – Incorruption

@Incorruption Thank you, I really clearly understand what you are talking about. But the argument offset, is not involved in any expression which must be constexpr. If you replace std::integral_constant<size_t,Last>{} by Last the resulting optimized code is exactly the same. Without inlining optimization, the resulting code is smaller if you just use Last. Depending on optimizer deciding to inline or not the lambda, the resulting code will be the same or better if you just do not try to help the compiler! – Bushing

@Bushing : with_acc_sizes appears to be a public interface (based on naming and namespace); just because concat doesn't need offset as a constant expression doesn't mean it shouldn't be written to accommodate all potential callers correctly. If with_acc_sizes were in namespace detail or somesuch where we know the only caller is concat, then I would fully agree with you. :-] – Incorruption

@ildjarn, thank you, now I understand your point of view. I had never think about using this kind of "tag-dispatch" like technique for anything but implementation! – Bushing

Answer 4

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 

Fug

Answer 5

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)...));
}

Illnatured

What's the std::tuple_cat(std::tuple_cat(arrays)...) doing? The inner one looks like it's converting the array into a tuple and the outer one looks like it's concatenating those tuples together. Then its dumping into an array that has the size of the sum of all the sizes in all of the arrays? Nice, except... – Dispend

... except that it's not portable. From tuple_cat "The behavior is undefined if any type in std::decay_t<Tuples>... is not a specialization of std::tuple. However, an implementation may choose to support types (such as std::array and std::pair) that follow the tuple-like protocol." Which is too bad actually. Quite elegant. – Dispend

Answer 6

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.

Chirr

Answer 7

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)...));
}

Victual

Answer 8

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.

Incorruption

You can remove typename and ::type in the using sum_sizes_t =... line – Caxton

@Caxton : I have them there on purpose. :-] Removing them would work here in this context but I prefer my metafunctions to return exactly std::integral_constant rather than a derived type so they can be used with specialization and not just SFINAE. – Incorruption

Answer 9

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 << " ";
    }
}

Globigerina

Answer 10

Here's a C++20 solution that's somewhat shorter, and (unlike most of the other answers) supports arrays of elements that aren't default-constructable:

#include <array>
#include <tuple>
#include <cstddef> // for size_t

// concatenate multiple arrays - requires C++20
//
// The usual approach is to default-construct `std::array<T, Na + Nb>`, then
// overwrite the elements, e.g. with `std::copy()` or loops.
//
// The problem with that is it requires that `T` is default-constructable;
// this implementation does not have that requirement.
template <class T, size_t Na, size_t Nb>
constexpr auto array_cat(
  const std::array<T, Na>& a,
  const std::array<T, Nb>& b,
  auto&&... rest) {
  if constexpr (sizeof...(rest) == 0) {
    return std::apply([](auto&&... elements) {
        return std::array { std::forward<decltype(elements)>(elements)... };
    }, std::tuple_cat(a, b));
  } else {
    return array_cat(a, array_cat(b, std::forward<decltype(rest)>(rest)...));
  }
}

constexpr std::array a {1, 2};
constexpr std::array b {3, 4};
constexpr std::array c {5, 6};
static_assert(array_cat(a, b) == std::array { 1, 2, 3, 4});
static_assert(array_cat(a, b, c) == std::array { 1, 2, 3, 4, 5, 6});

https://godbolt.org/z/T77ob9M65

Samellasameness