std::partial_sum

定義於標頭檔案 `<numeric>`
template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );	(1)	(C++20 起為 constexpr)
template< class InputIt, class OutputIt, class BinaryOp > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOp op );	(2)	(C++20 起為 constexpr)

1) 如果 [first, last) 為空，則不執行任何操作。

否則，按順序執行以下操作：

建立一個累加器 acc，其型別為 InputIt 的值型別，並用 *first 初始化它。
將 acc 賦值給 *d_first。
對於 [1, std::distance(first, last)) 中的每個整數 i，按順序執行以下操作：

a) 計算 acc + *iter(C++20 前)std::move(acc) + *iter(C++20 起)，其中 iter 是 first 的第 i 個迭代器。

b) 將結果賦值給 acc。

c) 將 acc^[1] 賦值給 *dest，其中 dest 是 d_first 的第 i 個迭代器。

2) 同 (1)，但計算 op(acc, *iter)(C++20 前)op(std::move(acc), *iter)(C++20 起) 代替。

給定 binary_op 作為實際的二元操作，

如果滿足以下任何條件，程式將不正確：

InputIt 的值型別不可由 *first 構造。
acc 不可寫入 d_first。
binary_op(acc, *iter)(C++20 前)binary_op(std::move(acc), *iter)(C++20 起) 的結果不可隱式轉換為 InputIt 的值型別。

給定 d_last 為將要返回的迭代器，如果滿足以下任何條件，則行為未定義：

binary_op 修改了 [first, last) 或 [d_first, d_last) 中的任何元素。
binary_op 使 [first, last] 或 [d_first, d_last] 中的任何迭代器或子範圍無效。

↑ 實際賦值的值是上一步中賦值的結果。我們在此假設賦值結果為 acc。

first, last	-	定義要求和元素的範圍的迭代器對
d_first	-	目標範圍的起始；可以等於 first
op	-	將應用的二元操作函式物件。函式的簽名應等效於以下內容 Ret fun(const Type1 &a, const Type2 &b); 簽名不需要有 const &。型別 Type1 必須使得型別 std::iterator_traits<InputIt>::value_type 的物件可以隱式轉換為 Type1。型別 Type2 必須使得 InputIt 型別的物件可以解引用，然後隱式轉換為 Type2。型別 Ret 必須使得 InputIt 型別的物件可以解引用並賦值為 Ret 型別的值。
型別要求
- `InputIt` 必須滿足 LegacyInputIterator 的要求。
- `OutputIt` 必須滿足 LegacyOutputIterator 的要求。

[編輯] 返回值

指向寫入的最後一個元素之後元素的迭代器，如果 [first, last) 為空，則為 d_first。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first, last)

1) 精確執行

N-1

次 operator+ 應用。

2) 精確執行

N-1

次二元函式 op 應用。

[編輯] 可能的實現

partial_sum (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<>());
}

partial_sum (2)

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

[編輯] 注意

引入 acc 是因為 LWG issue 539 的解決方案。使用 acc 而不是直接求和結果（即 *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);）的原因是，如果以下型別不匹配，後者的語義會令人困惑：

InputIt 的值型別
OutputIt 的可寫型別
operator+ 或 op 引數的型別
operator+ 或 op 的返回型別

acc 作為中間物件，用於儲存併為計算的每個步驟提供值：

其型別是 InputIt 的值型別
它被寫入到 d_first
其值傳遞給 operator+ 或 op
它儲存 operator+ 或 op 的返回值

enum not_int { x = 1, y = 2 };
 
char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];
 
// OK: uses operator+(char, char) and assigns char values to int array
std::partial_sum(i_array, i_array + 4, o_array);
 
// Error: cannot assign not_int values to int array
std::partial_sum(e_array, e_array + 4, o_array);
 
// OK: performs conversions when needed
// 1. creates “acc” of type char (the value type)
// 2. the char arguments are used for long multiplication (char -> long)
// 3. the long product is assigned to “acc” (long -> char)
// 4. “acc” is assigned to an element of “o_array” (char -> int)
// 5. go back to step 2 to process the remaining elements in the input range
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

[編輯] 示例

執行此程式碼

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
 
    std::cout << "The first " << v.size() << " even numbers are: ";
    // write the result to the cout stream
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // write the result back to the vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
 
    std::cout << "The first " << v.size() << " powers of 2 are: ";
    for (int 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

[編輯] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告	應用於	釋出時的行為	正確的行為
LWG 242	C++98	op 不得有副作用	它不能修改涉及的範圍
LWG 539	C++98	結果所需的型別要求缺少評估和賦值的有效性	已新增

[編輯] 參閱

adjacent_difference	計算一個範圍內相鄰元素之間的差值 (函式模板) [編輯]
accumulate	對一個範圍的元素進行求和或摺疊 (函式模板) [編輯]
inclusive_scan (C++17)	類似於 std::partial_sum，將第 $i$ 個輸入元素包含在第 $i$ 個和中 (函式模板) [編輯]
exclusive_scan (C++17)	類似於 std::partial_sum，將第 $i$ 個輸入元素從第 $i$ 個和中排除 (函式模板) [編輯]

[1] 實際賦值的值是上一步中賦值的結果。我們在此假設賦值結果為 acc。

[1]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作