concatenating any number of std::arrays, using only the bare minimum of ctor calls

Question

I want to implement this function (a function which can concatenate any number of arrays, and it considers the value category as well):

template <typename ELEMENT, std::size_t ...SIZE>
constexpr auto concat(std::array<ELEMENT, SIZE> &&&...arrays) {
    return std::array<ELEMENT, SUMMED_SIZE>{ CONCATENATED_ARRAY_ELEMENTS };
}

Notes:

• By &&&, I mean that each array in arrays can be rvalue/lvalue ref (can be mixed)
• By SUMMED_SIZE, I mean the the sum of SIZE (this is trivial)
• By CONCATENATED_ARRAY_ELEMENTS, I mean all the elements of each array of arrays concatenated. If an array in arrays is an rvalue/lvalue, then the corresponding elements in CONCATENATED_ARRAY_ELEMENTS should also be rvalues/lvalues.
• I don't want to have extra move/copy ctor calls (otherwise it would be trivial to implement this by using recursion), I want to have only one move/copy for each element in arrays.
• ELEMENT may not be default-constructible, so elements must be constructed by copy/move ctor.

Is this possible to do?

It is not hard to implement this function for two arrays (godbolt), but I'm not sure how to generalize this to more than two arrays. I could write 3/4/5/etc-argument function manually, but the number of needed functions grows exponentially.

Answer 1

This is a very interesting task. I suggest using an iterator object to populate the array. I think this is much shorter than other suggestions.

template <typename IT>
constexpr void populate(IT *&& it, std::size_t OFFSET, std::size_t TOTAL) {
    //
}

template <typename IT, typename T, std::size_t NA, std::size_t ... NR>
void populate(IT *&& it, std::size_t OFFSET, std::size_t N_TOTAL, const std::array<T, NA> & array_a, const std::array<T, NR> & ... arrays) {
    std::copy_n(std::make_move_iterator(array_a.begin()), NA, it);
    it += NA;
    if ((OFFSET + NA) < N_TOTAL) {
        populate(std::move(it), OFFSET + NA, N_TOTAL, arrays...);
    }
}

template <typename T, std::size_t ... Ns>
constexpr auto concat2(const std::array<T, Ns> & ... arrays)
{
    std::array<T, (Ns + ...)> result;
    auto it = result.begin();
    populate(std::move(it), (std::size_t)0, (std::size_t)(Ns + ...), arrays...);
    return result;
}

EDIT If using the default constructor is prohibited, and only move ctor allowed, you can use a different version of the code)

template <typename ELEMENT, std::size_t... INDICES>
constexpr auto populate_with_move(
                      std::array<ELEMENT *, sizeof...(INDICES)> & array_a,
                      std::index_sequence<INDICES...>) {
    return std::array<ELEMENT, sizeof...(INDICES)>{std::move(*(array_a[INDICES]))...};
}

template <typename ELEMENT, std::size_t ... Ns>
constexpr auto concat_2(std::array<ELEMENT, Ns> & ... arrays)
{
    std::array<ELEMENT *, (Ns + ...)> result;
    std::size_t i = 0;
    ([&](){
        auto it = arrays.begin();
        while (it != arrays.end()) {
            result[i] = &(*it);
            i++;
            it++;
        }
    }(), ...);
    return populate_with_move(result, std::make_index_sequence<(Ns + ...)>());
}

Answer 2

The ask here is basically a simplified version of std::tuple_cat. It's a lot easier than the general problem since you're accepting just std::array<T, N1>, std::array<T, N2>, ..., std::array<T, Nx> and returning std::array<T, N1 + N2 + ... + Nx>. So computing the return type is trivial (and also unnecessary).

But the actual indexing logic is the same. We need to produce two lists of numbers: a list of outer indices and a list of inner indices. The goal is to ultimately produce the expression:

return std::array{ arrays...[Inner][Outer]... };

Where, e.g., if we're concatenating an array of size 4 and an array of size 2, we'd want something like:

• Outer is the pack {0, 1, 2, 3, 0, 1}
• Inner is the pack {0, 0, 0, 0, 1, 1}

Which we can do, with Boost.Mp11, like this:

template<typename... Arrays>
constexpr auto concat(Arrays&& ... arrays) {
  // turns (array<int, 4>, array<int, 2>) [4, 2]
  using Sizes = mp_list<mp_int<std::tuple_size_v<std::remove_cvref_t<Arrays>>>...>;

  // the inner transform gives us [[0, 0, 0, 0], [1, 1]]
  // so we flatten it with mp_append
  using Inner = mp_apply<mp_append,
    mp_transform<mp_repeat, mp_transform<mp_list, mp_iota_c<sizeof...(Arrays)>>, Sizes>
    >;

  // the inner lists give us [[0, 1, 2, 3], [0, 1]]
  // so we flatten it with mp_append
  using Outer = mp_apply<mp_append,
    mp_list<mp_iota_c<std::tuple_size_v<std::remove_cvref_t<Arrays>>>...>
    >;

  return [&]<class... Is, class... Js>(mp_list<Is...>, mp_list<Js...>){
    return std::array{
        std::forward_like<decltype(arrays...[Is::value])>(
            arrays...[Is::value][Js::value]
        )...
    };
  }(Inner{}, Outer{});

The inner construction here is pretty awkward because it's not enough to do FWD(arr)[i][j] - because array's index operator doesn't propagate value category. So we need to use std::forward_like, which needs different expressions for the type and operand - which makes it inconvenient to macro out. I suppose you could define a function like std::array{index(FWD(arrays...[Is::value]), Js::value)...} but not sure it's worth it. Maybe if you do this in several places.

But this correctly moves or copies as desired.

Demo.

Answer 3

Building on @fareanor's version, you can create a generic version with your requirements, even that there's no default-constructor (and no default value), if you first gather the inputs as pointers first (in a std::variant because you don't know if you want to copy or move them), and then convert the array of the variants of the pointers back to the target array at the very end, where you then decide to actually call the copy or move constructors based on the contents of the variant.

If you don't need to mix T const& and T&&, then you can get rid of the std::variant and just implement two overloads that use an array of pointers (one const, the other not).

You then have to hope that your compiler optimizes all of that stuff away again.

The following code also doesn't handle the case when the type is only copy-constructible or only move-constructible (it assumes both constructors exist) - there would need to be some additional overloads or if constexpr or similar (but in that case ones that don't require a variant), but I leave that as an exercise to the reader.

Another exercise for this code could be to add C++20 concepts support to make compiler errors better understandable - the typename... Arrays is necessary in order to be able to mix copy and move within the concat arguments in combination with std::forward.

template<typename T, std::size_t N, typename It>
constexpr auto concat_array_helper(std::array<T, N> const& array, It it)
{
    for (std::size_t i = 0; i < N; ++i)
        *it++ = &array[i];
    return it;
}

template<typename T, std::size_t N, typename It>
constexpr auto concat_array_helper(std::array<T, N>&& array, It it)
{
    for (std::size_t i = 0; i < N; ++i)
        *it++ = &array[i];
    return it;
}

template<typename... Arrays>
struct concat_array_get_type_of_first;

template<typename T, std::size_t N, typename... Arrays>
struct concat_array_get_type_of_first<std::array<T, N>, Arrays...> {
    using value_type = T;
};

template<typename T, std::size_t... Index>
constexpr auto concat_array_copy_or_move(std::index_sequence<Index...>, std::array<std::variant<T const*, T*>, sizeof...(Index)> const& input)
{
    constexpr std::size_t N = sizeof...(Index);
    auto unpack = [] (std::variant<T const*, T*> const& pointer) -> T {
        if (std::holds_alternative<T const*>(pointer))
            return *std::get<T const*>(pointer);
        else
            return std::move(*std::get<T*>(pointer));
    };
    return std::array<T, N>{ unpack(input[Index])... };
}

template<typename... Arrays>
constexpr auto concat(Arrays&& ... arrays)
{
    using T = typename concat_array_get_type_of_first<std::decay_t<Arrays>...>::value_type;
    constexpr std::size_t const N = (std::tuple_size_v<std::decay_t<Arrays>> + ...);

    std::array<std::variant<T const*, T*>, N> temp;

    auto it = temp.begin();
    ([&]() {
        it = concat_array_helper(std::forward<Arrays>(arrays), it);
    }(), ...);

    return concat_array_copy_or_move(std::make_index_sequence<N>{}, temp);
}

(There's currently no transform_n, unfortunately, so the iteration is done explicitly here.)

Answer 4

You can make use of C++17 fold-expressions in order to avoid recursive unpacking.

I don't think it's possible to copy or move by value category because perfect forwarding is not applicable here so from inside the function, each array will be treated as an lvalue reference.

Since an rvalue reference can be bound to an lvalue reference to a const, I would suggest to take the arguments by const my_type & ... in order to be able to mix lvalue/rvalue refs as arguments in the call.

That would lead to something like below:

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

    auto it = result.begin();
    ([&](){
        std::copy_n(arrays.begin(), Ns, it);
        it += Ns;
    }(), ...);

    return result;
}

Of course you can define an overload for the specific case with only rvalue refs in order to replace copies by moves:

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

    auto it = result.begin();
    ([&](){
        std::copy_n(std::make_move_iterator(arrays.begin()), Ns, it);
        it += Ns;
    }(), ...);

    return result;
}

---

EDIT:

I don't think it's possible to create such a function with non-default-constructible elements without providing a default value (i.e. if we keep the function prototype requirements as is).

But if you are okay to change the function signature to accept a default value, you could add the following overloads:

template <typename T, std::size_t ... Ns>
constexpr auto concat(const T & def_val, const std::array<T, Ns> & ... arrays)
{
    std::array<T, (Ns + ...)> result = make_array<T, (Ns + ...)>(def_val);

    auto it = result.begin();
    ([&](){
        std::copy_n(arrays.begin(), Ns, it);
        it += Ns;
    }(), ...);

    return result;
}

// Overload for rvalues
template <typename T, std::size_t ... Ns>
constexpr auto concat(const T & def_val, std::array<T, Ns> && ... arrays)
{
    std::array<T, (Ns + ...)> result = make_array<T, (Ns + ...)>(def_val);

    auto it = result.begin();
    ([&](){
        std::copy_n(std::make_move_iterator(arrays.begin()), Ns, it);
        it += Ns;
    }(), ...);

    return result;
}

With make_array() defined as follows:

template <typename T, std::size_t ... Is>
std::array<T, sizeof...(Is)> make_array_impl(std::index_sequence<Is...>, const T & def_value)
{
    return {((void)Is, def_value)...};
}

template <typename T, std::size_t S>
std::array<T, S> make_array(const T & def_value)
{
    return make_array_impl(std::make_index_sequence<S>(), def_value);
}