C++ <numeric>: accumulate vs reduce, transform_reduce, Scans and the Init-Type Trap
Key takeaways
accumulate folds strictly left to right in the type of its init value; reduce may regroup and reorder, which enables parallelism but changes floating-point results and forbids non-associative operations.
<numeric> looks like the boring corner of the standard library: sums, products, prefix sums. In practice it is where a surprising number of subtle bugs live, because two functions that look interchangeable, std::accumulate and std::reduce, make very different promises, and because the type of the initial value quietly decides the type of the whole computation.
All examples below were compiled with g++ -std=c++20 and the outputs shown are what they printed.
accumulate: a left fold in the type of init
std::accumulate(first, last, init, op) computes op(...op(op(init, a0), a1)..., an), strictly left to right. The default op is +.
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
std::cout << std::accumulate(v.begin(), v.end(), 0) << '\n'; // 15
std::cout << std::accumulate(v.begin(), v.end(), 1, std::multiplies<>()) << '\n'; // 120
std::vector<std::string> words = {"Hello", " ", "World", "!"};
std::cout << std::accumulate(words.begin(), words.end(), std::string{}) << '\n'; // Hello World!
}Because the order is fixed, accumulate also works with operations that are not associative. Folding subtraction from the left, ((10 - 1) - 2) - 3, is well defined and gives 4. That is exactly the kind of operation reduce is not allowed to receive.
The init type is the accumulator type
The signature is T accumulate(InputIt, InputIt, T init). T is deduced from init, not from the elements, and every intermediate result is stored in a T.
std::vector<double> d = {0.5, 1.5, 2.5};
std::accumulate(d.begin(), d.end(), 0); // 3 -- int: 0+0.5 -> 0, 0+1.5 -> 1, 1+2.5 -> 3
std::accumulate(d.begin(), d.end(), 0.0); // 4.5
std::vector<int> big = {2000000000, 2000000000};
std::accumulate(big.begin(), big.end(), 0); // signed int overflow: undefined behavior
std::accumulate(big.begin(), big.end(), 0LL); // 4000000000
std::vector<int> neg = {-1, -2};
std::accumulate(neg.begin(), neg.end(), 0u); // 4294967293 -- the fold is done in unsignedThis is the <numeric> bug I have hit most often: summing prices stored as double with a literal 0, getting a plausible-looking integer, and not noticing for a while because the test data happened to be whole numbers. Do not count on a warning: the double-to-int conversion happens inside a standard library header, and GCC 10 printed nothing for it even with -Wall -Wextra -Wconversion. A habit that avoids the whole class: write the init with an explicit type, such as 0.0, 0LL, std::int64_t{0} or std::string{}.
Two smaller notes. Since C++20, accumulate moves the accumulator into each call (init = std::move(init) + *first), so concatenating strings this way is no longer quadratic in copies. And accumulate returns init for an empty range, which is usually what you want for sums but can hide the fact that you had no data.
reduce: permission to regroup
std::reduce (C++17) computes the same generalized sum, but the standard allows it to group and reorder operands arbitrarily. That freedom is what lets an implementation split the range across threads or SIMD lanes. The price is a precondition: the operation must be associative and commutative, otherwise the result is unspecified.
#include <execution>
#include <numeric>
#include <vector>
std::vector<int> ones(1000000, 1);
int a = std::reduce(ones.begin(), ones.end(), 0); // 1000000
int b = std::reduce(std::execution::par, ones.begin(), ones.end(), 0); // 1000000The permission to reorder applies even to the overload without an execution policy. std::reduce(v.begin(), v.end(), 0.0) is not a drop-in replacement for accumulate when you need bit-for-bit reproducible floating-point results.
Why regrouping matters for floating point
Integer addition is associative, so any grouping gives the same answer (as long as nothing overflows). Floating-point addition is not:
std::vector<float> f = {1e8f, 1.0f, -1e8f, 1.0f};
float left = std::accumulate(f.begin(), f.end(), 0.0f); // 1
float regrouped = (f[0] + f[2]) + (f[1] + f[3]); // 2In the left fold, 1e8f + 1.0f rounds back to 1e8f because a float has only about seven significant decimal digits, so one of the 1.0f values disappears. A different grouping cancels the large values first and keeps both. reduce is allowed to pick either grouping, and a parallel run may pick differently depending on how the range is split. For sums of values with similar magnitude the difference is usually in the last bits, but if you compare results against stored golden values or require identical output across runs, use accumulate, or sort and sum deliberately.
Operations reduce must not receive
Subtraction, division, string concatenation where order matters, and “keep the first element that…” style lambdas are all non-commutative or non-associative. They compile fine with reduce and may even produce the expected result on a small test, which is the dangerous part. The rule of thumb: if swapping two elements of the input could change the answer, use accumulate.
transform_reduce: map then reduce without a temporary
std::transform_reduce applies a transformation to each element (or pair of elements) and reduces the results, without materializing an intermediate vector. It has the same reordering permission as reduce.
With two ranges and no operations given, it computes a dot product: init + sum(a[i] * b[i]).
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {2, 2, 2, 2, 2};
int dot = std::transform_reduce(v1.begin(), v1.end(), v2.begin(), 0); // 30
// Unary form: reduce op first, then transform
int squares = std::transform_reduce(v1.begin(), v1.end(), 0, std::plus<>(),
[](int x) { return x * x; }); // 55Note the argument order in the unary form: init, then the reduction, then the transformation. Getting those two swapped often still compiles for simple int lambdas and yields a wrong answer.
A weighted average is a direct application:
double weighted_average(const std::vector<double>& values,
const std::vector<double>& weights) {
double weighted = std::transform_reduce(values.begin(), values.end(),
weights.begin(), 0.0);
double total = std::reduce(weights.begin(), weights.end(), 0.0);
return weighted / total;
}
// values {85, 90, 78, 92}, weights {0.3, 0.3, 0.2, 0.2} -> 86.5And the sample variance, which needs two passes (mean first, then squared deviations):
std::vector<double> scores = {85, 90, 78, 92, 88, 76, 95};
double mean = std::reduce(scores.begin(), scores.end(), 0.0) / scores.size();
double ss = std::transform_reduce(scores.begin(), scores.end(), 0.0, std::plus<>(),
[mean](double x) { double d = x - mean; return d * d; });
double variance = ss / (scores.size() - 1);
// mean 86.2857, variance 50.2381, std dev 7.08788std::inner_product is the C++98 predecessor of the two-range form. It is guaranteed to evaluate in order, and it accepts custom “outer” and “inner” operations:
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32
std::inner_product(a.begin(), a.end(), b.begin(), 1,
std::multiplies<>(), std::plus<>()); // (1+4)*(2+5)*(3+6) = 315Both inner_product and the two-range transform_reduce read last1 - first1 elements from the second range without checking its size. A shorter second vector is undefined behavior, not an error.
Prefix sums: partial_sum and the scans
std::partial_sum writes running totals. inclusive_scan computes the same thing but, like reduce, may regroup, which is what makes a parallel prefix sum possible. exclusive_scan shifts the result by one and starts from the init value.
std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> out(v.size());
std::partial_sum(v.begin(), v.end(), out.begin()); // 1 3 6 10 15
std::inclusive_scan(v.begin(), v.end(), out.begin()); // 1 3 6 10 15
std::exclusive_scan(v.begin(), v.end(), out.begin(), 0); // 0 1 3 6 10exclusive_scan is the natural tool for converting counts into offsets: if bucket i has count[i] items, exclusive_scan gives the starting index of each bucket. std::adjacent_difference is the inverse of partial_sum: applied to 1 3 6 10 15 it returns 1 2 3 4 5 (the first element is copied as is).
A common use is answering many range-sum queries. Store a prefix array with a leading zero, and each window is one subtraction:
std::vector<double> moving_average(const std::vector<double>& data, std::size_t k) {
if (k == 0 || data.size() < k) return {};
std::vector<double> prefix(data.size() + 1, 0.0);
std::partial_sum(data.begin(), data.end(), prefix.begin() + 1);
std::vector<double> out;
out.reserve(data.size() - k + 1);
for (std::size_t i = k; i < prefix.size(); ++i)
out.push_back((prefix[i] - prefix[i - k]) / k);
return out;
}
// {100, 102, 101, 105, 103, 107, 110}, k = 3 -> 101 102.667 103 105 106.667partial_sum has an accumulator-type subtlety of its own: the running value uses the input iterator’s value type. Running partial_sum over the bytes {200, 100, 50} into a vector<int> prints 200 44 94, because the running total is kept in unsigned char and wraps at 256. std::inclusive_scan(b.begin(), b.end(), out.begin(), std::plus<>(), 0) takes an init value (after the operation) and accumulates in its type, printing 200 300 350. (accumulate with an int init does not have this problem: summing {200, 100, 50} with init 0 gives 350.)
iota, gcd, lcm, midpoint
std::iota fills a range with increasing values, most often to build an index array that you then sort by some key:
std::vector<int> idx(5);
std::iota(idx.begin(), idx.end(), 0); // 0 1 2 3 4
std::sort(idx.begin(), idx.end(), [&](int i, int j) { return key[i] < key[j]; });<numeric> also has std::gcd and std::lcm (C++17) and std::midpoint (C++20). std::midpoint(a, b) computes the midpoint without the overflow that (a + b) / 2 suffers near the type’s limit: std::midpoint(2147483647, 2147483645) returns 2147483646, while the naive expression overflows int. For odd differences it rounds toward a.
Execution policies: what par actually buys you
std::execution::seq, par and par_unseq can be passed as the first argument to reduce, transform_reduce, the scans and most other algorithms. A few facts that are easy to miss:
- Toolchain support varies. MSVC implements the parallel policies itself. GCC’s libstdc++ uses Intel TBB as the backend, so you normally need TBB installed and linked with
-ltbb; without it, some versions fall back to serial execution. Clang with libc++ has had incomplete support for a long time. See C++17 parallel algorithms for details. - Parallel overloads need forward iterators. Input iterators such as
std::istream_iteratoronly work with the non-policy overloads. - Exceptions call
std::terminate. If the operation throws inside a policy-based algorithm, the program ends rather than propagating the exception. par_unseqforbids locks. The operation may be interleaved on a single thread, so taking a mutex inside it can deadlock.- Small inputs are often slower. Thread dispatch has a fixed cost. Whether parallel reduction wins depends on data size, the cost of each operation, memory bandwidth and core count, so measure on your target machine rather than trusting a published speedup.
The classic mistake is reaching for a parallel for_each and a shared counter:
int counter = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
[&](int x) { counter += x; }); // data race: undefined behavior
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0); // correctAn std::atomic<int> counter fixes the race but serializes every update on one cache line; reduce lets each worker keep a private partial sum and combines them at the end, which is the whole point of the algorithm.
Choosing quickly
- Order matters, the operation is not associative, or you need reproducible floating-point output:
accumulate/inner_product/partial_sum. - Associative and commutative operation, large data, possibly parallel:
reduce/transform_reduce/inclusive_scan. - Need a per-element transformation before summing:
transform_reduceinstead oftransforminto a temporary followed by a sum. - Whatever you pick, write the init value with the type you want the result to have.