C++で一般的なvariadic zipWithを記述することはできますか？

Question

私は変数arityのC++で一般的なzipWith関数が必要です。私には2つの問題があります。最初は、zipWithに渡された関数ポインタの型を判別できないということです。 zipWithに渡されるベクトルの数と同じアリティでなければならず、ベクトルの要素型への参照をそれぞれ受け入れる必要があります。二つ目は、これらのベクトルを並行して歩いて引数リストを作成し、func（）を呼び出す方法と、最短ベクトルが使い尽くされたときにベールする方法がわかりません。ここで

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

あなたは、あなたの関数パラメータはベクトルの束であると言いました。ここでは、Vargsのそれぞれが実際にstd::vectorであることを期待しています。入力変換は、パラメータパックに適用することができ、なぜ私たちは、あなたがベクトルを持っていることを保証するものではありません。

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

ベクターは、巨大なオブジェクトで、それではconstリットル値参照を使用させることができます。また、私たちは私たちは、ラムダまたはstd::bind式を使用することができますstd::functionを使用することができます。

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オブジェクトに変換されている古典的な関数ポインタを受け入れないでしょう。だから私はラムダで包んでいたのかもしれません...）

この時点で、私はページをリロードして、response (by pmr)の1つを見ました。私はこのジッパー、折り畳み、爆発、物事を実際に理解していないので、彼のソリューションは複雑すぎると思いました。だから私は、より直接的な解決策について考えた：

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

私は、各タプルは各ベクトルから対応する要素を摘採から作られたタプルのベクトルを作成します。次に、タプルを渡すことで 評価結果のベクトルを作成し、毎回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）で囲む必要があるため、再帰呼び出しのI値のオーバーロードが誤って選択されないようにすることです。各タプル要素の一部を変更する関数は、明示的に現在のインデックスを取得する必要があります。インデックスは、パラメータパック剥離時つによって上に移動：

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

テーブルであれば、最短の入力ベクトルとしてあるので、我々は現在の入力ベクトルが最初に終了するたびにテーブルをトリミングしなければなりません。 （feをforブロック内にconstとしてマークしたいと思います）。firstとrestはstd::vectorとなりましたが、私はそれを抽象化することができました。私が必要とするのは、反復インターフェース内の標準（シーケンス）コンテナに一致するタイプです。

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

私が行うことができ、個々のケース：しかし、今、私はevaluateに困惑

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は、引数を関数に小刻みにカリングすることも、そのプレースホルダシステムは任意の長さのパラメータパックと互換性がありません。私は私ができるように私は、元の入力ベクトルへのアクセスを持っていた場合、私はちょうど、各パラメータをリストなあ....

...待って、なぜない私はちょうどその？！...

...まあ、聞いたことがありません。私はテンプレートパラメータパックを関数パラメータに転送することを見てきました。私はちょうど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...)); } 

そして確かに、それは機能しました！もちろん、これは、私が他の回答者と同じように悪いと思った（別のやり方で）ことを意味しました。それはまた、私が不必要にこの投稿のほとんどであなたを退屈させたことを意味します。これをラップすると、を汎用シーケンスコンテナタイプに置き換えることがzip_widthに適用できることがわかりました。私はここのコードをコピーしたとして、私は確信してfuncの引数の数と番号ことを確認するのを忘れているので、私は、static_assertを追加

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

：そして、私はノー必須ベクトルに必須1つのベクトルを減らすことができることに気づきましたの入力ベクトルが一致する。今、私は両方の抽象化によりデュエル関数ポインタ対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（cv）資格を扱います。だから私はcontainersに切り替えました。 funcにはどのような構造もあります。 operator()の複数のバージョンを持つクラスオブジェクトでもあります。私はコンテナにr値を使用しているので、要素逆参照には最高のcv修飾を使用し、関数はそれを過負荷解決に使用できます。結果の型を内部的に決定するための再帰的な "呼び出し"は、l値参照への "ダウングレード"を防ぐために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をコピーし、明示的に異なるサイズのタイプを使用して、異なるコンテナタイプに対して校正、少なくともベース場合の結果のタイプを挙げます。

出力イテレータを実行する関数は、通常、すべてのイテレータが終了した後にイテレータを返します。これにより、中断した場所で新しい出力を開始することができます（別の出力機能でも​​）。これらはすべて擬似イテレータなので、標準出力イテレータは重要ではありません。 doトラック位置であるため、出力イテレータとして前方イテレータ（またはそれ以上）を使用する場合は重要です。 （出力として前方イテレータを使用するのは、最大転送回数が残りのイテレーション空間を超えない限り安全です）。一部の関数は、出力イテレータをパラメータリストの最後に置きます。 zip_widthは、パラメータパックが最後になければならないため、後者を使用する必要があります。

zipWithの接尾辞の戻り値型に移動すると、戻り値の型式を計算するときに、関数の署名の公正なゲームがすべて行われます。また、コンパイル時の非互換性のために計算ができないかどうかをすぐに知ることができます。 std::back_inserter関数は、特別な出力イテレータを、push_backメンバ関数を介して要素を追加するベクトルに戻します。

Answer 2

は、私が一緒に石畳です：

#include <iostream> 
#include <vector> 
#include <utility> 

template<typename F, typename T, typename Arg> 
auto fold(F f, T&& t, Arg&& a) 
    -> decltype(f(std::forward<T>(t), std::forward<Arg>(a))) 
{ return f(std::forward<T>(t), std::forward<Arg>(a)); } 

template<typename F, typename T, typename Head, typename... Args> 
auto fold(F f, T&& init, Head&& h, Args&&... args) 
    -> decltype(f(std::forward<T>(init), std::forward<Head>(h))) 
{ 
    return fold(f, f(std::forward<T>(init), std::forward<Head>(h)), 
       std::forward<Args>(args)...); 
} 

// hack in a fold for void functions 
struct ignore {}; 

// cannot be a lambda, needs to be polymorphic on the iterator type 
struct end_or { 
    template<typename InputIterator> 
    bool operator()(bool in, const std::pair<InputIterator, InputIterator>& p) 
    { return in || p.first == p.second; } 
}; 

// same same but different 
struct inc { 
    template<typename InputIterator> 
    ignore operator()(ignore, std::pair<InputIterator, InputIterator>& p) 
    { p.first++; return ignore(); } 
}; 

template<typename Fun, typename OutputIterator, 
     typename... InputIterators> 
void zipWith(Fun f, OutputIterator out, 
      std::pair<InputIterators, InputIterators>... inputs) { 
    if(fold(end_or(), false, inputs...)) return; 
    while(!fold(end_or(), false, inputs...)) { 
    *out++ = f(*(inputs.first)...); 
    fold(inc(), ignore(), inputs...); 
    } 
} 

template<typename Fun, typename OutputIterator, 
     typename InputIterator, typename... Rest> 
void transformV(Fun f, OutputIterator out, InputIterator begin, InputIterator end, 
       Rest... rest) 
{ 
    if(begin == end) return ; 
    while(begin != end) { 
    *out++ = f(*begin, *(rest)...); 
    fold(inc2(), ignore(), begin, rest...); 
    } 
} 

struct ternary_plus { 
    template<typename T, typename U, typename V> 
    auto operator()(const T& t, const U& u, const V& v) 
    -> decltype(t + u + v) // common type? 
    { return t + u + v; } 
}; 

int main() 
{ 
    using namespace std; 
    vector<int> a = {1, 2, 3}, b = {1, 2}, c = {1, 2, 3}; 
    vector<int> out; 

    zipWith(ternary_plus(), back_inserter(out) 
      , make_pair(begin(a), end(a)) 
      , make_pair(begin(b), end(b)) 
      , make_pair(begin(c), end(c))); 

    transformV(ternary_plus(), back_inserter(out), 
      begin(a), end(a), begin(b), begin(c)); 

    for(auto x : out) { 
    std::cout << x << std::endl; 
    } 

    return 0; 
} 

これは、以前のバージョンに比べて若干改善変種です。すべての 良いプログラムである必要があります、それは左折を定義することから始まります。

ペアでパックされたイテレータの問題は解決しません。

stdlibの用語では、この関数はtransformと呼ばれ、 は、1つのシーケンスの長さのみが指定され、その他のものは少なくとも同じ長さであることを要求します。私はこれをtransformVと呼んで、 の名前の衝突を避けるためにここに呼び出しました。