std::transform_reduce
Von cppreference.com
| Definiert in der Header-Datei <numeric> |
||
| template< class InputIt1, class InputIt2, class T > T transform_reduce( InputIt1 first1, InputIt1 last1, |
(1) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > |
(2) | (seit C++17) |
| template< class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2 > |
(3) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, |
(4) | (seit C++17) |
| template< class InputIt, class T, class BinaryOp, class UnaryOp > |
(5) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt, class T, |
(6) | (seit C++17) |
1) Entspricht transform_reduce(first1, last1, first2, init,
std::plus<>(), std::multiplies<>()), eine parallelisierte Version von std::inner_product.
std::plus<>(), std::multiplies<>()), eine parallelisierte Version von std::inner_product.
3) Wendet transform auf jedes Elementpaar der Bereiche
[first1, last1) und den Bereich von std::distance(first1, last1) Elementen ab first2 an und reduziert die Ergebnisse (möglicherweise permutiert und aggregiert auf nicht spezifizierte Weise) zusammen mit dem Anfangswert init mittels reduce. Das Ergebnis ist nicht deterministisch, wenn reduce nicht assoziativ oder nicht kommutativ ist (z. B. Gleitkommaaddition).
Wenn einer der folgenden Werte nicht in
T konvertierbar ist, ist das Programm ill-formed- reduce(init, init)
- reduce(init, transform(*first1, *first2))
- reduce(transform(*first1, *first2), init)
- reduce(transform(*first1, *first2), transform(*first1, *first2))
Wenn last2 als der std::distance(first1, last1)te nächste Iterator von first2 gesetzt ist und eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
-
Tist nicht MoveConstructible. - transform oder reduce modifiziert ein Element von
[first1,last1)oder[first2,last2). - transform oder reduce macht einen Iterator oder Teilbereich von
[first1,last1]oder[first2,last2]ungültig.
5) Wendet transform auf jedes Element im Bereich
[first, last) an und reduziert die Ergebnisse (möglicherweise permutiert und aggregiert auf nicht spezifizierte Weise) zusammen mit dem Anfangswert init mittels reduce. Das Ergebnis ist nicht deterministisch, wenn reduce nicht assoziativ oder nicht kommutativ ist (z. B. Gleitkommaaddition).
Wenn einer der folgenden Werte nicht in
T konvertierbar ist, ist das Programm ill-formed- 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
-
Tist nicht MoveConstructible. - transform oder reduce modifiziert ein Element von
[first,last). - transform oder reduce macht einen Iterator oder Teilbereich von
[first,last]ungültig.
2,4,6) Dasselbe wie (1,3,5), aber gemäß policy ausgeführt.
Diese Überladungen nehmen an der Auflösungsauflösung teil, nur 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) |
Inhalt |
[edit] Parameter
| first1, last1 | - | das Iterator-Paar, das den Bereich der Elemente definiert, die als linkes Operand von transform verwendet werden |
| first2 | - | der Start des Bereichs der Elemente, die als rechter Operand von transform verwendet werden |
| first, last | - | das Iterator-Paar, das den Bereich der Elemente definiert, die als Operand von transform verwendet werden |
| init | - | der Anfangswert der generalisierten Summe |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| reduce | - | binäre Funktionsobjekt, das in nicht spezifizierter Reihenfolge auf die Ergebnisse von transform, die Ergebnisse anderer reduce und init angewendet wird. |
| transform | - | unäres oder binäres Funktionsobjekt, das auf jedes Element des/der Eingabebereiche(s) 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. | ||
[edit] Rückgabewert
1,2) Die verallgemeinerte 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 aus den beiden Eingabebereichen 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 aus den beiden Eingabebereichen transformiert wird.
5,6) Die verallgemeinerte 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 enthält, ist die Summe der Wert des Elements.
- Andernfalls werden die folgenden Operationen der Reihe nach ausgeführt
- Nimmt zwei beliebige Elemente elem1 und elem2 aus der Gruppe.
- Berechnet binary_op(elem1, elem2) und legt das Ergebnis zurück in die Gruppe.
- Wiederholt die Schritte 1 und 2, bis nur noch ein Element in der Gruppe vorhanden ist.
[edit] Komplexität
Gegeben N als std::distance(first1, last1) (oder std::distance(first, last) für Überladungen (5,6))
3-6) O(N) Anwendungen von reduce und transform.
[edit] Ausnahmen
Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten Fehler wie folgt
- Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und
ExecutionPolicyeine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andereExecutionPolicyist das Verhalten implementierungsabhängig. - Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.
[edit] Anmerkungen
transform wird nie auf init angewendet.
Wenn first == last oder first1 == last1, wird init unverändert zurückgegeben.
[edit] 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. Z. B. unter GNU/Linux muss die Intel TBB installiert sein und die Option -ltbb muss für den gcc/clang-Compiler angegeben werden.
Führen Sie diesen Code aus
#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
[edit] Siehe auch
| summiert oder faltet eine Reihe von Elementen (Funktionstemplate) | |
| Wendet eine Funktion auf einen Elementbereich an und speichert die Ergebnisse in einem Zielbereich (Funktionstempelat) | |
| (C++17) |
ähnlich wie std::accumulate, aber nicht-sequenziell (Funktionstemplate) |
