Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::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
      Operations on uninitialized memory
       
       
      Defined in header<numeric>
      template<class InputIt>

      typenamestd::iterator_traits<InputIt>::value_type

          reduce( InputIt first, InputIt last);
      		 (1)(since C++17)
      (constexpr since C++20)
      template<class ExecutionPolicy,class ForwardIt>

      typenamestd::iterator_traits<ForwardIt>::value_type
          reduce( ExecutionPolicy&& policy,

                  ForwardIt first, ForwardIt last);
      		 (2)(since C++17)
      template<class InputIt,class T>
      T reduce( InputIt first, InputIt last, T init);
      		 (3)(since C++17)
      (constexpr since C++20)
      template<class ExecutionPolicy,class ForwardIt,class T>

      T reduce( ExecutionPolicy&& policy,

                ForwardIt first, ForwardIt last, T init);
      		 (4)(since C++17)
      template<class InputIt,class T,class BinaryOp>
      T reduce( InputIt first, InputIt last, T init, BinaryOp op);
      		 (5)(since C++17)
      (constexpr since C++20)
      template<class ExecutionPolicy,

               class ForwardIt,class T,class BinaryOp>
      T reduce( ExecutionPolicy&& policy,

                ForwardIt first, ForwardIt last, T init, BinaryOp op);
      		 (6)(since C++17)
      1) Equivalent toreduce(first, last,typenamestd::iterator_traits<InputIt>::value_type{}).
      3) Equivalent toreduce(first, last, init,std::plus<>()).
      5) Reduces the range[first, last), possibly permuted and aggregated in unspecified manner, along with the initial valueinit overop.
      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)

      Givenbinary_op as the actual binary operation:

      • The result is non-deterministic if thebinary_op 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:
      • binary_op(init,*first)
      • binary_op(*first, init)
      • binary_op(init, init)
      • binary_op(*first,*first)
      • If any of the following conditions is satisfied, the behavior is undefined:
      • T is notMoveConstructible.
      • binary_op modifies any element of[first, last).
      • binary_op invalidates any iterator or subrange of[first, last].

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining therange of elements to apply the algorithm to
      init - the initial value of the generalized sum
      policy - theexecution policy to use
      op - binaryFunctionObject that will be applied in unspecified order to the result of dereferencing the input iterators, the results of otherop andinit.
      Type requirements
      -
      InputIt must meet the requirements ofLegacyInputIterator.
      -
      ForwardIt must meet the requirements ofLegacyForwardIterator.

      [edit]Return value

      1-4) The generalized sum ofinit and the elements of[first, last) overstd::plus<>().
      5,6) The generalized sum ofinit and the elements of[first, last) overop.

      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(first, last):

      1-4)\(\scriptsize O(N)\)O(N) applications ofstd::plus<>().
      5,6)\(\scriptsize O(N)\)O(N) applications ofop.

      [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

      std::reduce behaves likestd::accumulate except the elements of the range may be grouped and rearranged in arbitrary order.

      [edit]Example

      Side-by-side comparison betweenstd::reduce andstd::accumulate:

      Run this code
      #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){constauto t1=std::chrono::high_resolution_clock::now();constauto[name, result]= fun();constauto t2=std::chrono::high_resolution_clock::now();conststd::chrono::duration<double,std::milli> ms= t2- t1;std::cout<<std::setw(28)<<std::left<< name<<"sum: "<< result<<'\t'<<"time: "<< ms.count()<<" ms\n";}; {conststd::vector<double> v(100'000'007,0.1);         eval([&v]{returnstd::pair{"std::accumulate (double)",std::accumulate(v.cbegin(), v.cend(),0.0)};});        eval([&v]{returnstd::pair{"std::reduce (seq, double)",            std::reduce(SEQ v.cbegin(), v.cend())};});        eval([&v]{returnstd::pair{"std::reduce (par, double)",            std::reduce(PAR v.cbegin(), v.cend())};});} {conststd::vector<long> v(100'000'007,1);         eval([&v]{returnstd::pair{"std::accumulate (long)",std::accumulate(v.cbegin(), v.cend(),0l)};});        eval([&v]{returnstd::pair{"std::reduce (seq, long)",            std::reduce(SEQ v.cbegin(), v.cend())};});        eval([&v]{returnstd::pair{"std::reduce (par, long)",            std::reduce(PAR v.cbegin(), v.cend())};});}}

      Possible output:

      // POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.outstd::accumulate (double)    sum: 10,000,000.7time: 356.9 msstd::reduce (seq, double)   sum: 10,000,000.7time: 140.1 msstd::reduce (par, double)   sum: 10,000,000.7time: 140.1 msstd::accumulate (long)      sum: 100,000,007time: 46.0 msstd::reduce (seq, long)     sum: 100,000,007time: 67.3 msstd::reduce (par, long)     sum: 100,000,007time: 63.3 ms // POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.outstd::accumulate (double)    sum: 10,000,000.7time: 353.4 msstd::reduce (seq, double)   sum: 10,000,000.7time: 140.7 msstd::reduce (par, double)   sum: 10,000,000.7time: 24.7 msstd::accumulate (long)      sum: 100,000,007time: 42.4 msstd::reduce (seq, long)     sum: 100,000,007time: 52.0 msstd::reduce (par, long)     sum: 100,000,007time: 23.1 ms

      [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]
      applies an invocable, then reduces out of order
      (function template)[edit]
      left-folds a range of elements
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/reduce&oldid=180315"
      [8]ページ先頭
      ©2009-2025 Movatter.jp