std::transform_reduce(3)

📦 version 2024.07.05, in nixpkgs unstable, opensuse-leap 16.0

💖 `std::transform_reduce` (3) — C++ Standard Library 💖

okay so bestie, listen. this is std::transform_reduce, and she is genuinely that girl. she lives in the header <numeric>, and she's basically the glow-up of std::inner_product — transform stuff, then reduce it, optionally in parallel, optionally with your own ops. let's get into it ✨

✨ SYNOPSIS ✨

so first of all, she's defined in the header <numeric> 🎀 and uh, there are six of her. six overloads. she's not subtle. let's meet them:

template< class InputIt1, class InputIt2, class T >
T transform_reduce( InputIt1 first1, InputIt1 last1,
                    InputIt2 first2, T init );

(1) (since C++17) (constexpr since C++20)

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class T >
T transform_reduce( ExecutionPolicy&& policy,
                    ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, T init );

(2) (since C++17)

template< class InputIt1, class InputIt2, class T,
          class BinaryOp1, class BinaryOp2 >
T transform_reduce( InputIt1 first1, InputIt1 last1,
                    InputIt2 first2, T init,
                    BinaryOp1 reduce, BinaryOp2 transform );

(3) (since C++17) (constexpr since C++20)

template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2, class T,
          class BinaryOp1, class BinaryOp2 >
T transform_reduce( ExecutionPolicy&& policy,
                    ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, T init,
                    BinaryOp1 reduce, BinaryOp2 transform );

(4) (since C++17)

template< class InputIt, class T,
          class BinaryOp, class UnaryOp >
T transform_reduce( InputIt first, InputIt last, T init,
                    BinaryOp reduce, UnaryOp transform );

(5) (since C++17) (constexpr since C++20)

template< class ExecutionPolicy,
          class ForwardIt, class T,
          class BinaryOp, class UnaryOp >
T transform_reduce( ExecutionPolicy&& policy,
                    ForwardIt first, ForwardIt last, T init,
                    BinaryOp reduce, UnaryOp transform );

(6) (since C++17)

🦋 what each overload actually does 🦋

1) this one is literally equivalent to transform_reduce(first1, last1, first2, init, std::plus<>(), std::multiplies<>()) — she's the effectively parallelized version of the default std::inner_product. no cap 💅

3) applies transform to each pair of elements from the ranges [first1, last1) and the range of std::distance(first1, last1) elements starting from first2, and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.

⚠️ the result is non-deterministic if the reduce is not associative or not commutative (such as floating-point addition). like, she's allowed to shuffle. that's the vibe. don't come for her when 0.1 + 0.2 acts up 🙈

if any of the following values is not convertible to T, the program is ill-formed:

reduce(init, init)
reduce(init, transform(*first1, *first2))
reduce(transform(*first1, *first2), init)
reduce(transform(*first1, *first2), transform(*first1, *first2))

given last2 as the std::distance(first1, last1)th next iterator of first2, if any of the following conditions is satisfied, the behavior is undefined (💀 not a good time):

T is not MoveConstructible.
transform or reduce modifies any element of [first1, last1) or [first2, last2).
transform or reduce invalidates any iterator or subrange of [first1, last1] or [first2, last2).

5) applies transform to each element in the range [first, last) and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.

⚠️ same deal: the result is non-deterministic if the reduce is not associative or not commutative (such as floating-point addition).

if any of the following values is not convertible to T, the program is ill-formed:

reduce(init, init)
reduce(init, transform(*first))
reduce(transform(*first), init)
reduce(transform(*first), transform(*first))

if any of the following conditions is satisfied, the behavior is undefined:

T is not MoveConstructible.
transform or reduce modifies any element of [first, last).
transform or reduce invalidates any iterator or subrange of [first, last].

2, 4, 6) same as (1, 3, 5), but executed according to policy 🏃‍♀️💨

these overloads participate in overload resolution only if:

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true. (until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true. (since C++20)

🌸 PARAMETERS 🌸

first1, last1 — the range of elements to be taken as the left operand of transform
first2 — the start of range of elements to be taken as the right operand of transform
first, last — the range of elements to be taken as the operand of transform
init — the initial value of the generalized sum
policy — the execution policy to use. see execution policy for details 👀
reduce — binary FunctionObject that will be applied in unspecified order to the results of transform, the results of other reduce and init.
transform — unary or binary FunctionObject that will be applied to each element of the input range(s). the return type must be acceptable as input to reduce.

💜 TYPE REQUIREMENTS 💜

InputIt1, InputIt2, InputIt must meet the requirements of LegacyInputIterator.
ForwardIt1, ForwardIt2, ForwardIt must meet the requirements of LegacyForwardIterator.

👑 RETURN VALUE 👑

1, 2) the generalized sum of init and values over std::plus<>(), where values are the values transformed by std::multiplies<>(), each value is transformed from a pair of elements from the two input ranges.

3, 4) the generalized sum of init and values over reduce, where values are the values transformed by transform, each value is transformed from a pair of elements from the two input ranges.

5, 6) the generalized sum of init and values over reduce, where values are the values transformed by transform, each value is transformed from an element from the input range.

now, the generalized sum of a group of elements over an binary operation binary_op is defined as follows (this is the part everyone skips, don't be that person 🫶):

if the group only has one element, the sum is the value of the element.
otherwise, performs the following operations in order:
1. takes any two elements elem1 and elem2 from the group.
2. calculates binary_op(elem1, elem2) and puts the result back to the group.
3. repeats steps 1 and 2 until there is only one element in the group.

🔥 COMPLEXITY 🔥

given N as std::distance(first1, last1) (or std::distance(first, last) for overloads (5,6)) — don't come for my notation, it's just N bestie:

1, 2) O(N) applications of std::plus<>() and std::multiplies<>() respectively.
3–6) O(N) applications of reduce and transform respectively.

💀 EXCEPTIONS 💀

the overloads with a template parameter named ExecutionPolicy report errors as follows:

if execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. for any other ExecutionPolicy, the behavior is implementation-defined 🫠
if the algorithm fails to allocate memory, std::bad_alloc is thrown.

🎀 NOTES 🎀

transform is never applied to init. like, ever. she said not today 💅

if first == last or first1 == last1, init is returned, unmodified. empty range? you get your init back, untouched, iconic.

⭐ EXAMPLE ⭐

transform_reduce can be used to parallelize std::inner_product 🏃‍♀️ some systems may need additional support to get advantages of parallel execution. e.g., on GNU/Linux, the Intel TBB be installed and -ltbb option be provided to gcc/clang compiler.

// Run this code

#if PARALLEL
#include <execution>
#define PAR std::execution::par,
#else
#define PAR
#endif

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <locale>
#include <numeric>
#include <vector>

// to parallelize non-associate accumulative operation, you'd better choose
// transform_reduce instead of reduce; e.g., a + b * b != b + a * a
void print_sum_squared(long const num)
{
    std::cout.imbue(std::locale{"en_US.UTF8"});
    std::cout << "num = " << num << '\n';

    // create an immutable vector filled with pattern: 1,2,3,4, 1,2,3,4 ...
    const std::vector<long> v{[n = num * 4] {
        std::vector<long> v;
        v.reserve(n);
        std::generate_n(std::back_inserter(v), n,
            [i = 0]() mutable { return 1 + i++ % 4; });
        return v;
    }()};

    auto squared_sum = [](auto sum, auto val) { return sum + val * val; };

    auto sum1 = std::accumulate(v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "accumulate(): " << sum1 << '\n';

    auto sum2 = std::reduce(PAR v.cbegin(), v.cend(), 0L, squared_sum);
    std::cout << "reduce(): " << sum2 << '\n';

    auto sum3 = std::transform_reduce(PAR v.cbegin(), v.cend(), 0L, std::plus{},
                                      [](auto val) { return val * val; });
    std::cout << "transform_reduce(): " << sum3 << "\n\n";
}

int main()
{
    print_sum_squared(1);
    print_sum_squared(1'000);
    print_sum_squared(1'000'000);
}

🌈 possible output 🌈

and this is the moment, the payoff, the reason reduce gets a bad rep and transform_reduce gets a crown 👑:

num = 1
accumulate(): 30
reduce(): 30
transform_reduce(): 30

num = 1,000
accumulate(): 30,000
reduce(): -7,025,681,278,312,630,348
transform_reduce(): 30,000

num = 1,000,000
accumulate(): 30,000,000
reduce(): -5,314,886,882,370,003,032
transform_reduce(): 30,000,000

like. reduce() really said "let me rearrange your float additions and ruin your whole life" 😭 transform_reduce said "i got you bestie, i'll add in a sane order." that's the whole lesson fr fr.

// Compile-options for parallel execution on POSIX:
// g++ -O2 -std=c++17 -Wall -Wextra -pedantic -DPARALLEL ./example.cpp -ltbb -o tr; ./tr

💖 SEE ALSO 💖

okay bestie, these are the other algorithm girlies in the same friend group — go give them a follow:

accumulate — sums up or folds a range of elements (function template) 🌸 — like, the original, the classic, the one that does it in order.
transform — applies a function to a range of elements, storing results in a destination range (function template) ✨ — the "make it a whole new range" icon.
reduce — similar to std::accumulate, except out of order (C++17) (function template) 🔥 — same energy as accumulate but chaotic (respectfully), so don't go assuming the order, iykyk.

okay that's the whole page, bestie 🫶 everything from the #include to the SEE ALSO is officially yours now. no cap.

that's it, that's the vibe — page's done, go compile something iconic 💅✨

this lil legend came straight from http://cppreference.com, version 2024.06.10, dated 2024.06.10 — so if it's out of date by the time you read it, that's between you and the site, not me 😭🎀

periodt. 💜

📦 where this page comes from

nixpkgs unstable: stdman 2024.07.05
opensuse-leap 16.0: stdman 2024.07.05-bp160.1.9 · MIT
💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash-1017 on 2026-11-04: a language model's rewrite of the original, under its terms

std::transform_reduce(3)