偏和

类别: 算法	组件类型: 函数

原型

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryOperation binary_op);

描述

更准确地说，运行总和首先初始化为*first并赋值给*result。对于每个迭代器i在[first + 1, last)中，从开始到结束的顺序，总和通过sum = sum + *i(在第一个版本中)或sum = binary_op(sum, *i)(在第二个版本中)更新，并赋值给*(result + (i - first)). [2]

定义

类型要求

• InputIterator是 输入迭代器 的模型。
• OutputIterator是 输出迭代器 的模型。
• 如果x以及y是InputIterator的值类型的对象，则x + y已定义。
• 的返回类型x + y可转换为InputIterator的值类型。
• InputIterator的值类型可转换为OutputIterator的值类型集中的一种类型。

• InputIterator是 输入迭代器 的模型。
• OutputIterator是 输出迭代器 的模型。
• BinaryFunction是 二元函数 的模型。
• InputIterator的值类型可转换为BinaryFunction的第一个参数类型和第二个参数类型。
• BinaryFunction的结果类型可转换为InputIterator的值类型。
• InputIterator的值类型可转换为OutputIterator的值类型集中的一种类型。

先决条件

• [first, last)是一个有效范围。
• [result, result + (last - first))是一个有效范围。

复杂度

示例

int main()
{
  const int N = 10;
  int A[N];

  fill(A, A+N, 1);
  cout << "A:                 ";
  copy(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;

  cout << "Partial sums of A: ";
  partial_sum(A, A+N, ostream_iterator<int>(cout, " "));
  cout << endl;
}  

注释

[1] 注意result允许与first是相同的迭代器。这对于“就地”计算偏和很有用。

[2] 二元运算不需要是结合的或交换的：所有运算的顺序都是指定的。

另请参阅