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

Soit binary_op l'opération binaire effective :

• Le résultat est non déterministe si le binary_op n'est pas associatif ou n'est pas commutatif (comme l'addition en virgule flottante).

• Si l'une des valeurs suivantes n'est pas convertible en T, le programme est mal formé :

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

• Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

• T n'est pas MoveConstructible.
• binary_op modifie tout élément de [first, last).
• binary_op invalide tout itérateur ou sous-plage de [first, last].

Paramètres

Valeur de retour

La somme généralisée d'un groupe d'éléments sur une opération binaire binary_op est définie comme suit :

• Si le groupe ne contient qu'un seul élément, la somme est la valeur de cet élément.
• Sinon, effectue les opérations suivantes dans l'ordre :

1. Prend deux éléments quelconques elem1 et elem2 du groupe.
2. Calcule binary_op ( elem1, elem2 ) et replace le résultat dans le groupe.
3. Répète les étapes 1 et 2 jusqu'à ce qu'il ne reste qu'un seul élément dans le groupe.

Complexité

Étant donné \(\scriptsize N\) N comme std:: distance ( first, last ) :

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

• Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard , std::terminate est appelé. Pour tout autre ExecutionPolicy , le comportement est défini par l'implémentation.
• Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Notes

std::reduce se comporte comme std::accumulate sauf que les éléments de la plage peuvent être groupés et réorganisés dans un ordre arbitraire.

Exemple

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

Voir aussi