std:: transform_reduce

From cppreference.net

Definiert im Header `<numeric>`
template < class InputIt1, class InputIt2, class T > T transform_reduce ( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init ) ;	(1)	(seit C++17) (constexpr seit C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > T transform_reduce ( ExecutionPolicy && policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init ) ;	(2)	(seit C++17)
template < class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce ( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform ) ;	(3)	(seit C++17) (constexpr seit C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce ( ExecutionPolicy && policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform ) ;	(4)	(seit C++17)
template < class InputIt, class T, class BinaryOp, class UnaryOp > T transform_reduce ( InputIt first, InputIt last, T init, BinaryOp reduce, UnaryOp transform ) ;	(5)	(seit C++17) (constexpr seit C++20)
template < class ExecutionPolicy, class ForwardIt, class T, class BinaryOp, class UnaryOp > T transform_reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, T init, BinaryOp reduce, UnaryOp transform ) ;	(6)	(seit C++17)

1) Entspricht transform_reduce ( first1, last1, first2, init,
std:: plus <> ( ) , std:: multiplies <> ( ) ) , effektiv die parallelisierte Version des Standard- std::inner_product .

3) Wendet transform auf jedes Elementpaar aus den Bereichen

first1

last1

und dem Bereich von std:: distance ( first1, last1 ) Elementen beginnend bei first2 an und reduziert die Ergebnisse (möglicherweise umgeordnet und in nicht spezifizierter Weise aggregiert) zusammen mit dem Initialwert init über reduce .

Das Ergebnis ist nicht-deterministisch, wenn die reduce Operation weder assoziativ noch kommutativ ist (wie beispielsweise die Gleitkomma-Addition).

Falls einer der folgenden Werte nicht in

konvertierbar ist, ist das Programm fehlerhaft:

reduce ( init, init )
reduce ( init, transform ( * first1, * first2 ) )
reduce ( transform ( * first1, * first2 ) , init )
reduce ( transform ( * first1, * first2 ) , transform ( * first1, * first2 ) )

Gegeben last2 als den std:: distance ( first1, last1 ) ten nächsten Iterator von first2 , falls eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

T ist nicht MoveConstructible .
transform oder reduce modifiziert irgendein Element von [ first1 , last1 ) oder [ first2 , last2 ) .
transform oder reduce invalidiert irgendeinen Iterator oder Teilbereich von [ first1 , last1 ] oder [ first2 , last2 ] .

5) Wendet transform auf jedes Element im Bereich

first

last

an und reduziert die Ergebnisse (möglicherweise umgeordnet und in nicht spezifizierter Weise aggregiert) zusammen mit dem Initialwert init über reduce .

Das Ergebnis ist nicht-deterministisch, wenn die reduce -Operation nicht assoziativ oder nicht kommutativ ist (wie beispielsweise die Gleitkomma-Addition).

Falls einer der folgenden Werte nicht in

konvertierbar ist, ist das Programm fehlerhaft:

reduce ( init, init )
reduce ( init, transform ( * first ) )
reduce ( transform ( * first ) , init )
reduce ( transform ( * first ) , transform ( * first ) )

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

T ist nicht MoveConstructible .
transform oder reduce modifiziert irgendein Element von [ first , last ) .
transform oder reduce invalidiert irgendeinen Iterator oder Teilbereich von [ first , last ] .

2,4,6) Gleich wie (1,3,5) , aber ausgeführt gemäß policy .

Diese Überladungen nehmen nur dann an der Überladungsauflösung teil, wenn alle folgenden Bedingungen erfüllt sind:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> ist true .	(bis C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> ist true .	(seit C++20)

Inhaltsverzeichnis

Parameter

first1, last1	-	das Iteratorpaar, das den Bereich der Elemente definiert, die als linke Operanden von transform verwendet werden
first2	-	der Start des Bereichs von Elementen, die als rechte Operanden von transform verwendet werden
first, last	-	das Iteratorpaar, das den Bereich der Elemente definiert, die als Operanden von transform verwendet werden
init	-	der Anfangswert der generalisierten Summe
policy	-	die zu verwendende Ausführungsrichtlinie
reduce	-	binäres FunctionObject , das in nicht spezifizierter Reihenfolge auf die Ergebnisse von transform , die Ergebnisse anderer reduce und init angewendet wird.
transform	-	unäres oder binäres FunctionObject , das auf jedes Element des Eingabebereichs (bzw. der Eingabebereiche) angewendet wird. Der Rückgabetyp muss als Eingabe für reduce akzeptabel sein.
Typanforderungen
- `InputIt1, InputIt2, InputIt` müssen die Anforderungen von LegacyInputIterator erfüllen.
- `ForwardIt1, ForwardIt2, ForwardIt` müssen die Anforderungen von LegacyForwardIterator erfüllen.

Rückgabewert

1,2) Die generalisierte Summe von init und values über std:: plus <> ( ) , wobei values die durch std:: multiplies <> ( ) transformierten Werte sind, wobei jeder Wert aus einem Paar von Elementen der beiden Eingabebereiche transformiert wird.

3,4) Die verallgemeinerte Summe von init und values über reduce , wobei values die durch transform transformierten Werte sind, wobei jeder Wert aus einem Paar von Elementen der beiden Eingabebereiche transformiert wird.

5,6) Die generalisierte Summe von init und values über reduce , wobei values die durch transform transformierten Werte sind, wobei jeder Wert aus einem Element des Eingabebereichs transformiert wird.

Die verallgemeinerte Summe einer Gruppe von Elementen über eine binäre Operation binary_op ist wie folgt definiert:

Wenn die Gruppe nur ein Element hat, ist die Summe der Wert des Elements.
Andernfalls werden die folgenden Operationen in dieser Reihenfolge ausgeführt:

Nimmt zwei beliebige Elemente elem1 und elem2 aus der Gruppe.
Berechnet binary_op ( elem1, elem2 ) und fügt das Ergebnis zurück in die Gruppe ein.
Wiederholt die Schritte 1 und 2, bis nur noch ein Element in der Gruppe vorhanden ist.

Komplexität

Gegeben $\scriptsize N$ $N$ als std:: distance ( first1, last1 ) (oder std:: distance ( first, last ) für Überladungen (5,6) ):

1,2)

O(N)

Anwendungen von std:: plus <> ( ) und std:: multiplies <> ( ) entsprechend.

3-6)

O(N)

Anwendungen von reduce und transform jeweils.

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
Wenn der Algorithmus keinen Speicher allokieren kann, wird std::bad_alloc geworfen.

Hinweise

transform wird niemals auf init angewendet.

Wenn first == last oder first1 == last1 , wird init unverändert zurückgegeben.

Beispiel

transform_reduce kann verwendet werden, um std::inner_product zu parallelisieren. Einige Systeme benötigen möglicherweise zusätzliche Unterstützung, um die Vorteile der parallelen Ausführung zu nutzen. Zum Beispiel muss unter GNU/Linux die Intel TBB installiert sein und die - ltbb Option an den gcc/clang Compiler übergeben werden.

Code ausführen

#if PARALLEL
#include <execution>
#define PAR std::execution::par,
#else
#define PAR
#endif
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <locale>
#include <numeric>
#include <vector>
// to parallelize non-associate accumulative operation, you'd better choose
// transform_reduce instead of reduce; e.g., a + b * b != b + a * a
void print_sum_squared(long const num)
{
    std::cout.imbue(std::locale{"en_US.UTF8"});
    std::cout << "num = " << num << '\n';
    // create an immutable vector filled with pattern: 1,2,3,4, 1,2,3,4 ...
    const std::vector<long> v{[n = num * 4] {
        std::vector<long> v;
        v.reserve(n);
        std::generate_n(std::back_inserter(v), n,
            [i = 0]() mutable { return 1 + i++ % 4; });
        return v;
    }()};
    auto squared_sum = [](auto sum, auto val) { return sum + val * val; };
    auto sum1 = std::accumulate(v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "accumulate(): " << sum1 << '\n';
    auto sum2 = std::reduce(PAR v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "reduce(): " << sum2 << '\n';
    auto sum3 = std::transform_reduce(PAR v.cbegin(), v.cend(), 0L, std::plus{},
                                      [](auto val) { return val * val; });
    std::cout << "transform_reduce(): " << sum3 << "\n\n";
}
int main()
{
    print_sum_squared(1);
    print_sum_squared(1'000);
    print_sum_squared(1'000'000);
}

Mögliche Ausgabe:

num = 1
accumulate(): 30
reduce(): 30
transform_reduce(): 30
num = 1,000
accumulate(): 30,000
reduce(): -7,025,681,278,312,630,348
transform_reduce(): 30,000
num = 1,000,000
accumulate(): 30,000,000
reduce(): -5,314,886,882,370,003,032
transform_reduce(): 30,000,000
// Compile-options for parallel execution on POSIX:
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

Siehe auch

accumulate	summiert oder faltet eine Reihe von Elementen (Funktions-Template)
transform	wendet eine Funktion auf eine Reihe von Elementen an und speichert die Ergebnisse in einem Zielbereich (Funktions-Template)
reduce (C++17)	ähnlich wie std::accumulate , jedoch außerhalb der Reihenfolge (Funktions-Template)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants