Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::transform_reduce

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      (C++17)
      transform_reduce
      (C++17)
      Operations on uninitialized memory
       
       
      Defined in header<numeric>
      template<class InputIt1,class InputIt2,class T>

      T transform_reduce( InputIt1 first1, InputIt1 last1,

                          InputIt2 first2, T init);
      		 (1)(since C++17)
      (constexpr since 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)(since 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)(since C++17)
      (constexpr since 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)(since 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)(since C++17)
      (constexpr since 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)(since C++17)
      1) Equivalent totransform_reduce(first1, last1, first2, init,
                       std::plus<>(),std::multiplies<>())      , effectively parallelized version of the defaultstd::inner_product.
      3) Appliestransform to each pair of elements from the ranges[first1, last1) and the range ofstd::distance(first1, last1) elements starting fromfirst2 and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial valueinit overreduce.
      The result is non-deterministic if thereduce is not associative or not commutative (such as floating-point addition).
      If any of the following values is not convertible toT, the program is ill-formed:
      • reduce(init, init)
      • reduce(init, transform(*first1,*first2))
      • reduce(transform(*first1,*first2), init)
      • reduce(transform(*first1,*first2), transform(*first1,*first2))
      Givenlast2 as thestd::distance(first1, last1)th next iterator offirst2, if any of the following conditions is satisfied, the behavior is undefined:
      • T is notMoveConstructible.
      • transform orreduce modifies any element of[first1, last1) or[first2, last2).
      • transform orreduce invalidates any iterator or subrange of[first1, last1] or[first2, last2].
      5) Appliestransform to each element in the range[first, last) and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial valueinit overreduce.
      The result is non-deterministic if thereduce is not associative or not commutative (such as floating-point addition).
      If any of the following values is not convertible toT, the program is ill-formed:
      • reduce(init, init)
      • reduce(init, transform(*first))
      • reduce(transform(*first), init)
      • reduce(transform(*first), transform(*first))
      If any of the following conditions is satisfied, the behavior is undefined:
      • T is notMoveConstructible.
      • transform orreduce modifies any element of[first, last).
      • transform orreduce invalidates any iterator or subrange of[first, last].
      2,4,6) Same as(1,3,5), but executed according topolicy.
      These overloads participate in overload resolution only if all following conditions are satisfied:

      std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue.

      		(until C++20)

      std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue.

      		(since C++20)

      Contents

      [edit]Parameters

      first1, last1 - the pair of iterators defining therange of elements to be taken as the left operand oftransform
      first2 - the start of range of elements to be taken as the right operand oftransform
      first, last - the pair of iterators defining therange of elements to be taken as the operand oftransform
      init - the initial value of the generalized sum
      policy - theexecution policy to use
      reduce - binaryFunctionObject that will be applied in unspecified order to the results oftransform, the results of otherreduce andinit.
      transform - unary or binaryFunctionObject that will be applied to each element of the input range(s). The return type must be acceptable as input toreduce.
      Type requirements
      -
      InputIt1, InputIt2, InputIt must meet the requirements ofLegacyInputIterator.
      -
      ForwardIt1, ForwardIt2, ForwardIt must meet the requirements ofLegacyForwardIterator.

      [edit]Return value

      1,2) The generalized sum ofinit andvalues overstd::plus<>(), wherevalues are the values transformed bystd::multiplies<>(), each value is transformed from a pair of elements from the two input ranges.
      3,4) The generalized sum ofinit andvalues overreduce, wherevalues are the values transformed bytransform, each value is transformed from a pair of elements from the two input ranges.
      5,6) The generalized sum ofinit andvalues overreduce, wherevalues are the values transformed bytransform, each value is transformed from an element from the input range.

      Thegeneralized sum of a group of elements over an binary operationbinary_op is defined as follows:

      • If the group only has one element, the sum is the value of the element.
      • Otherwise, performs the following operations in order:
      1. Takes any two elementselem1 andelem2 from the group.
      2. Calculatesbinary_op(elem1, elem2) and puts the result back to the group.
      3. Repeats steps 1 and 2 until there is only one element in the group.

      [edit]Complexity

      Given\(\scriptsize N\)N asstd::distance(first1, last1) (orstd::distance(first, last) for overloads(5,6)):

      1,2)\(\scriptsize O(N)\)O(N) applications ofstd::plus<>() andstd::multiplies<>() respectively.
      3-6)\(\scriptsize O(N)\)O(N) applications ofreduce andtransform respectively.

      [edit]Exceptions

      The overloads with a template parameter namedExecutionPolicy report errors as follows:

      • If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
      • If the algorithm fails to allocate memory,std::bad_alloc is thrown.

      [edit]Notes

      transform is never applied toinit.

      Iffirst== last orfirst1== last1,init is returned, unmodified.

      [edit]Example

      transform_reduce can be used to parallelizestd::inner_product. Some systems may need additional support to get advantages of parallel execution. E.g., on GNU/Linux, theIntel TBB be installed and-ltbb option be provided to gcc/clang compiler.

      Run this 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 * avoid print_sum_squared(longconst 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 ...conststd::vector<long> v{[n= num*4]{std::vector<long> v;        v.reserve(n);std::generate_n(std::back_inserter(v), n,[i=0]() mutable{return1+ 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);}

      Possible output:

      num = 1accumulate(): 30reduce(): 30transform_reduce(): 30 num = 1,000accumulate(): 30,000reduce(): -7,025,681,278,312,630,348transform_reduce(): 30,000 num = 1,000,000accumulate(): 30,000,000reduce(): -5,314,886,882,370,003,032transform_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

      [edit]See also

      sums up or folds a range of elements
      (function template)[edit]
      applies a function to a range of elements, storing results in a destination range
      (function template)[edit]
      (C++17)
      		 similar tostd::accumulate, except out of order
      (function template)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/transform_reduce&oldid=180311"
      [8]ページ先頭
      ©2009-2025 Movatter.jp