名前空間
変種
操作

std::reduce

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
reduce
(C++17)
C のライブラリ
 
ヘッダ <numeric> で定義
template<class InputIt>

typename std::iterator_traits<InputIt>::value_type reduce(

    InputIt first, InputIt last);
(1) (C++17およびそれ以降)
template<class ExecutionPolicy, class ForwardIt>

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

    ForwardIt first, ForwardIt last);
(2) (C++17およびそれ以降)
template<class InputIt, class T>
T reduce(InputIt first, InputIt last, T init);
(3) (C++17およびそれ以降)
template<class ExecutionPolicy, class ForwardIt, class T>

T reduce(ExecutionPolicy&& policy,

         ForwardIt first, ForwardIt last, T init);
(4) (C++17およびそれ以降)
template<class InputIt, class T, class BinaryOp>
T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);
(5) (C++17およびそれ以降)
template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp>

T reduce(ExecutionPolicy&& policy,

         ForwardIt first, ForwardIt last, T init, BinaryOp binary_op);
(6) (C++17およびそれ以降)
1) reduce(first, last, typename std::iterator_traits<InputIt>::value_type{}) と同じです。
3) reduce(first, last, init, std::plus<>()) と同じです。
5) binary_op と初期値 init を用いて、場合によっては未規定の方法で並べ替えたり集約したりしながら、範囲 [first; last) を縮小します。
2,4,6) (1,3,5) と同じですが、 policy に従って実行されます。 このオーバーロードは、std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true である場合にのみ、オーバーロード解決に参加します。

binary_op が交換法則や結合法則を満たさない場合、動作は非決定的になります。

binary_op が終端イテレータを含む [first; last] 内のいずれかのイテレータを無効化したり、いずれかの要素を変更したりした場合、動作は未定義です。

目次

[編集] 引数

first, last - アルゴリズムを適用する要素の範囲
init - 一般化された合計の初期値
policy - 使用する実行ポリシー。 詳細は実行ポリシーを参照してください
binary_op - 入力イテレータを逆参照した結果、他の binary_op の結果、および init に未規定の順序で適用される二項 FunctionObject
型の要件
-
InputItInputIterator の要件を満たさなければなりません。
-
ForwardItForwardIterator の要件を満たさなければなりません。
-
TMoveConstructible の要件を満たさなければなりません。 また、 binary_op(init, *first)binary_op(*first, init)binary_op(init, init) および binary_op(*first, *first)T に変換可能でなければなりません。

[編集] 戻り値

init, *first, *(first+1), ... *(last-1)binary_op による一般化された合計。

ただし一般化された合計 GSUM(op, a
1
, ..., a
N
)
は以下のように定義されます。

  • N=1 であれば、結果は a
    1
    です。
  • N > 1 であれば、結果は op(GSUM(op, b
    1
    , ..., b
    K
    ), GSUM(op, b
    M
    , ..., b
    N
    ))
    です。 ただし、
  • b
    1
    , ..., b
    N
    a1, ..., aN の任意の順列であってもよく、
  • 1 < K+1 = M ≤ N です。

別の言い方をすると、 reducestd::accumulate と似た動作をしますが、範囲内の要素は適当な順序でグループ化されたり並べ替えられたりすることがあります。

[編集] 計算量

O(last - first) 回の binary_op の適用。

[編集] 例外

テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。

  • アルゴリズムの一部として呼び出された関数の実行が例外を投げ、 ExecutionPolicy が3つの標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。 それ以外のあらゆる ExecutionPolicy については、動作は処理系定義です。
  • アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。

[編集] ノート

範囲が空の場合は、 init が変更されずに返されます。

[編集]

reduce と std::accumulate を並べて比較します。

#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>
#include <execution>
 
int main()
{
    std::vector<double> v(10'000'007, 0.5);
 
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        double result = std::accumulate(v.begin(), v.end(), 0.0);
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << "std::accumulate result " << result
                  << " took " << ms.count() << " ms\n";
    }
 
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        double result = std::reduce(std::execution::par, v.begin(), v.end());
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << "std::reduce result "
                  << result << " took " << ms.count() << " ms\n";
    }
}

出力例:

std::accumulate result 5000003.50000 took 12.7365 ms
std::reduce result 5000003.50000 took 5.06423 ms

[編集] 関連項目

指定範囲の要素を合計します
(関数テンプレート) [edit]
指定範囲の要素に関数を適用します
(関数テンプレート) [edit]
不定の計算順序で、関数オブジェクトを適用した結果を reduce します
(関数テンプレート) [edit]