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 );

Dado binary_op como la operación binaria real:

• El resultado es no determinista si la binary_op no es asociativa o no es conmutativa (como la suma de punto flotante).

• Si alguno de los siguientes valores no es convertible a T, el programa está mal formado:

• binary_op(init, *first)
• binary_op(*first, init)
• binary_op(init, init)
• binary_op(*first, *first)

• Si se cumple alguna de las siguientes condiciones, el comportamiento es indefinido:

• T no es MoveConstructible.
• binary_op modifica cualquier elemento de [first, last).
• binary_op invalida cualquier iterador o subrango de [first, last].

Parámetros

Valor de retorno

La suma generalizada de un grupo de elementos sobre una operación binaria binary_op se define de la siguiente manera:

• Si el grupo solo tiene un elemento, la suma es el valor del elemento.
• De lo contrario, realiza las siguientes operaciones en orden:

1. Toma dos elementos cualesquiera elem1 y elem2 del grupo.
2. Calcula binary_op ( elem1, elem2 ) y coloca el resultado de vuelta en el grupo.
3. Repite los pasos 1 y 2 hasta que solo quede un elemento en el grupo.

Complejidad

Dado \(\scriptsize N\) N como std:: distance ( first, last ) :

Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy reportan errores de la siguiente manera:

• Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y ExecutionPolicy es uno de los standard policies , std::terminate es llamado. Para cualquier otro ExecutionPolicy , el comportamiento está definido por la implementación.
• Si el algoritmo falla al asignar memoria, std::bad_alloc es lanzado.

Notas

std::reduce se comporta como std::accumulate excepto que los elementos del rango pueden ser agrupados y reorganizados en orden arbitrario.

Ejemplo

#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 [nombre, resultado] = 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 << nombre << "suma: "
                  << resultado << '\t' << "tiempo: " << 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)    suma: 10,000,000.7	tiempo: 356.9 ms
std::reduce (seq, double)   suma: 10,000,000.7	tiempo: 140.1 ms
std::reduce (par, double)   suma: 10,000,000.7	tiempo: 140.1 ms
std::accumulate (long)      suma: 100,000,007	tiempo: 46.0 ms
std::reduce (seq, long)     suma: 100,000,007	tiempo: 67.3 ms
std::reduce (par, long)     suma: 100,000,007	tiempo: 63.3 ms
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    suma: 10,000,000.7	tiempo: 353.4 ms
std::reduce (seq, double)   suma: 10,000,000.7	tiempo: 140.7 ms
std::reduce (par, double)   suma: 10,000,000.7	tiempo: 24.7 ms
std::accumulate (long)      suma: 100,000,007	tiempo: 42.4 ms
std::reduce (seq, long)     suma: 100,000,007	tiempo: 52.0 ms
std::reduce (par, long)     suma: 100,000,007	tiempo: 23.1 ms

Véase también