连接一系列std::arrays

Question

考虑以下内容：(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;
}

给定一个序列 std::array<T, length1>, std::array<T, length2>, ..., std::array<T, lengthK>，我该如何推广上述代码并编写一个函数，将这个序列连接到 std::array<T, sum(lengths)> 中？

如果有一种方法可以编写可重用的函数，使用给定的二元操作减少类似模板类的序列，例如，在上面的示例中使用concat，而不是编写特殊方法（每次二元操作更改都必须重新编写）。

（如果我理解正确，相关的标准库算法(accumulate, reduce)仅在二元操作结果的类始终相同时起作用。）

- Danra

---

我们有std::tuple_cat。一个选项是简单地编写从结果元组到数组的转换。 - chris

@chris 很不错，我不知道那个函数。但是正如我上面所写的，如果有一个解决方案可以将任何给定的模板二元操作应用于不同类别的对象序列，那就太好了（当然，该操作应该是可结合的，并且适用于所有中间结果）。 - Danra

Answer 1

这是一个简单的 C++17 解决方案，使用折叠表达式(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;
}

使用示例：

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

实时演示

- Constructor

---

太好了！有没有关于如何使用折叠表达式来实现通用版本的想法（适用于任意二进制运算符）？ - Danra

@Danra 在这种情况下，通用版本不会那么有效。 - Constructor

相当不错。一个被低估的答案。 - tigertang

真的很漂亮！这个可以在任何意义上成为constexpr吗？更一般地说，数组算法是否会在编译时展开？ - HyperBoar

@HyperBoar，是的，自从C++20算法中出现了std::copy_n()等constexpr函数后，std::array类的方法甚至更早就已经是constexpr了。因此，我在答案中提到的示例可以成功编译使用现代版本的g++和clang++编译器以及编译器选项-std=c++20：在线演示。 - Constructor

Answer 2

您可以执行以下操作：

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

使用方式

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

并且

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

C++14演示
C++11演示

- Jarod42

---

那很漂亮。 - Danra

我相信这是[tag:C++14]，对吗？（http://coliru.stacked-crooked.com/a/be3a0aa97b39c1db） - Yakk - Adam Nevraumont

@Yakk-AdamNevraumont: 的确，缺少尾随返回类型是C++11的。已添加演示。 - Jarod42

@Jarod42 嗯，出于某种原因，我以为这是一个constexpr问题。不要理我。 - Yakk - Adam Nevraumont

直到C++20，std::copy才成为constexpr...;-) - Jarod42

Answer 3

给定一系列的std::array<T, length1>, std::array<T, length2>, ..., std::array<T, lengthK>，如何编写一个函数将这些序列连接成一个std::array<T, sum(lengths)>？

以下是C++17的解决方案。它很可能可以缩短和改进，正在努力中。

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

使用方法：

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

实时 wandbox 示例

适用于 g++7 和 clang++5。

- Vittorio Romeo

---

这是我的代码。随意使用其中的任何部分：http://melpon.org/wandbox/permlink/arkvF7HpZGr4LKOa。我没有使用`std::copy`的唯一原因是为了保持其`constexpr`，因为这似乎很合适。 - chris

考虑到OP标记了问题为C++11，它的位置还是相当不错的。因此，我宁愿将C++17的改进保留在一个地方。 - chris

我的C++17贡献：完美转发，从rvalue输入中移动而不是复制：http://melpon.org/wandbox/permlink/5O1X7JTAfJ7d40sT 顺便说一句，你的concat在技术上会导致UB，因为没有模板参数可以满足constexpr要求（需要去掉constexpr，因为std::copy永远不是constexpr）。 - ildjarn

@Oliv：函数参数永远不是constexpr；这就是将期望的值编码到类型中（在这种情况下使用 integral_constant）的重要性所在。Lambda 是否为 constexpr，与它在常量上下文中是否需要作为函数参数传递的值完全无关。 - ildjarn

@Oliv：根据命名和命名空间，with_acc_sizes似乎是一个公共接口；仅仅因为concat不需要将offset作为常量表达式，这并不意味着它不应该被编写以正确适应所有潜在的调用者。如果with_acc_sizes位于namespace detail或类似的位置，我们知道唯一的调用者是concat，那么我完全同意你的观点。:-] - ildjarn

Answer 4

使用@Constructor的C++17解决方案的更简洁演化，还增加了Type不需要默认可构造的额外优势。

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

- LTMDUM

---

std::tuple_cat(std::tuple_cat(arrays)...)是什么意思？内部的函数看起来像是将数组转换为元组，而外部的函数则像是将这些元组连接在一起。然后它会被转储到一个数组中，该数组的大小等于所有数组中所有大小的总和？很好，但是... - Adrian

除了它不可移植之外。来自tuple_cat *"如果std::decay_t<Tuples>中的任何类型不是std::tuple的特化，则其行为未定义。然而，实现可以选择支持遵循类似元组协议的类型（例如std::array和std::pair）"。这实在太糟糕了。相当优雅。 - Adrian

Answer 5

我的第一个想法是考虑将数组转换为引用元组（绑定），使用 tuple_cat 进行操作，然后执行构建最终数组所需的任何操作（即根据最初传入的参数移动或复制）：

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

预期结果：

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

- Richard Hodges

Answer 6

这是一个使用 constexpr 的 C++17 解决方案，可以正确处理只支持可移动语义的类型。

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

- Evg

Answer 7

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

这让我们可以内联扩展参数包。

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

这让我们来到第二点。对于N，简单的方法是：

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

但不使用递归也应该是可行的。

未测试代码。

- Yakk - Adam Nevraumont

Answer 8

严格采用C++11；不如@Jarod42的易读，但如果调用树没有完全展开（即未全部内联），并且有许多数组，则潜在效率更高，因为只存在一个结果对象而不是多个临时逐渐增长的结果对象：

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

在线演示

请注意，对于rvalues，使用std::move算法进行转发，而不是std::copy。

- ildjarn

---

在 using sum_sizes_t =...那行中，您可以删除 typename 和 ::type。 - Danra

@Danra：我有意放置它们。:-] 在这种情况下删除它们可以起作用，但我更喜欢我的元函数返回确切的std::integral_constant而不是派生类型，这样它们就可以与专门化一起使用，而不仅仅是SFINAE。 - ildjarn

Answer 9

这并不具有普适性，但利用了在花括号中展开两个数组的事实，可以用它来初始化一个新数组。

无论如何，我不确定泛化有多大用处。对于一堆大小不匹配的数组，除了将它们全部合并起来，还能做什么呢？

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

- DrPizza