C++ partial_sum(STL partial_sum)部分和計算方法詳解

2020-07-16 10:04:29
定義在 header 標頭檔案中的 partial_sum() 可以計算輸入序列中元素的部分和,並將結果儲存到一個輸出序列中。

partial_sum() 會計算出輸入序列中長度從1開始不斷增加的序列的和,所以第一個輸出值就是第一個元素,下一個值是前兩個元素的和,再下一個值就是前三個元素的和,以此類推。這和 adjacent_difference() 演算法是相反的,因此 partial_sum() 不會做 adjacent_difference() 做的事。下面是一個範例:
std::vector<int> data {2, 3, 5, 7, 11, 13, 17, 19};
std::cout << "Partial sums: ";
std::partial_sum(std::begin(data), std::end(data),std::ostream_iterator<int>{std::cout, " "});
std::cout << std::endl; // Partial sums: 2 5 10 17 28 41 58 77
可以看到,輸出是由長度穩定增加的序列的和組成的。通過執行下面的程式碼,可以很容易展示出這些結果:
std::vector<int> data {2, 3, 5, 7, 11, 13, 17, 19};
std::cout << "Original data: ";
std::copy(std::begin(data), std::end(data), std::ostream_ iterator<int>{std::cout, " "});
std::adjacent_difference(std::begin(data), std::end(data),std::begin (data));
std::cout << "nDifferences : ";
std::copy(std::begin(data), std::end(data),std::ostream_iterator<int>{std::cout," "});
std::cout << "nPartial sums : ";
std::partial_sum(std::begin(data), std::end(data),std::ostream_iterator<int>{std::cout, " "});
std::cout << std::endl;
注意,這裡的輸出疊代器和輸入序列的開始疊代器是相同的。這是合法的,可以認為 data 是可覆蓋的,但演算法被定義為阻止這麼做。執行這段程式碼後得到的輸出如下:

Original data: 2 3 5 7 11 13 17 19
Differences: 2 1 2 2 4 2 4 2
Partial sums: 2 3 5 7 11 13 17 19

輸出顯示了用原始值的差值計算出的部分和,這一點不令人吃驚。像 adjacent_difference() 演算法一樣,可以提供一個函數物件作為 partial_sum() 的額外引數,額外引數被用來定義一個代替加法的運算子。下面是它可能的運用方式:
std::vector<int> data {2, 3, 5, 7, 11, 13, 17, 19};
std::cout << "Partial sums:";
std::partial_sum (std::begin (data) , std::end (data),std::ostream_iterator<int>{std::cout, " "}, std::minus<int>());
std::cout << std::endl;  // Partial sums: 2 -1 -6 -13 -24 -37 -54 -73
這裡使用了減法運算子,所以值是 2、2-3、2-3-5、2-3-5-7 的結果,以此類推。