Danra
Danra

Reputation: 9946

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

Upvotes: 18

Views: 7454

Answers (11)

Catriel
Catriel

Reputation: 667

#include <iostream>
#include <array>
#include <tuple>

// concatenate a sequence of std::array objects
template <typename... Arrays> auto array_concat (const Arrays&... arrays) 
{    
    std::array<typename std::tuple_element_t<0, std::tuple<Arrays ...>>::value_type, (arrays.size () + ...)> result;
    std::size_t offset = 0;

    ((std::copy(arrays.begin(), arrays.end(), result.begin() + offset), offset += arrays.size()), ...);

    return result;
}


// Example usage
int main() {
    std::array arr1 { 1, 2, 3 };
    std::array arr2 { 4, 5 };
    std::array arr3 { 6, 7, 8, 9 };
    std::array arr4 { 0 };

    auto result = array_concat (arr1, arr2, arr3, arr4);

    std::cout << "result.size () = " << result.size () << " = " << arr1.size () << " + " << arr2.size () << " + " << arr3.size ()  << " + " << arr4.size () << "\n\n";
    
    for (const auto& elem : result) {
        std::cout << elem << " ";
    }
    std::cout << "\n";
}

Upvotes: 0

Fred Emmott
Fred Emmott

Reputation: 206

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

Upvotes: 1

LTMDUM
LTMDUM

Reputation: 61

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

Upvotes: 4

Jarod42
Jarod42

Reputation: 218323

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

Upvotes: 12

Evg
Evg

Reputation: 26362

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

Upvotes: 2

Constructor
Constructor

Reputation: 7491

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

Upvotes: 23

DrPizza
DrPizza

Reputation: 18360

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

Upvotes: 1

ildjarn
ildjarn

Reputation: 63005

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.

Upvotes: 1

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275976

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.

Upvotes: 2

Richard Hodges
Richard Hodges

Reputation: 69942

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 

Upvotes: 3

Vittorio Romeo
Vittorio Romeo

Reputation: 93394

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.

Upvotes: 6

Related Questions