std::reduce

template< class InputIt >
typename std::iterator_traits<InputIt>::value_type
    reduce( InputIt first, InputIt last );

template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
    reduce( ExecutionPolicy&& policy,
            ForwardIt first, ForwardIt last );

template< class InputIt, class T >
T reduce( InputIt first, InputIt last, T init );

template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init );

template< class InputIt, class T, class BinaryOp >
T reduce( InputIt first, InputIt last, T init, BinaryOp op );

template< class ExecutionPolicy,
          class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init, BinaryOp op );

Gegeben binary_op als die tatsächliche binäre Operation:

• Das Ergebnis ist nicht deterministisch, wenn der binary_op nicht assoziativ oder nicht kommutativ ist (wie z. B. Gleitkommaaddition).

• Wenn einer der folgenden Werte nicht in T konvertierbar ist, ist das Programm fehlerhaft:

• 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:

• T ist nicht MoveConstructible.
• binary_op modifiziert ein Element von [first, last).
• binary_op macht einen Iterator oder Teilbereich von [first, last] ungültig.

Parameter

Rückgabewert

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:

1. Nimmt zwei beliebige Elemente elem1 und elem2 aus der Gruppe.
2. Berechnet binary_op ( elem1, elem2 ) und fügt das Ergebnis zurück in die Gruppe ein.
3. 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 ( first, last ) :

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

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.

Beispiel

#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 << "Summe: "
                  << result << '\t' << "Zeit: " << 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())}; });
    }
}

// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out
std::accumulate (double)    Summe: 10.000.000,7	Zeit: 356,9 ms
std::reduce (seq, double)   Summe: 10.000.000,7	Zeit: 140,1 ms
std::reduce (par, double)   Summe: 10.000.000,7	Zeit: 140,1 ms
std::accumulate (long)      Summe: 100.000.007	Zeit: 46,0 ms
std::reduce (seq, long)     Summe: 100.000.007	Zeit: 67,3 ms
std::reduce (par, long)     Summe: 100.000.007	Zeit: 63,3 ms
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    Summe: 10.000.000,7	Zeit: 353,4 ms
std::reduce (seq, double)   Summe: 10.000.000,7	Zeit: 140,7 ms
std::reduce (par, double)   Summe: 10.000.000,7	Zeit: 24,7 ms
std::accumulate (long)      Summe: 100.000.007	Zeit: 42,4 ms
std::reduce (seq, long)     Summe: 100.000.007	Zeit: 52,0 ms
std::reduce (par, long)     Summe: 100.000.007	Zeit: 23,1 ms

Siehe auch