std::partial_sum

提供: cppreference.com

ヘッダ `<numeric>` で定義
	(1)
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );			(C++20未満)
template< class InputIt, class OutputIt > constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );			(C++20以上)
		(2)
template< class InputIt, class OutputIt, class BinaryOperation > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );				(C++20未満)
template< class InputIt, class OutputIt, class BinaryOperation > constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );				(C++20以上)

範囲 [first, last) の部分範囲の部分和を計算し、それらを d_first から始まる範囲に書き込みます。 1つめのバージョンは要素を加算するために operator+ を使用し、2つめのバージョンは指定された二項関数を使用します。どちらの場合も、左側の被演算子に std::move が適用されます。 (C++20以上)

以下の操作と同等です。

*(d_first)   = *first;
*(d_first+1) = *first + *(first+1);
*(d_first+2) = *first + *(first+1) + *(first+2);
*(d_first+3) = *first + *(first+1) + *(first+2) + *(first+3);
...

`op` は副作用を持っていてはなりません。	(C++11未満)
`op` は終端イテレータを含むいかなるイテレータも無効化してはならず、影響のある範囲のいかなる要素も変更してはなりません。	(C++11以上)

first, last	-	加算する要素の範囲
d_first	-	書き込み先範囲の先頭。 `first` と等しくても構いません
op	-	適用される二項演算関数オブジェクト。関数のシグネチャは以下と同等であるべきです。 Ret fun(const Type1 &a, const Type2 &b); シグネチャが const & を持つ必要はありません。型 Type1 は、 iterator_traits<InputIt>::value_type 型のオブジェクトから暗黙に変換可能なものでなければなりません。型 Type2 は、 InputIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。型 Ret は iterator_traits<InputIt>::value_type 型のオブジェクトに代入可能なものでなければなりません。
型の要件
- `InputIt` は LegacyInputIterator の要件を満たさなければなりません。
- `OutputIt` は LegacyOutputIterator の要件を満たさなければなりません。

[編集] 戻り値

最後に書き込まれた要素の次の要素を指すイテレータ。

[編集] 計算量

ちょうど (last - first) - 1 回の二項演算の適用。

[編集] 実装例

1つめのバージョン

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = std::move(sum) + *first; // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

2つめのバージョン

template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOperation op)
{
    if (first == last) return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last) {
       sum = op(std::move(sum), *first); // std::move since C++20
       *++d_first = sum;
    }
    return ++d_first;
}

[編集] 例

Run this code

#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <functional>
 
int main()
{
    std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or std::vector<int>v(10, 2);
 
    std::cout << "The first 10 even numbers are: ";
    std::partial_sum(v.begin(), v.end(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());
    std::cout << "The first 10 powers of 2 are: ";
    for (auto n : v) {
        std::cout << n << " ";
    }
    std::cout << '\n';
}

出力:

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024

[編集] 関連項目

adjacent_difference	指定範囲の隣接する要素間の差を計算します (関数テンプレート) [edit]
accumulate	指定範囲の要素を合計します (関数テンプレート) [edit]
inclusive_scan (C++17)	std::partial_sum と同様ですが、計算順序は不定です (関数テンプレート) [edit]
exclusive_scan (C++17)	std::inclusive_scan と同様ですが、 i 番目の合計に i 番目の要素が含まれません (関数テンプレート) [edit]

「https://ja.cppreference.com/mwiki/index.php?title=cpp/algorithm/partial_sum&oldid=46607」から取得

言語
標準ライブラリヘッダ
フリースタンディング処理系とホスト処理系
名前付き要件
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
イテレータライブラリ
範囲ライブラリ (C++20)
アルゴリズムライブラリ
数値演算ライブラリ
ローカライゼーションライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドサポートライブラリ (C++11)
技術仕様書

cppreference.com

名前空間

変種

表示

操作