std:: transform_reduce

From cppreference.net

Défini dans l'en-tête `<numeric>`
template < class InputIt1, class InputIt2, class T > T transform_reduce ( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init ) ;	(1)	(depuis C++17) (constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > T transform_reduce ( ExecutionPolicy && policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init ) ;	(2)	(depuis C++17)
template < class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce ( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform ) ;	(3)	(depuis C++17) (constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2 > T transform_reduce ( ExecutionPolicy && policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init, BinaryOp1 reduce, BinaryOp2 transform ) ;	(4)	(depuis C++17)
template < class InputIt, class T, class BinaryOp, class UnaryOp > T transform_reduce ( InputIt first, InputIt last, T init, BinaryOp reduce, UnaryOp transform ) ;	(5)	(depuis C++17) (constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt, class T, class BinaryOp, class UnaryOp > T transform_reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, T init, BinaryOp reduce, UnaryOp transform ) ;	(6)	(depuis C++17)

1) Équivalent à transform_reduce ( first1, last1, first2, init,
std:: plus <> ( ) , std:: multiplies <> ( ) ) , version parallélisée effective de la std::inner_product par défaut.

3) Applique transform à chaque paire d'éléments des plages

first1

last1

et de la plage de std:: distance ( first1, last1 ) éléments commençant à first2 et réduit les résultats (éventuellement permutés et agrégés de manière non spécifiée) avec la valeur initiale init via reduce .

Le résultat est non déterministe si la reduce n'est ni associative ni commutative (comme l'addition en virgule flottante).

Si l'une des valeurs suivantes n'est pas convertible en

, le programme est mal formé :

reduce ( init, init )
reduce ( init, transform ( * first1, * first2 ) )
reduce ( transform ( * first1, * first2 ) , init )
reduce ( transform ( * first1, * first2 ) , transform ( * first1, * first2 ) )

Étant donné last2 comme le std:: distance ( first1, last1 ) ième itérateur suivant de first2 , si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

T n'est pas MoveConstructible .
transform ou reduce modifie un élément quelconque de [ first1 , last1 ) ou de [ first2 , last2 ) .
transform ou reduce invalide un itérateur ou un sous-intervalle quelconque de [ first1 , last1 ] ou de [ first2 , last2 ] .

5) Applique transform à chaque élément dans l'intervalle

first

last

et réduit les résultats (éventuellement permutés et agrégés de manière non spécifiée) avec la valeur initiale init via reduce .

Le résultat est non déterministe si la reduce n'est pas associative ou non commutative (comme l'addition en virgule flottante).

Si l'une des valeurs suivantes n'est pas convertible vers

, le programme est mal formé :

reduce ( init, init )
reduce ( init, transform ( * first ) )
reduce ( transform ( * first ) , init )
reduce ( transform ( * first ) , transform ( * first ) )

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

T n'est pas MoveConstructible .
transform ou reduce modifie un élément quelconque de [ first , last ) .
transform ou reduce invalide un itérateur ou un sous-intervalle quelconque de [ first , last ] .

2,4,6) Identique à (1,3,5) , mais exécuté selon la policy .

Ces surcharges participent à la résolution de surcharge seulement si toutes les conditions suivantes sont satisfaites :

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> est true .	(jusqu'à C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> est true .	(depuis C++20)

Table des matières

Paramètres

first1, last1	-	la paire d'itérateurs définissant l'intervalle des éléments à prendre comme opérande gauche de transform
first2	-	le début de l'intervalle des éléments à prendre comme opérande droit de transform
first, last	-	la paire d'itérateurs définissant l'intervalle des éléments à prendre comme opérande de transform
init	-	la valeur initiale de la somme généralisée
policy	-	la politique d'exécution à utiliser
reduce	-	le FunctionObject binaire qui sera appliqué dans un ordre non spécifié aux résultats de transform , aux résultats d'autres reduce et à init .
transform	-	le FunctionObject unaire ou binaire qui sera appliqué à chaque élément du/des intervalle(s) d'entrée. Le type de retour doit être acceptable en entrée de reduce .
Exigences de type
- `InputIt1, InputIt2, InputIt` doivent satisfaire aux exigences de LegacyInputIterator .
- `ForwardIt1, ForwardIt2, ForwardIt` doivent satisfaire aux exigences de LegacyForwardIterator .

Valeur de retour

1,2) La somme généralisée de init et values sur std:: plus <> ( ) , où values sont les valeurs transformées par std:: multiplies <> ( ) , chaque valeur étant transformée à partir d'une paire d'éléments des deux plages d'entrée.

3,4) La somme généralisée de init et values sur reduce , où values sont les valeurs transformées par transform , chaque valeur étant transformée à partir d'une paire d'éléments des deux plages d'entrée.

5,6) La somme généralisée de init et values sur reduce , où values sont les valeurs transformées par transform , chaque valeur étant transformée à partir d'un élément de la plage d'entrée.

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 :

Prend deux éléments quelconques elem1 et elem2 du groupe.
Calcule binary_op ( elem1, elem2 ) et replace le résultat dans le groupe.
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 ( first1, last1 ) (ou std:: distance ( first, last ) pour les surcharges (5,6) ):

1,2)

O(N)

applications de std:: plus <> ( ) et std:: multiplies <> ( ) respectivement.

3-6)

O(N)

applications de reduce et transform respectivement.

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ée. 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ée.

Notes

transform n'est jamais appliqué à init .

Si first == last ou first1 == last1 , init est retourné, non modifié.

Exemple

transform_reduce peut être utilisé pour paralléliser std::inner_product . Certains systèmes peuvent nécessiter un support supplémentaire pour tirer parti de l'exécution parallèle. Par exemple, sur GNU/Linux, Intel TBB doit être installé et l'option - ltbb doit être fournie au compilateur gcc/clang.

Exécuter ce code

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

Sortie possible :

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

Voir aussi

accumulate	additionne ou plie une plage d'éléments (modèle de fonction)
transform	applique une fonction à une plage d'éléments, stockant les résultats dans une plage de destination (modèle de fonction)
reduce (C++17)	similaire à std::accumulate , mais sans ordre (modèle de fonction)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants