std::reduce
Von cppreference.com
| Definiert in der Header-Datei <numeric> |
||
| template< class InputIt > typename std::iterator_traits<InputIt>::value_type |
(1) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt > typename std::iterator_traits<ForwardIt>::value_type |
(2) | (seit C++17) |
| template< class InputIt, class T > T reduce( InputIt first, InputIt last, T init ); |
(3) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt, class T > T reduce( ExecutionPolicy&& policy, |
(4) | (seit C++17) |
| template< class InputIt, class T, class BinaryOp > T reduce( InputIt first, InputIt last, T init, BinaryOp op ); |
(5) | (seit C++17) (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp > |
(6) | (seit C++17) |
1) Entspricht reduce(first, last, typename std::iterator_traits<InputIt>::value_type{}).
3) Entspricht reduce(first, last, init, std::plus<>()).
5) Reduziert den Bereich
[first, last), möglicherweise permutiert und aggregiert auf nicht spezifizierte Weise, zusammen mit dem Anfangswert init über op.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) |
Gegeben binary_op als die tatsächliche binäre Operation
- Das Ergebnis ist nicht deterministisch, wenn binary_op nicht assoziativ oder nicht kommutativ ist (wie z. B. Gleitkomma-Addition).
- Wenn einer der folgenden Werte nicht in
Tkonvertierbar ist, ist das Programm schlecht geformt
- binary_op(init, *first)
- binary_op(*first, init)
- binary_op(init, init)
- binary_op(*first, *first)
- Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert
-
Tist nicht MoveConstructible. - binary_op modifiziert kein Element von
[first,last). - binary_op macht keinen Iterator oder Teilbereich von
[first,last]ungültig.
-
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Iteratorenpaar, das den Bereich der Elemente definiert, auf die der Algorithmus angewendet werden soll |
| init | - | der Anfangswert der generalisierten Summe |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| op | - | binäres FunctionObject, das in nicht spezifizierter Reihenfolge auf das Ergebnis der Dereferenzierung der Eingabeiteratoren, die Ergebnisse anderer op und init angewendet wird. |
| Typanforderungen | ||
-InputIt muss die Anforderungen von LegacyInputIterator erfüllen. | ||
-ForwardIt muss die Anforderungen von LegacyForwardIterator erfüllen. | ||
[bearbeiten] Rückgabewert
5,6) Die generalisierte Summe von init und den Elementen von
[first, last) über op.Die *generalisierte 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 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 ist.
[bearbeiten] Komplexität
Gegeben N als std::distance(first, last)
5,6) O(N) Anwendungen von op.
[bearbeiten] 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.
[bearbeiten] Hinweise
std::reduce verhält sich wie std::accumulate, außer dass die Elemente des Bereichs in beliebiger Reihenfolge gruppiert und neu angeordnet werden können.
[bearbeiten] Beispiel
Seitenvergleich zwischen std::reduce und std::accumulate
Führen Sie diesen Code aus
#if PARALLEL #include <execution> #define SEQ std::execution::seq, #define PAR std::execution::par, #else #define SEQ #define PAR #endif #include <chrono> #include <iomanip> #include <iostream> #include <locale> #include <numeric> #include <utility> #include <vector> int main() { std::cout.imbue(std::locale("en_US.UTF-8")); std::cout << std::fixed << std::setprecision(1); auto eval = [](auto fun) { const auto t1 = std::chrono::high_resolution_clock::now(); const auto [name, result] = fun(); const auto t2 = std::chrono::high_resolution_clock::now(); const std::chrono::duration<double, std::milli> ms = t2 - t1; std::cout << std::setw(28) << std::left << name << "sum: " << result << '\t' << "time: " << ms.count() << " ms\n"; }; { const std::vector<double> v(100'000'007, 0.1); eval([&v]{ return std::pair{"std::accumulate (double)", std::accumulate(v.cbegin(), v.cend(), 0.0)}; }); eval([&v]{ return std::pair{"std::reduce (seq, double)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair{"std::reduce (par, double)", std::reduce(PAR v.cbegin(), v.cend())}; }); } { const std::vector<long> v(100'000'007, 1); eval([&v]{ return std::pair{"std::accumulate (long)", std::accumulate(v.cbegin(), v.cend(), 0l)}; }); eval([&v]{ return std::pair{"std::reduce (seq, long)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair{"std::reduce (par, long)", std::reduce(PAR v.cbegin(), v.cend())}; }); } }
Mögliche Ausgabe
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out std::accumulate (double) sum: 10,000,000.7 time: 356.9 ms std::reduce (seq, double) sum: 10,000,000.7 time: 140.1 ms std::reduce (par, double) sum: 10,000,000.7 time: 140.1 ms std::accumulate (long) sum: 100,000,007 time: 46.0 ms std::reduce (seq, long) sum: 100,000,007 time: 67.3 ms std::reduce (par, long) sum: 100,000,007 time: 63.3 ms // POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out std::accumulate (double) sum: 10,000,000.7 time: 353.4 ms std::reduce (seq, double) sum: 10,000,000.7 time: 140.7 ms std::reduce (par, double) sum: 10,000,000.7 time: 24.7 ms std::accumulate (long) sum: 100,000,007 time: 42.4 ms std::reduce (seq, long) sum: 100,000,007 time: 52.0 ms std::reduce (par, long) sum: 100,000,007 time: 23.1 ms
[bearbeiten] 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) |
wendet eine aufrufbare Funktion an und reduziert dann nicht-sequenziell (Funktionstemplate) |
| (C++23) |
Faltet einen Elementbereich von links (Algorithmus-Funktionsobjekt) |
