C++ stl convolution

Question

Esiste una buona implementazione dell'algoritmo per calcolare la convoluzione di due intervalli in C++ STL (o addirittura boost)? cioè qualcosa con il prototipo (convoluzione di due gamme a..b e c..d):

template< class Iterator > 
void convolution(Iterator a, Iterator b, Iterator c, Iterator d); 

che possono modificare a..b gamma

Answer 1

Sì std :: trasformare

std::transform(a, b, c, a, Op); 

// a b is the the first input range 
// c is the start of the second range (which must be at least as large as (b-a) 
// 
// We then use a as the output iterator as well. 

// Op is a BinaryFunction 

Per rispondere il commento su come eseguire accumulo di stato nei commenti:

struct Operator 
{ 
    State& state; 
    Operator(Sate& state) : state(state) {} 
    Type operator()(TypeR1 const& r1Value, TypeR2 const& r2Value) const 
    { 
     Plop(state, r1Value, r2Value); 
     return Convolute(state, r2Value, r2Value); 
    } 
}; 
State theState = 0; 
Operator Op(theState); 

Answer 2

Non sono abbastanza sicuro di cosa debba essere una "convoluzione" da due sequenze a una di queste due sequenze: sembra essere una comprensione diversa dalla mia comprensione. Di seguito è una versione di convolution utilizzando un numero variabile di iteratori. Poiché in questo momento sono solo troppo pigro, userò una nozione un po 'rara di passare l'iteratore di destinazione come prima discussione piuttosto che come ultima argomentazione. Ecco un'implementazione di un corrispondente zip() algoritmi:

#include <tuple> 

namespace algo 
{ 
    template <typename... T> 
    void dummy(T...) 
    { 
    } 

    template <typename To, typename InIt, typename... It> 
    To zip(To to, InIt it, InIt end, It... its) 
    { 
     for (; it != end; ++it, ++to) { 
      *to = std::make_tuple(*it, *its...); 
      algo::dummy(++its...); 
     } 
     return to; 
    } 
}  

Ecco un semplice programma di test ho usato per verificare che il precedente non quello che intendevo fare:

#include <deque> 
#include <iostream> 
#include <iterator> 
#include <list> 
#include <vector> 

enum class e { a = 'a', b = 'b', c = 'c' }; 

std::ostream& operator<< (std::ostream& out, 
          std::tuple<int, double, e> const& v) 
{ 
    return out << "[" 
       << std::get<0>(v) << ", " 
       << std::get<1>(v) << ", " 
       << char(std::get<2>(v)) << "]"; 
} 

int main() 
{ 
    typedef std::tuple<int, double, e> tuple; 
    std::vector<int> v{ 1, 2, 3 }; 
    std::deque<double> d{ 1.1, 2.2, 3.3 }; 
    std::list<e>  l{ e::a, e::b, e::c }; 
    std::vector<tuple> r; 

    algo::zip(std::back_inserter(r), v.begin(), v.end(), d.begin(), l.begin()); 

    std::copy(r.begin(), r.end(), 
       std::ostream_iterator<tuple>(std::cout, "\n")); 
}