क्या सी ++ में जेनेरिक वैरैडिक ज़िप लिखना संभव है?

Question

मैं एक सामान्य ज़िप चाहता हूं जो परिवर्तनीय धैर्य के सी ++ में कार्य करता है। मुझे दो समस्याएं हैं पहला यह है कि मैं ज़िप के साथ पारित फ़ंक्शन पॉइंटर का प्रकार निर्धारित नहीं कर सकता। यह एक ही धर्मार्थ होना चाहिए क्योंकि ज़िपों को पारित करने वाले वैक्टरों की संख्या क्रमशः वैक्टरों के तत्व प्रकारों के संदर्भों को स्वीकार करनी चाहिए। दूसरी बात यह है कि मुझे नहीं पता कि एक तर्क सूची बनाने के लिए समानांतर में इन वैक्टरों को कैसे चलना है, 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 वस्तु में परिवर्तित किया जा रहा तो मुझे इसे लैम्ब्डा में लपेटना पड़ा। शायद मुझे इसके बारे में यहां पूछना चाहिए ....)

इस बिंदु पर, मैंने पृष्ठ को फिर से लोड किया और एक 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; 
} 

मैं tuples है, जहां प्रत्येक टपल प्रत्येक वेक्टर से इसी तत्व तोड़ से बनाया गया था का एक वेक्टर पैदा करेगा। फिर मैं प्रत्येक बार tuple और func पास करने से मूल्यांकन परिणामों का वेक्टर बनाउंगा।

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

पहली पंक्ति के पहले भाग समारोह का उपयोग करने देता है:

rearrange_vectors अग्रिम (डिफ़ॉल्ट-निर्माण) में मानों की तालिका बनाने के लिए और बाहर एक समय में प्रत्येक प्रविष्टि के एक उप-वस्तु को भरने है कॉपी-एंड-पेस्ट के बिना इसका अपना रिटर्न प्रकार। एकमात्र चेतावनी यह है कि आर-वैल्यू संदर्भ पैरामीटर std::forward (या move) से घिरा होना चाहिए ताकि रिकर्सिव कॉल का एल-वैल्यू ओवरलोड गलती से नहीं चुना जा सके। प्रत्येक ट्यूपल तत्व के भाग को म्यूट करने वाला फ़ंक्शन स्पष्ट रूप से वर्तमान इंडेक्स लेना होता है। सूचकांक पैरामीटर पैक छीलने के दौरान एक के बाद ऊपर ले जाता है:

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

तालिका के रूप में लंबे समय से कम से कम इनपुट वेक्टर के रूप में है, इसलिए हम तालिका ट्रिम करने के लिए जब भी वर्तमान इनपुट वेक्टर पहले समाप्त हो जाती है है। (काश मैं feconstfor ब्लॉक के भीतर const के रूप में चिह्नित कर सकता हूं।) मूल रूप से first और reststd::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 तर्क गिनती और संख्या इनपुट वैक्टर के सहमत हैं। अब मुझे लगता है कि मैं दोनों दूर सार संक्षेप द्वारा dueling समारोह-सूचक बनाम 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; 
} 

एक आर मूल्य संदर्भ के साथ एक समारोह पैरामीटर अंकन सार्वभौमिक गुजर तरीका है। यह सभी प्रकार के संदर्भों और const/volatile (सीवी) योग्यता को संभालता है। यही कारण है कि मैंने containers इसे स्विच किया। func में कोई संरचना हो सकती है; यह operator() के कई संस्करणों के साथ एक क्लास ऑब्जेक्ट भी हो सकता है। चूंकि मैं कंटेनर के लिए आर-वैल्यू का उपयोग कर रहा हूं, इसलिए वे तत्व डीरफ्रेंसिंग के लिए सर्वोत्तम सीवी-योग्यता का उपयोग करेंगे, और फ़ंक्शन ओवरलोड रिज़ॉल्यूशन के लिए इसका उपयोग कर सकता है। आंतरिक रूप से परिणाम प्रकार निर्धारित करने के लिए रिकर्सिव "कॉल" को std::forward का उपयोग करने के लिए किसी भी "डाउनग्रेड्स" को एल-मान संदर्भों को रोकने के लिए उपयोग करने की आवश्यकता है। यह इस पुनरावृत्ति में एक दोष भी प्रकट करता है: I वापसी प्रकार प्रदान करना चाहिए।

मैं इसे ठीक कर दूंगा, लेकिन पहले मैं एसटीएल मार्ग की व्याख्या करना चाहता हूं। आप किसी विशिष्ट कंटेनर प्रकार को पूर्व-निर्धारित नहीं करते हैं और उसे उपयोगकर्ता को वापस नहीं करते हैं। आप एक विशेष ऑब्जेक्ट, आउटपुट-इटरेटर के लिए पूछते हैं, जिससे आप परिणाम भेजते हैं। इटरेटर को एक कंटेनर से जोड़ा जा सकता है, जिसमें मानक कई किस्मों को प्रदान करता है। इसके परिणामस्वरूप सीधे आउटपुट स्ट्रीम से कनेक्ट किया जा सकता है, परिणाम सीधे प्रिंट कर सकते हैं! इटेटरेटर विधि मुझे स्मृति चिंताओं के बारे में सीधे चिंता करने से भी राहत देती है।

#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 कहा।