是否可以在C++中編寫通用可變參數zipWith？

Question

我想在C++中使用變量arity的通用zipWith函數。我有兩個問題。首先是我無法確定傳遞給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) { 
    ??? 
} 

您必須在表達式部分的參數包後面加一個「...」才能看到展開的列表。你也必須在常規參數部分放置一個：

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::function所以我們可以使用拉姆達或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; 
} 

我想創建的元組，每個元組從採摘從每個向量對應的元素組成的向量。然後，我會創建一個向量 評估結果，每次傳遞一個元組和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）包圍，所以遞歸調用的l值超載不會被錯誤地選擇。改變每個元組元素的一部分的函數必須顯式地獲取當前索引。索引參數包剝離時由一個向上移動：

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

該表是隻要最短輸入向量，所以我們必須每當當前輸入向量結束第一修整表。 （我希望我能在for塊內的標記fe爲const）。我本來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也不支持零碎地將函數參數轉換成函數，其佔位符系統與任意長度的參數包不兼容。我希望我可以列出每個參數就像我可以，如果我必須訪問原始輸入向量....

......等等，爲什麼不我做到這一點？！...

...好吧，我從來沒有聽說過它。我見過將模板參數包傳遞給函數參數;我剛剛在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。我意識到，我可以強制一個矢量減少到沒有強制性的載體：

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的參數個數和數量的輸入向量一致。現在我知道我可以通過抽象兩者遠離固定決鬥函數指針與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限定來進行元素取消引用，並且該函數可以將其用於重載解析。內部確定結果類型的遞歸「調用」需要使用std::forward來防止任何「降級」爲l值引用。它也揭示了這個迭代中的一個缺陷：我需要提供返回類型。

我會解決這個問題，但首先我要解釋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成員函數添加元素的向量返回一個特殊的輸出迭代器。

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，並且 要求只有一個序列的長度被指定，並且其他的至少要一樣長。我在此稱其爲transformV以避免名稱衝突 。