È possibile scrivere un generico varia zip zip in C++?

Question

Voglio una funzione generica zipWith in C++ di variabile arity. Ho due problemi. Il primo è che non riesco a determinare il tipo di puntatore della funzione passato a zipWith. Deve essere dello stesso tipo del numero di vettori passati a zipWith e deve accettare rispettivamente i riferimenti ai tipi di elementi dei vettori. Il secondo è che non ho idea di come camminare questi vettori in parallelo per costruire un elenco di argomenti, chiamare func() e rilasciare una volta che il vettore più breve è esaurito.

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

Answer 1

Ho avuto una risposta lunga, poi ho cambiato idea in un modo che ha reso la soluzione molto più breve. Ma mostrerò il mio processo mentale e ti darò entrambe le risposte!

Il mio primo passo è determinare la firma appropriata. Non capisco tutto, ma puoi trattare un pacchetto di parametri come un elenco separato da virgole degli oggetti reali con il dump di testo nascosto. Puoi estendere l'elenco su entrambi i lati di più elementi separati da virgola! Così direttamente l'applicazione che:

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

si deve mettere un "..." dopo un parametro pack per una sezione di espressione per visualizzare l'elenco espanso. Devi metterne uno anche nella parte regolare dei parametri:

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

Hai detto che i tuoi parametri di funzione sono un mucchio di vettori. Qui, speriamo che ciascuno di Vargs sia davvero un std::vector. Digitare le trasformazioni possono essere applicate a un pacchetto di parametri, quindi perché non assicurarsi di avere vettori:

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

vettori possono essere oggetti enormi, quindi cerchiamo di usare const riferimenti l-valore. Inoltre, potremmo usare std::function modo che possiamo utilizzare lambda o std::bind espressioni:.

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

(Mi sono imbattuto in problemi qui da utilizzare per i test std::pow mio compilatore non avrebbe accettato un puntatore a funzione classica di essere convertito in un oggetto std::function Quindi dovevo avvolgerlo in un lambda, forse dovrei chiedere qui ...)

A questo punto, ho ricaricato la pagina e ne ho visto uno response (by pmr). Non capisco davvero questo zippare, piegare, esplodere, qualsiasi cosa, quindi ho pensato che la sua soluzione fosse troppo complicata.Così ho pensato a una soluzione più diretta:

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

vorrei creare un vettore di tuple, dove ogni tupla è stato fatto da spennare elementi corrispondenti da ogni vettore. Quindi creerei un vettore di risultati di valutazione passando una tupla e func ogni volta.

La rearrange_vectors deve fare tabella di valori di anticipo (default-costruito) e riempire ogni voce un sotto-oggetto alla volta:

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

La prima parte della prima linea permette l'accesso alla funzione il proprio tipo di ritorno senza copia e incolla. L'unica avvertenza è che i parametri di riferimento del valore r devono essere circondati da std::forward (o move) in modo che un sovraccarico di valore l della chiamata ricorsiva non venga scelto per errore. La funzione che modifica la parte di ciascun elemento di tupla deve prendere esplicitamente l'indice corrente. L'indice sposta da uno durante parametro pacchetto peeling:

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

il tavolo è lungo come il più corto vettore di ingresso, quindi dobbiamo tagliare la tavola quando la corrente di vettore di ingresso termina prima. (Vorrei poter contrassegnare fe come const nel blocco for.) Originariamente avevo first e rest come std::vector, ma mi sono reso conto che avrei potuto estrarlo; tutto ciò di cui ho bisogno sono tipi che corrispondono ai contenitori standard (sequenza) nell'interfaccia di iterazione. Ma ora sto perplesso sul evaluate:

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

posso fare i singoli casi:

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

ma non posso generalizzare per un caso ricorsivo. IIUC, std::tuple non supporta il distacco della coda (e/o della testa) come una sotto-tupla. Lo standard std::bind non supporta gli argomenti di curring in una funzione in modo frammentario e il relativo sistema segnaposto non è compatibile con i pacchetti di parametri a lunghezza arbitraria. Vorrei poter solo elencare ogni parametro, come ho potuto, se ho avuto accesso ai vettori di input originali ....

... Aspetta, perché non ho fare proprio questo?! ...

... Beh, non ne ho mai sentito parlare. Ho visto il trasferimento di un pacchetto di parametri template ai parametri della funzione; L'ho appena mostrato in zipWith. Posso farlo dall'elenco dei parametri delle funzioni agli interni della funzione? (Mentre sto scrivendo, ora mi ricordo di aver visto nella parte membro-inizializzazione costruttori della classe, per i membri non statici che sono array o tipi di classe.) C'è solo un modo per scoprirlo:

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

dove Sono costretto a calcolare in anticipo il numero totale di chiamate:

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

e, sicuramente, ha funzionato! Naturalmente, questo significava che pensavo troppo al problema quanto l'altro rispondente (in un modo diverso). Significa anche che ti ho inutilmente annoiato con la maggior parte di questo post. Come ho concluso, mi sono reso conto che la sostituzione di std::vector con tipi generici di contenitori di sequenza può essere applicata in zip_width.E mi sono reso conto che avrei potuto ridurre il obbligatoria un vettore a nessun vettori obbligatorie:

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

ho aggiunto il static_assert come ho copiato il codice qui, dal momento che ho dimenticato di fare in modo che numero di argomenti 's il func e il numero dei vettori di input sono d'accordo. Ora mi rendo conto che posso risolvere la funzione puntatore vs. std::function oggetto duello astraendo sia lontano:

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

Marcatura un parametro di funzione con un riferimento r-value è il metodo di passaggio universale. Gestisce tutti i tipi di riferimenti e le qualifiche const/volatile (cv). Ecco perché ho cambiato lo containers. Il func potrebbe avere qualsiasi struttura; può anche essere un oggetto di classe con più versioni di operator(). Dal momento che sto usando i valori r per i contenitori, useranno la migliore qualifica di cv per la dereferenziazione degli elementi, e la funzione può usare quella per la risoluzione di sovraccarico. La "chiamata" ricorsiva per determinare internamente il tipo di risultato deve utilizzare std::forward per impedire qualsiasi "downgrade" ai riferimenti di valore l. Rivela anche un difetto in questa iterazione: I deve fornire il tipo di ritorno.

Lo aggiusterò, ma prima voglio spiegare il modo STL. Non si predeterminano uno specifico tipo di contenitore e lo si restituisce all'utente. Chiedi un oggetto speciale, un iteratore di output, a cui invii i risultati. L'iteratore potrebbe essere collegato a un contenitore, di cui lo standard fornisce diverse varietà. Potrebbe invece essere collegato a un flusso di output, stampando direttamente i risultati! Il metodo iteratore mi libera anche dal preoccuparmi direttamente dei problemi di memoria.

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

ho copiato minimum_common_size qui, ma esplicitamente menzionati il ​​tipo di risultato per il caso meno di base, impermeabilità alle diverse tipologie di contenitori utilizzando tipi differenti di formato.

Le funzioni che utilizzano un iteratore di uscita in genere restituiscono l'iteratore al termine di tutti gli iteratori. Ciò ti consente di avviare una nuova uscita in uscita (anche con una funzione di output diversa) da cui hai interrotto. Non è fondamentale per gli iteratori di output standard, dal momento che sono tutti pseudo-iteratori. È importante quando si utilizza un iteratore di inoltro (o superiore) come un iteratore di uscita poiché la posizione di traccia è . (L'uso di un iteratore in avanti come output è sicuro fino a quando il numero massimo di trasferimenti non supera lo spazio di iterazione rimanente.) Alcune funzioni posizionano l'iteratore di output alla fine dell'elenco dei parametri, altri all'inizio; zip_width deve utilizzare quest'ultimo poiché i pacchetti di parametri devono andare alla fine.

Il passaggio a un suffisso di tipo restituito in zipWith rende ogni parte del fair game della firma della funzione quando viene calcolata l'espressione del tipo restituito. Mi consente anche di sapere subito se il calcolo non può essere eseguito a causa di incompatibilità in fase di compilazione. La funzione std::back_inserter restituisce uno speciale output-iterator al vettore che aggiunge elementi tramite la funzione membro push_back.

Answer 2

Ecco quello che ho messo insieme:

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

Questo è un po 'migliorata variante rispetto alle versioni precedenti. Come ogni buon programma , inizia definendo un left-fold.

Ancora non risolve il problema degli iteratori imballati a coppie.

In termini stdlib questa funzione sarebbe chiamato transform e sarebbe richiedono che solo la lunghezza di una sequenza è specificato e gli altri essere almeno altrettanto lungo. L'ho chiamato transformV qui per evitare scontri di nomi .