std::reduce
来自cppreference.com
| 在标头 <numeric> 定义
|
||
| template< class InputIt > typename std::iterator_traits<InputIt>::value_type |
(1) | (C++17 起) (C++20 起为 constexpr) |
| template< class ExecutionPolicy, class ForwardIt > typename std::iterator_traits<ForwardIt>::value_type |
(2) | (C++17 起) |
| template< class InputIt, class T > T reduce( InputIt first, InputIt last, T init ); |
(3) | (C++17 起) (C++20 起为 constexpr) |
| template< class ExecutionPolicy, class ForwardIt, class T > T reduce( ExecutionPolicy&& policy, |
(4) | (C++17 起) |
| template< class InputIt, class T, class BinaryOp > T reduce( InputIt first, InputIt last, T init, BinaryOp op ); |
(5) | (C++17 起) (C++20 起为 constexpr) |
| template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp > |
(6) | (C++17 起) |
1) 等价于 reduce(first, last, typename std::iterator_traits<InputIt>::value_type{})。
3) 等价于 reduce(first, last, init, std::plus<>())。
5) 在 op 上以初值 init 对范围
[first, last) 进行规约，可能以未指定方式进行排列和聚合。2,4,6) 同 (1,3,5)，但按照 policy 执行。
这些重载只有在
是 true 时时才会参与重载决议。
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> |
(C++20 前) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> |
(C++20 起) |
给定 binary_op 为实际的二元运算：
- 如果 binary_op 不可结合或不可交换（例如浮点加法），那么结果不确定。
- 如果以下任何值不可转换到
T，那么程序非良构：
- binary_op(init, *first)
- binary_op(*first, init)
- binary_op(init, init)
- binary_op(*first, *first)
- 如果满足以下任意条件，那么行为未定义：
-
T不可移动构造 (MoveConstructible) 。 - binary_op 会修改
[first,last)的元素。 - binary_op 会使
[first,last]中的迭代器或子范围失效。
-
参数
| first, last | - | 要应用算法的元素范围 |
| init | - | 广义和的初值 |
| policy | - | 所用的执行策略。细节见执行策略。 |
| op | - | 将以未指定顺序应用于输入迭代器的解引用结果、其他 binary_op 的结果及 init 上的二元函数对象 (FunctionObject) 。 |
| 类型要求 | ||
-InputIt 必须满足老式输入迭代器 (LegacyInputIterator) 。
| ||
-ForwardIt 必须满足老式向前迭代器 (LegacyForwardIterator) 。
| ||
返回值
5,6) init 和
[first, last) 的元素在 op 上的广义和。一组元素在二元运算 binary_op 上的广义和 定义如下：
- 如果元素组只有一个元素，那么和就是该元素的值。
- 否则，依次进行以下操作：
- 从元素组中取走两个元素 elem1 和 elem2。
- 计算 binary_op(elem1, elem2)，并将结果放回元素组。
- 重复以上两步，直到组里只剩一个元素。
复杂度
给定 N 为 std::distance(first, last)：
5,6) 应用 O(N) 次 op。
异常
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
- 如果作为算法一部分调用的函数的执行抛出异常，且
ExecutionPolicy是标准策略之一，那么调用 std::terminate。对于任何其他ExecutionPolicy，行为由实现定义。 - 如果算法无法分配内存，那么抛出 std::bad_alloc。
注解
std::reduce 表现类似 std::accumulate，但范围中的元素可能以任意顺序分组并重排。
示例
std::reduce 与 std::accumulate 间并行的比较：
运行此代码
#if PARALLEL #include <execution> #define SEQ std::execution::seq, #define PAR std::execution::par, #else #define SEQ #define PAR #endif #include <chrono> #include <iomanip> #include <iostream> #include <numeric> #include <utility> #include <vector> int main() { std::cout.imbue(std::locale("en_US.UTF-8")); std::cout << std::fixed << std::setprecision(1); auto eval = [](auto fun) { const auto t1 = std::chrono::high_resolution_clock::now(); const auto [name, result] = fun(); const auto t2 = std::chrono::high_resolution_clock::now(); const std::chrono::duration<double, std::milli> ms = t2 - t1; std::cout << std::setw(28) << std::left << name << "和：" << result << '\t' << "时间：" << ms.count() << " 毫秒\n"; }; { const std::vector<double> v(100'000'007, 0.1); eval([&v]{ return std::pair{"std::accumulate (double)", std::accumulate(v.cbegin(), v.cend(), 0.0)}; }); eval([&v]{ return std::pair{"std::reduce (seq, double)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair{"std::reduce (par, double)", std::reduce(PAR v.cbegin(), v.cend())}; }); } { const std::vector<long> v(100'000'007, 1); eval([&v]{ return std::pair{"std::accumulate (long)", std::accumulate(v.cbegin(), v.cend(), 0l)}; }); eval([&v]{ return std::pair{"std::reduce (seq, long)", std::reduce(SEQ v.cbegin(), v.cend())}; }); eval([&v]{ return std::pair{"std::reduce (par, long)", std::reduce(PAR v.cbegin(), v.cend())}; }); } }
可能的输出：
// POSIX：g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out std::accumulate (double) 和：10,000,000.7 时间：356.9 毫秒 std::reduce (seq, double) 和：10,000,000.7 时间：140.1 毫秒 std::reduce (par, double) 和：10,000,000.7 时间：140.1 毫秒 std::accumulate (long) 和：100,000,007 时间：46.0 毫秒 std::reduce (seq, long) 和：100,000,007 时间：67.3 毫秒 std::reduce (par, long) 和：100,000,007 时间：63.3 毫秒 // POSIX：g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out std::accumulate (double) 和：10,000,000.7 时间：353.4 毫秒 std::reduce (seq, double) 和：10,000,000.7 时间：140.7 毫秒 std::reduce (par, double) 和：10,000,000.7 时间：24.7 毫秒 std::accumulate (long) 和：100,000,007 时间：42.4 毫秒 std::reduce (seq, long) 和：100,000,007 时间：52.0 毫秒 std::reduce (par, long) 和：100,000,007 时间：23.1 毫秒
参阅
| 对一个范围内的元素求和或折叠 (函数模板) | |
| 将一个函数应用于某一范围的各个元素，并在目标范围存储结果 (函数模板) | |
| (C++17) |
应用一个可调用物，然后以乱序规约 (函数模板) |
| (C++23) |
左折叠范围内的元素 (niebloid) |