Is it possible to write a generic zipWith variable in C ++?

Question

I need a generic zipWith function in the C ++ variable arity. I have two problems. Firstly, I cannot determine the type of function pointer passed to zipWith. It must be the same as the number of vectors passed to zipWith, and it must accept references to types of vector elements, respectively. Secondly, I don’t know how to navigate these vectors in parallel in order to build a list of arguments, call func (), and pledge after exhausting the shortest 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

I had a long answer, then I changed my mind so that the solution was much shorter. But I'm going to show my thought process and give you both answers!

My first step is to determine the correct signature. I don’t understand all this, but you can consider the package of parameters as a list of actual elements, separated by commas, with a hidden text dump. You can expand the list on both sides with more separated commas! Therefore, the direct application of this:

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

You must put "..." after the parameter package for the expression section to see the extended list. You should also put it in the regular parameters part:

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

You said that your function parameters are a bunch of vectors. Here you are hoping that each of Vargs indeed std::vector . Type conversions can be applied to the parameter package, so why don’t we make sure that you have vectors:

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

Vectors can be huge objects, so use const l-value links. Alternatively, we could use std::function so that we can use lambda or std::bind expressions:

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

(I ran into problems here using std::pow for testing. My compiler did not accept the classic function pointer converted to an std::function object. So I had to wrap it in lambda. Maybe I should ask about this .. ..)

At this point, I reloaded the page and saw one answer (by pmr) . I really do not understand this clasp, folding, bang, anything, so I thought his decision was too complicated. So I thought of a more direct solution:

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

I would create a vector of tuples, where each tuple was made from plucking the corresponding elements from each vector. Then I will create a vector of evaluation results from passing the tuple and func each time.

rearrange_vectors should make a table of values ​​in advance (built by default) and fill each record with a sub-object at a time:

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

The first part of the first line allows the function to access its own return type without copying and pasting. The only caveat is that the r-value reference parameters should be surrounded by std::forward (or move ), so the overload error of the recursive call l will not be selected by mistake. A function that mutates part of each tuple element must explicitly accept the current index. When moving the package of parameters, the index increases by one:

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

The table is the shortest input vector, so we must crop the table whenever the current input vector ends first. (I would like to mark fe as const in the for block.) I initially had first and rest as std::vector , but I realized that I could abstract this; all i need is the types corresponding to the standard (sequential) containers in the iterative interface. But now I am puzzled by evaluate :

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

I can do individual cases:

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

but I cannot generalize it to a recursive case. IIUC, std::tuple does not support peeling of the tail (and / or head) as a tuple. In addition, std::bind supports currying arguments in functions in parts, and its substitution system is incompatible with packages of parameters of arbitrary length. I would just like to specify each parameter as I could if I had access to the original input vectors ....

... Wait, why not do it only ?! ...

... Well, I never heard of that. I saw how to transfer a package of template parameters to function parameters; I just showed it in zipWith . Can I do this from a list of function parameters in internal functions? (As I write, now I remember that I saw this in terms of initializing the element of class constructors, for non-static members that are arrays or types of classes.) There is only one way to find out:

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

where I am forced to pre-calculate the total number of calls:

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

and of course it worked! Of course, this meant that I thought too much about the problem as badly as the other respondent (in a different way). It also means that I missed you too much with most of this post. When I wrapped this up, I realized that replacing std::vector with generic container types can be applied to zip_width . And I realized that I can reduce the required one vector without the required vectors:

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

I added static_assert when I copied the code here, since I forgot to make sure that the argument counter func and the number of input vectors are consistent. Now I understand that I can fix the dueling function-pointer object vs. std::function , abstracting both:

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

Marking a function parameter with a r-value reference is a universal method of transmission. It handles all kinds of links and const / volatile (cv) qualifications. That is why I switched containers to it. func can have any structure; it may even be an object of a class with multiple versions of operator () . Since I use r-values ​​for containers, they will use the best cv qualification for dereferencing elements, and the function can use this to resolve overloading. A recursive "call" to internally determine the type of result should use std::forward to prevent "downgrading" to references to an l-value. It also shows the drawback of this iteration: I must provide a return type.

I will fix this, but first I want to explain the STL path. You do not predefine a specific container type and return it to the user. You request a special object - iterator output, to which you send the results. An iterator can be connected to a container, the standard of which provides several options. Instead, it can be connected to the output stream, directly printing the results! The iterator method also relieves me of immediate concern about memory issues.

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

I copied minimum_common_size here, but explicitly mentioned the result type for the least based case, checking out different types of containers using different types of sizes.

Functions that accept iterator output usually return an iterator after all iterators have completed. This allows you to start a new exit (even with a different output function) where you left off. This is not critical for standard output iterators, since they are all pseudo-iterators. This is important when using the forward iterator (or higher) as the output iterator, since they make the track position. (Using the advanced iterator as the output is safe if the maximum number of transfers does not exceed the remaining iterative space.) Some functions put the output iterator at the end of the parameter list, others at the beginning; zip_width should use the latter, since parameter packets should go at the end.

Moving to the suffix return type in zipWith makes every part of the function sign fair play when evaluating the return type expression. It also lets me know right away whether it is impossible to compute due to incompatibility at compile time. The std::back_inserter returns a special output iterator to a vector that adds elements through the push_back member function.

Answer 2

Here is what I put together:

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

This is a slightly improved version compared to previous versions. Since every good program should begin with a definition of left addition.

It still does not solve the problem of iterators packed in pairs.

In terms of stdlib, this function will be called transform and will require that only the length of one sequence be given, and the others, at least for so long. I named it transformV here to avoid the names.