C++ stl Faltung

Question

Gibt es eine schöne Implementierung des Algorithmus zur Berechnung der Faltung von zwei Bereichen in C++ STL (oder sogar Boost)? also etwas mit Prototyp (Faltung von zwei Bereichen a..b und c..d):

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

die a..b Bereich

Answer 1

Ja std :: modifiziert verwandeln

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 

den Kommentar auf beantworten, wie auszuführen Zustandsakkumulation in den Kommentaren:

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

Ich bin nicht ganz sicher, was eine "Faltung" von zwei Sequenzen zu einer dieser beiden Sequenzen sein soll: Es scheint ein anderes Verständnis als mein Verständnis zu sein. Unten ist eine Version von convolution mit einer variablen Anzahl von Iteratoren. Da ich im Moment einfach zu faul bin, verwende ich eine etwas ungewöhnliche Vorstellung davon, den Ziel-Iterator als erstes Argument und nicht als letztes Argument zu übergeben. Hier ist eine Implementierung eines entsprechenden zip() Algorithmen:

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

Es folgt ein einfaches Prüfprogramm ich, dass die oben zu verifizieren ist, was ich es vorhatte:

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