std:: reduce

From cppreference.net

定义于头文件 `<numeric>`
template < class InputIt > typename std:: iterator_traits < InputIt > :: value_type reduce ( InputIt first, InputIt last ) ;	(1)	(C++17 起) (C++20 起为 constexpr)
template < class ExecutionPolicy, class ForwardIt > typename std:: iterator_traits < ForwardIt > :: value_type reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last ) ;	(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, ForwardIt first, ForwardIt last, T init ) ;	(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 > T reduce ( ExecutionPolicy && policy, ForwardIt first, ForwardIt last, T init, BinaryOp op ) ;	(6)	(C++17 起)

1) 等价于 reduce ( first, last, typename std:: iterator_traits < InputIt > :: value_type { } ) 。

3) 等价于 reduce ( first, last, init, std:: plus <> ( ) ) 。

5) 将可能以未指定方式排列和聚合的范围

first

last

与初始值 init 通过 op 进行归约。

2,4,6) 与 (1,3,5) 相同，但根据 policy 执行。

这些重载仅在满足以下所有条件时参与重载决议：

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> 为 true 。	(C++20 前)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> 为 true 。	(C++20 起)

给定 binary_op 作为实际二元操作：

如果 binary_op 不满足结合律或交换律（例如浮点数加法），则结果将是非确定性的。

如果以下任意值无法转换为 T ，则程序非良构：

binary_op ( init, * first )
binary_op ( * first, init )
binary_op ( init, init )
binary_op ( * first, * first )

注：根据要求，所有C++代码（位于


       标签内）及HTML标签均保持原样未翻译。由于原文仅包含代码片段，无其他需要翻译的自然语言文本，故输出内容与原文完全一致。

若满足以下任一条件，则行为未定义：

T 不满足 MoveConstructible 要求。
binary_op 修改了 [ first , last ) 范围内的任何元素。
binary_op 使 [ first , last ] 范围内的任何迭代器或子区间失效。

first, last	-	定义算法应用范围的迭代器对
init	-	广义和的初始值
policy	-	使用的执行策略
op	-	将以未指定顺序应用于解引用输入迭代器结果、其他 op 结果和 init 的二元函数对象
类型要求
- `InputIt` 必须满足 LegacyInputIterator 的要求
- `ForwardIt` 必须满足 LegacyForwardIterator 的要求

返回值

1-4) 广义上的 init 与区间

first

last

内元素在 std:: plus <> ( ) 操作下的累加和。

5,6) init 与范围

first

last

中元素的广义和，通过 op 运算得到。

一组元素在二元运算 binary_op 上的 广义和 定义如下：

如果该组仅有一个元素，则求和结果即为该元素的值。
否则，按顺序执行以下操作：

从群组中取出任意两个元素 elem1 和 elem2 。
计算 binary_op ( elem1, elem2 ) 并将结果放回群组。
重复步骤1和2，直到群组中仅剩一个元素。

复杂度

给定 $\scriptsize N$ $N$ 为 std:: distance ( first, last ) ：

1-4)

O(N)

次 std:: plus <> ( ) 的应用。

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 <locale>
#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 << "sum: "
                  << result << '\t' << "time: " << ms.count() << " ms\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)    sum: 10,000,000.7	time: 356.9 ms
std::reduce (seq, double)   sum: 10,000,000.7	time: 140.1 ms
std::reduce (par, double)   sum: 10,000,000.7	time: 140.1 ms
std::accumulate (long)      sum: 100,000,007	time: 46.0 ms
std::reduce (seq, long)     sum: 100,000,007	time: 67.3 ms
std::reduce (par, long)     sum: 100,000,007	time: 63.3 ms
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    sum: 10,000,000.7	time: 353.4 ms
std::reduce (seq, double)   sum: 10,000,000.7	time:

参见

accumulate	对范围内的元素进行求和或折叠操作 (函数模板)
transform	对范围内的元素应用函数，并将结果存储到目标范围 (函数模板)
transform_reduce (C++17)	应用可调用对象后，以无序方式执行规约操作 (函数模板)
ranges::fold_left (C++23)	对范围内的元素执行左折叠操作 (算法函数对象)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std:: reduce

目录

参数

返回值

复杂度

异常

注释

示例

参见