c++ - 是否可以在 C++ 中编写通用的可变参数 zipWith？

Question

我想要一个通用的 zipWith 函数在 C++ 变量arity。我有两个问题。首先是我无法确定传递给 zipWith 的函数指针的类型。它必须与传递给 zipWith 的 vector 数量相同，并且必须分别接受对 vector 元素类型的引用。第二个是我不知道如何并行遍历这些 vector 来构建参数列表、调用 func() 并在最短的 vector 用完后保释。

template <typename R, typename T, typename... Vargs>
std::vector<R> zipWith (R func(???<what goes here>), std::vector<T> first, Vargs rest) {
   ???
}

Answer 1

我有一个很长的答案，然后我改变了主意，使解决方案变得更短。但我将展示我的思考过程并给你们两个答案!

我的第一步是确定正确的签名。我不了解所有内容，但您可以将参数包视为隐藏文本转储的实际项目的逗号分隔列表。您可以通过更多以逗号分隔的项目扩展任一侧的列表!所以直接应用:

template <typename R, typename T, typename... Vargs>
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, Vargs rest) {
   ???
}

您必须在表达式部分的参数包后放置一个“...”才能查看扩展列表。您也必须在常规参数部分放置一个:

template <typename R, typename T, typename... Vargs>
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, Vargs... rest) {
   ???
}

你说你的函数参数是一堆 vector 。在这里，您希望 Vargs真的是 std::vector .类型转换可以应用于参数包，那么我们为什么不确保您拥有 vector :

template <typename R, typename T, typename... Vargs>
std::vector<R> zipWith (R func(T,Vargs...), std::vector<T> first, std::vector<Vargs> ...rest) {
   ???
}

vector 可以是巨大的对象，所以让我们使用 const l 值引用。此外，我们可以使用 std::function所以我们可以使用 lambda 或 std::bind表达式:

template <typename R, typename T, typename... Vargs>
std::vector<R> zipWith (std::function<R(T, Vargs...)> func, std::vector<T> const &first, std::vector<Vargs> const &...rest) {
   ???
}

(我在这里使用 std::pow 进行测试时遇到了问题。我的编译器不接受将经典函数指针转换为 std::function 对象。所以我不得不将它包装在 lambda 中。也许我应该在这里问一下....)

这时，我重新加载页面，看到一个 response (by pmr) .我真的不理解这种压缩、折叠、爆炸等等，所以我认为他/她的解决方案太复杂了。所以我想到了一个更直接的解决方案:

template < typename R, typename T, typename ...MoreTs >
std::vector<R>
zip_with( std::function<R(T,MoreTs...)> func,
 const std::vector<T>& first, const std::vector<MoreTs>& ...rest )
{
    auto const      tuples = rearrange_vectors( first, rest... );
    std::vector<R>  result;

    result.reserve( tuples.size() );
    for ( auto const &x : tuples )
        result.push_back( evaluate(x, func) );
    return result;
}

我会创建一个元组 vector ，其中每个元组都是通过从每个 vector 中提取相应元素而制成的。然后我会创建一个 vector
传递元组和 func 的评估结果每一次。
rearrange_vectors必须提前制作值表(默认构造)并一次填写每个条目一个子对象:

template < typename T, typename ...MoreTs >
std::vector<std::tuple<T, MoreTs...>>
rearrange_vectors( const std::vector<T>& first,
 const std::vector<MoreTs>& ...rest )
{
    decltype(rearrange_vectors(first, rest...))
      result( first.size() );

    fill_vector_perpendicularly<0>( result, first, rest... );
    return result;
}

第一行的第一部分让函数无需复制粘贴就可以访问自己的返回类型。唯一需要注意的是，r 值引用参数必须用 std::forward 括起来。 (或 move )因此不会错误地选择递归调用的左值重载。改变每个元组元素的一部分的函数必须显式地采用当前索引。参数包剥离期间索引向上移动1:

template < std::size_t, typename ...U >
void  fill_vector_perpendicularly( std::vector<std::tuple<U...>>& )
{ }

template < std::size_t I, class Seq, class ...MoreSeqs, typename ...U >
void  fill_vector_perpendicularly( std::vector<std::tuple<U...>>&
 table, const Seq& first, const MoreSeqs& ...rest )
{
    auto        t = table.begin();
    auto const  te = table.end();

    for ( auto  f = first.begin(), fe = first.end(); (te != t) && (fe
     != f) ; ++t, ++f )
        std::get<I>( *t ) = *f;
    table.erase( t, te );
    fill_vector_perpendicularly<I + 1u>( table, rest... );
}

表格与最短的输入 vector 一样长，因此每当当前输入 vector 首先结束时，我们必须修剪表格。 (我希望我可以在 fe 块中将 const 标记为 for。)我最初有 first和 rest如 std::vector ，但我意识到我可以把它抽象出来；我所需要的只是与迭代界面中的标准(序列)容器相匹配的类型。但现在我难住了 evaluate :

template < typename R, typename T, typename ...MoreTs >
R  evaluate( const std::tuple<T, MoreTs...>& x,
 std::function<R(T,MoreTs...)> func )
{
     //???
}

我可以做个别情况:

template < typename R >
R  evaluate( const std::tuple<>& x, std::function<R()> func )
{ return func(); }

template < typename R, typename T >
R  evaluate( const std::tuple<T>& x, std::function<R(T)> func )
{ return func( std::get<0>(x) ); }

但我不能将它概括为递归情况。 IIUC, std::tuple不支持将尾部(和/或头部)剥离为子元组。 std::bind也没有支持零散地将参数柯里化到函数中，并且其占位符系统与任意长度的参数包不兼容。我希望我可以像我可以访问原始输入 vector 一样列出每个参数......

...等等，为什么不 我就是这样做的 ？!...

……嗯，我从来没有听说过。我已经看到将模板参数包传输到函数参数；我刚刚在 zipWith 中展示了它.我可以从函数参数列表到函数内部吗？ (在我写的时候，我现在记得在类构造函数的成员初始化部分看到它，对于数组或类类型的非静态成员。)只有一种方法可以找到:

template < typename R, typename T, typename ...MoreTs >
std::vector<R>
zip_with( std::function<R(T,MoreTs...)> func, const std::vector<T>&
 first, const std::vector<MoreTs>& ...rest )
{
    auto const  s = minimum_common_size( first, rest... );
    decltype(zip_with(func,first,rest...))         result;

    result.reserve( s );
    for ( std::size_t  i = 0 ; i < s ; ++i )
        result.push_back( func(first[i], rest[i]...) );
    return result;
}

我被迫预先计算调用总数:

inline  std::size_t minimum_common_size()  { return 0u; }

template < class SizedSequence >
std::size_t  minimum_common_size( const SizedSequence& first )
{ return first.size(); }

template < class Seq, class ...MoreSeqs >
std::size_t
minimum_common_size( const Seq& first, const MoreSeqs& ...rest )
{ return std::min( first.size(), minimum_common_size(rest...) ); }

果然，它奏效了!当然，这意味着我和其他受访者一样(以不同的方式)过度考虑了这个问题。这也意味着我不必要地对这篇文章的大部分内容感到厌烦。当我结束这个时，我意识到 std::vector 的替换具有通用序列容器类型的可以应用于 zip_width .我意识到我可以将强制的单 vector 减少到无强制 vector :

template < typename R, typename ...T, class ...SizedSequences >
std::vector<R>
zip_with( R func(T...) /*std::function<R(T...)> func*/,
 SizedSequences const& ...containers )
{
    static_assert( sizeof...(T) == sizeof...(SizedSequences),
     "The input and processing lengths don't match." );

    auto const  s = minimum_common_size( containers... );
    decltype( zip_with(func, containers...) )     result;

    result.reserve( s );
    for ( std::size_t  i = 0 ; i < s ; ++i )
        result.push_back( func(containers[i]...) );
    return result;
}

我添加了 static_assert因为我在这里复制了代码，因为我忘记确保 func的参数计数和输入 vector 的数量一致。现在我意识到我可以修复决斗函数指针 vs. std::function通过抽象两个对象:

template < typename R, typename Func, class ...SizedSequences >
std::vector<R>
zip_with( Func&& func, SizedSequences&& ...containers )
{
    auto const     s = minimum_common_size( containers... );
    decltype( zip_with<R>(std::forward<Func>(func),
     std::forward<SizedSequences>(containers)...) )  result;

    result.reserve( s );
    for ( std::size_t  i = 0 ; i < s ; ++i )
        result.push_back( func(containers[i]...) );
    return result;
}

使用 r 值引用标记函数参数是通用传递方法。它处理各种引用和 const/ volatile (简历)资格。这就是为什么我换了 containers到它。 func可以有任何结构；它甚至可以是具有多个版本 operator () 的类对象.由于我对容器使用 r 值，因此它们将使用最佳的 cv 限定来取消引用元素，并且该函数可以将其用于重载解析。内部确定结果类型的递归“调用”需要使用 std::forward防止对左值引用的任何“降级”。它还揭示了本次迭代中的一个缺陷:I 必须提供返回类型。

我会解决这个问题，但首先我想解释 STL 方式。您不会预先确定特定的容器类型并将其返回给用户。你要求一个特殊的对象，一个输出迭代器，你将结果发送到它。迭代器可以连接到一个容器，标准提供了多种容器。它可以连接到输出流，直接打印结果!迭代器方法也让我不必直接担心内存问题。

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <utility>
#include <vector>

inline  std::size_t minimum_common_size()  { return 0u; }

template < class SizedSequence >
std::size_t  minimum_common_size( const SizedSequence& first )
{ return first.size(); }

template < class Seq, class ...MoreSeqs >
std::size_t  minimum_common_size( const Seq& first,
 const MoreSeqs& ...rest )
{
    return std::min<std::size_t>( first.size(),
     minimum_common_size(rest...) );
}

template < typename OutIter, typename Func, class ...SizedSequences >
OutIter
zip_with( OutIter o, Func&& func, SizedSequences&& ...containers )
{
    auto const  s = minimum_common_size( containers... );

    for ( std::size_t  i = 0 ; i < s ; ++i )
        *o++ = func( containers[i]... );
    return o;
}

template < typename Func, class ...SizedSequences >
auto  zipWith( Func&& func, SizedSequences&& ...containers )
 -> std::vector<decltype( func(containers.front()...) )>
{
    using std::forward;

    decltype( zipWith(forward<Func>( func ), forward<SizedSequences>(
     containers )...) )  result;
#if 1
    // `std::vector` is the only standard container with the `reserve`
    // member function.  Using it saves time when doing multiple small
    // inserts, since you'll do reallocation at most (hopefully) once.
    // The cost is that `s` is already computed within `zip_with`, but
    // we can't get at it.  (Remember that most container types
    // wouldn't need it.)  Change the preprocessor flag to change the
    // trade-off.
    result.reserve( minimum_common_size(containers...) );
#endif
    zip_with( std::back_inserter(result), forward<Func>(func),
     forward<SizedSequences>(containers)... );
    return result;
}

我复制了 minimum_common_size在这里，但明确提到了最小基本情况的结果类型，使用不同大小类型针对不同容器类型进行校对。

采用输出迭代器的函数通常在所有迭代器完成后返回迭代器。这使您可以从中断的地方开始新的输出运行(即使使用不同的输出功能)。这对于标准输出迭代器来说并不重要，因为它们都是伪迭代器。使用前向迭代器(或更高版本)作为输出迭代器时很重要，因为它们 做 轨道位置。 (使用前向迭代器作为输出迭代器是安全的，只要最大传输次数不超过剩余迭代空间。)有些函数将输出迭代器放在参数列表的末尾，其他函数放在开头； zip_width必须使用后者，因为参数包必须放在最后。

移至 zipWith 中的后缀返回类型在计算返回类型表达式时，使函数签名的每个部分都公平游戏。如果由于编译时不兼容而无法完成计算，它也会让我立即知道。 std::back_inserter函数返回一个特殊的输出迭代器到通过 push_back 添加元素的 vector 。成员函数。