std::reduce() 算法

自 C++20 起

// (1)
template< class InputIt >
constexpr typename std::iterator_traits<InputIt>::value_type
    reduce( InputIt first, InputIt last );

// (2)
template< class InputIt, class T >
constexpr T reduce( InputIt first, InputIt last, T init );

// (3)
template< class InputIt, class T, class BinaryOp >
constexpr T reduce( InputIt first, InputIt last, T init, BinaryOp binary_op );

// (4)
template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
    reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

// (5)
template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init );

// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp binary_op );

自 C++17 起

// (1)
template< class InputIt >
typename std::iterator_traits<InputIt>::value_type
    reduce( InputIt first, InputIt last );

// (2)
template< class InputIt, class T >
T reduce( InputIt first, InputIt last, T init );

// (3)
template< class InputIt, class T, class BinaryOp >
T reduce( InputIt first, InputIt last, T init, BinaryOp binary_op );

// (4)
template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
    reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

// (5)
template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init );

// (6)
template< class ExecutionPolicy, class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init, BinaryOp binary_op );

• (1) 与 reduce(first, last, typename std::iterator_traits<InputIt>::value_type{}) 相同

• (2) 与 reduce(first, last, init, std::plus<>()) 相同

• (3) 通过 binary_op 约减范围 [first; last)，可能以未指定的方式排列和聚合，并与初始值 init 一起。

• (4 - 6) 与 (1 - 3) 相同，但根据策略执行。

  重载决议

  这些重载只有在 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 修改 [first, last) 中的任何元素或使任何迭代器失效，包括结束迭代器。

参数

first last	要应用算法的元素范围。
init	广义和的初始值。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
binary_op	二元函数对象，将以未指定顺序应用于解引用输入迭代器的结果、其他 binary_op 的结果和 init。

类型要求

InputIt	LegacyInputIterator
ForwardIt	LegacyForwardIterator
T	MoveAssignable MoveConstructible

• 以下表达式必须可转换为 T
  • binary_op(init, *first)
  • binary_op(*first, init)
  • binary_op(init, init)
  • binary_op(*first, *first)

返回值

init 和 *first, *(first + 1), ... *(last - 1) 通过 binary_op 的广义和，

行为类似于 std::reduce，但范围中的元素可以以任意顺序进行分组和重新排列。

形式上，广义和 GSUM(op, a1, ..., aN) 定义如下：

• 如果 N = 1，则为 a1
• 如果 N > 1，则为 op(GSUM(op, b 1, ..., b K), GSUM(op, b M, ..., b N))，其中
  • b1, ..., bN 可以是 a1, ..., aN 的任意排列
  • 且 1 < K + 1 = M ≤ N

重要

如果范围为空，则返回未修改的 init。

复杂度

O(last - first) 次 binary_op 应用。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的。.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

示例

Main.cpp

#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 << "sum: "
                  << result << "\t time: " << ms.count() << " ms\n";
    };
    {
        const std::vector<double> v(100'000'007, 0.1);

        eval([&v]{ return std::pair{"std::reduce (double)",
            std::reduce(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::reduce (long)",
            std::reduce(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::reduce (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::reduce (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::reduce (double)    sum: 10,000,000.7    time: 353.4 ms
std::reduce (seq, double)   sum: 10,000,000.7    time: 140.7 ms
std::reduce (par, double)   sum: 10,000,000.7    time: 24.7 ms
std::reduce (long)      sum: 100,000,007     time: 42.4 ms
std::reduce (seq, long)     sum: 100,000,007     time: 52.0 ms
std::reduce (par, long)     sum: 100,000,007     time: 23.1 ms