std::exclusive_scan
来自cppreference.com
<tbody>
</tbody>
| 在标头 <numeric> 定义
|
||
template< class InputIt, class OutputIt, class T > OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init ); |
(1) | (C++17 起) (C++20 起为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T > ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, T init ); |
(2) | (C++17 起) |
template< class InputIt, class OutputIt, class T, class BinaryOp > OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init, BinaryOp op ); |
(3) | (C++17 起) (C++20 起为 constexpr) |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T, class BinaryOp > ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first, T init, BinaryOp op ); |
(4) | (C++17 起) |
1) 等价于
exclusive_scan(first, last, d_first, init, std::plus<>()。3) 用
op 计算排除性前缀和。 对于
[0, std::distance(first, last)) 中的所有整数 i，按顺序进行以下操作：
- 创建一个序列，它以
init开始，然后按顺序后随[first,iter)中的所有元素，其中iter是first的下i个迭代器。 - 计算该序列在
op下的广义非交换和。 - 将计算结果赋给
*dest，其中dest是d_first的下i个迭代器。
2,4) 同 (1,3)，但按照
policy 执行。 这些重载只有在满足以下所有条件时才会参与重载决议：
|
|
(C++20 前) |
|
|
(C++20 起) |
一个元素序列在二元运算 binary_op 上的广义非交换和 定义如下：
- 如果序列只有一个元素，那么和就是该元素的值。
- 否则，依次进行以下操作：
- 从序列中选择两个相邻元素
elem1和elem2。 - 计算
binary_op(elem1, elem2)，并将序列中的这两个元素替换成计算结果。 - 重复以上两步，直到组里只剩一个元素。
给定 binary_op 为实际的二元运算：
- 如果
binary_op不可结合（例如浮点加法），那么结果不确定。
- 如果以下任何值不可转换到
T，那么程序非良构：
binary_op(init, *first)binary_op(init, init)binary_op(*first, *first)
- 如果满足以下任意条件，那么行为未定义：
T不可移动构造 (MoveConstructible) 。binary_op会修改[first,last)的元素。binary_op会使[first,last]中的迭代器或子范围失效。
参数
| first, last | - | 要求和的元素范围的迭代器对 |
| d_first | - | 目标范围的起始；可以等于 first
|
| policy | - | 所用的执行策略 |
| init | - | 初始值 |
| op | - | 二元函数对象 (FunctionObject) ，将应用到各输入迭代器的解引用结果、其他 op 的结果和 init 之上。
|
| 类型要求 | ||
-InputIt 必须满足老式输入迭代器 (LegacyInputIterator) 。
| ||
-OutputIt 必须满足老式输出迭代器 (LegacyOutputIterator) 。
| ||
-ForwardIt1, ForwardIt2 必须满足老式向前迭代器 (LegacyForwardIterator) 。
| ||
返回值
指向最后写入元素的后一元素的迭代器。
复杂度
给定 N 为 std::distance(first, last)：
1,2) 应用 O(N) 次
std::plus<>()。3,4) 应用 O(N) 次
op。异常
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
- 如果作为算法一部分调用的函数的执行抛出异常，且
ExecutionPolicy是标准策略之一，那么调用 std::terminate。对于任何其他ExecutionPolicy，行为由实现定义。 - 如果算法无法分配内存，那么抛出 std::bad_alloc。
示例
运行此代码
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
int main()
{
std::vector data{3, 1, 4, 1, 5, 9, 2, 6};
std::cout << "Exclusive sum: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
0);
std::cout << "\nInclusive sum: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n\nExclusive product: ";
std::exclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
1, std::multiplies<>{});
std::cout << "\nInclusive product: ";
std::inclusive_scan(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "),
std::multiplies<>{});
}
输出：
Exclusive sum: 0 3 4 8 9 14 23 25
Inclusive sum: 3 4 8 9 14 23 25 31
Exclusive product: 1 3 3 12 12 60 540 1080
Inclusive product: 3 3 12 12 60 540 1080 6480
参阅
| 计算范围中相邻元素的差 (函数模板) | |
| 求和或折叠范围中元素 (函数模板) | |
| 计算范围中元素的部分和 (函数模板) | |
(C++17) |
应用可调用对象，然后计算排除扫描 (函数模板) |
(C++17) |
类似 std::partial_sum，第 i 个和中包含第 i 个输入 (函数模板) |