std::transform_reduce

 

C++

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)

Metaprogramming library (C++11)

Diagnostics library

General utilities library

Strings library

Containers library

Iterators library

Ranges library (C++20)

Algorithms library

Numerics library

Localizations library

Input/output library

Filesystem library (C++17)

Regular expressions library (C++11)

Concurrency support library (C++11)

Technical specifications

Symbols index

External libraries

 

Algorithm library

Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
is_execution_policy (C++17)	execution::seqexecution::parexecution::par_unseqexecution::unseq (C++17)(C++17)(C++17)(C++20)	execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced (C++17)(C++17)(C++17)(C++20)
Non-modifying sequence operations
all_ofany_ofnone_of (C++11)(C++11)(C++11) for_each for_each_n (C++17)	countcount_if mismatch equal adjacent_find	search search_n lexicographical_compare lexicographical_compare_three_way (C++20)	findfind_iffind_if_not (C++11) find_end find_first_of
Modifying sequence operations
copycopy_if (C++11) copy_n (C++11) copy_backward move (C++11) move_backward (C++11) shift_leftshift_right (C++20)(C++20) transform	fill fill_n generate generate_n swap iter_swap swap_ranges sample (C++17)	removeremove_if replacereplace_if reverse rotate unique random_shuffle (until C++17)	remove_copyremove_copy_if replace_copyreplace_copy_if reverse_copy rotate_copy unique_copy shuffle (C++11)
Partitioning operations
is_partitioned (C++11) partition_point (C++11)	partition partition_copy (C++11)	stable_partition
Sorting operations
is_sorted (C++11) is_sorted_until (C++11)	sort stable_sort	partial_sort partial_sort_copy	nth_element
Binary search operations
lower_bound	upper_bound	binary_search	equal_range
Set operations (on sorted ranges)
merge inplace_merge	set_difference set_intersection	set_symmetric_difference set_union	includes
Heap operations
is_heap (C++11) is_heap_until (C++11)	make_heap sort_heap	push_heap pop_heap
Minimum/maximum operations
max max_element	min min_element	minmax (C++11) minmax_element (C++11)	clamp (C++17)
Permutations
is_permutation (C++11)	next_permutation	prev_permutation
Numeric operations
iota (C++11) inner_product adjacent_difference	accumulate reduce (C++17) transform_reduce (C++17)	transform_inclusive_scan (C++17) transform_exclusive_scan (C++17)	partial_sum inclusive_scan (C++17) exclusive_scan (C++17)
Operations on uninitialized storage
uninitialized_copy uninitialized_move (C++17) uninitialized_fill	uninitialized_copy_n (C++11) uninitialized_move_n (C++17) uninitialized_fill_n	uninitialized_default_construct (C++17) uninitialized_value_construct (C++17) uninitialized_default_construct_n (C++17) uninitialized_value_construct_n (C++17)	destroy (C++17) destroy_n (C++17) destroy_at (C++17) construct_at (C++20)
C library
qsort	bsearch

 

Defined in header <numeric>
	(1)
template< class InputIt1, class InputIt2, class T > T transform_reduce( InputIt1 first1, InputIt1 last1,                     InputIt2 first2,                     T init );			(since C++17) (until C++20)
template< class InputIt1, class InputIt2, class T > constexpr T transform_reduce( InputIt1 first1, InputIt1 last1,                     InputIt2 first2,                     T init );			(since C++20)
		(2)
template< class InputIt1, class InputIt2,           class T,           class BinaryReductionOp,           class BinaryTransformOp > T transform_reduce( InputIt1 first1, InputIt1 last1,                     InputIt2 first2,                     T init,                     BinaryReductionOp reduce,                     BinaryTransformOp transform );				(since C++17) (until C++20)
template< class InputIt1, class InputIt2,           class T,           class BinaryReductionOp,           class BinaryTransformOp > constexpr T transform_reduce( InputIt1 first1, InputIt1 last1,                     InputIt2 first2,                     T init,                     BinaryReductionOp reduce,                     BinaryTransformOp transform );				(since C++20)
			(3)
template< class InputIt,           class T,           class BinaryReductionOp,           class UnaryTransformOp > T transform_reduce( InputIt first, InputIt last,                     T init,                     BinaryReductionOp reduce,                     UnaryTransformOp transform );					(since C++17) (until C++20)
template< class InputIt, class T,           class BinaryReductionOp,           class UnaryTransformOp > constexpr T transform_reduce( InputIt first, InputIt last,                     T init,                     BinaryReductionOp reduce,                     UnaryTransformOp transform );					(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 );				(4)	(since C++17)
template< class ExecutionPolicy,           class ForwardIt1, class ForwardIt2, class T,           class BinaryReductionOp,           class BinaryTransformOp > T transform_reduce( ExecutionPolicy&& policy,                     ForwardIt1 first1, ForwardIt1 last1,                     ForwardIt2 first2,                     T init,                     BinaryReductionOp reduce,                     BinaryTransformOp transform );				(5)	(since C++17)
template< class ExecutionPolicy,           class ForwardIt, class T,           class BinaryReductionOp,           class UnaryTransformOp > T transform_reduce( ExecutionPolicy&& policy,                     ForwardIt first, ForwardIt last,                     T init,                     BinaryReductionOp reduce,                     UnaryTransformOp transform );				(6)	(since C++17)

1) Equivalent to std::transform_reduce(first1, last1, first2, init, std::plus<>(), std::multiplies<>());, effectively parallelized version of the default std::inner_product.

2) Applies transform to each pair of elements from the ranges [first, last) and the range starting at first2 and reduces the results (possibly permuted and aggregated in unspecified manner) along with the initial value init over reduce.

3) 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.

4-6) Same as (1-3), but executed according to policy. These overloads do not participate in overload resolution unless

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)

The behavior is non-deterministic if reduce is not associative or not commutative.

The behavior is undefined if reduce, or transform modifies any element or invalidates any iterator in the input ranges, including their end iterators.

Parameters

first, last	-	the range of elements to apply the algorithm to
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
- T must meet the requirements of MoveConstructible in order to use overloads (3,6). and the result of the expressions reduce(init, transform(*first)), reduce(transform(*first), init), reduce(init, init), and reduce(transform(*first), transform(*first)) must be convertible to T.
- T must meet the requirements of MoveConstructible in order to use overloads (2,5). and the result of the expressions reduce(init, transform(*first1, *first2)), reduce(transform(*first1, *first2), init), reduce(init, init), and reduce(transform(*first1, *first2), transform(*first1, *first2)) must be convertible to T.
- InputIt must meet the requirements of LegacyInputIterator.
- ForwardIt must meet the requirements of LegacyForwardIterator.

Return value

2) Generalized sum of init and transform(*first, *first2), transform(*(first + 1), *(first2 + 1)), ..., over reduce.

3) Generalized sum of init and transform(*first), transform(*(first + 1)), ... transform(*(last - 1)) over reduce,

where generalized sum GSUM(op, a
1, ..., a
N) is defined as follows:

• if N = 1, a
  1
• if N > 1, op(GSUM(op, b
  1, ..., b
  K), GSUM(op, b
  M, ..., b
  N)) where

• b
  1, ..., b
  N may be any permutation of a1, ..., aN and
• 1 < K + 1 = M ≤ N

in other words, the results of transform or of reduce may be grouped and arranged in arbitrary order.

Complexity

1,2,4,5) O(last1 - first1) applications each of reduce and transform.

3,6) O(last - first) applications each of transform and reduce.

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

In the unary-binary overload (3,6), transform is not applied to init.

If first == last or first1 == last1, init is returned, unmodified.

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:

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

See also

accumulate	sums up or folds a range of elements (function template)
transform	applies a function to a range of elements, storing results in a destination range (function template)
reduce (C++17)	similar to std::accumulate, except out of order (function template)