Ch8.7: Numeric Algorithms

Overview

The header <numeric> provides algorithms for combining elements: summing, reducing, computing prefix results, and more. These algorithms are simple but extremely useful in everyday programming.

In this chapter, you will learn:

• accumulate
• reduce
• transform_reduce
• partial_sum
• inclusive_scan and exclusive_scan

1. accumulate

accumulate processes elements from left to right and combines them with a binary operation. It always requires an initial value.

::fast_io::vector<int> v{1, 2, 3, 4};

int sum = ::std::accumulate(
    v.begin(), v.end(),
    0,
    ::std::plus<>()
);

print("sum = ", sum, "\n");

You can compute a product using std::multiplies<>:

int product = ::std::accumulate(
    v.begin(), v.end(),
    1,
    ::std::multiplies<>()
);

Be careful: the initial value changes the result. For example, summing integers starting from 1 instead of 0 produces a different total. This is one reason why reduce is often preferred.

2. reduce

reduce is similar to accumulate but is designed for parallel execution. Unlike accumulate, it does not require an initial value. If omitted, the first element is used.

int sum = ::std::reduce(
    v.begin(), v.end(),
    ::std::plus<>()
);

You may also provide an initial value explicitly:

int sum2 = ::std::reduce(
    v.begin(), v.end(),
    0,
    ::std::plus<>()
);

Because the order of combination is unspecified, the operation must be associative.

Why prefer reduce? Because it avoids the common mistake of choosing the wrong initial value. With accumulate, forgetting the initial value silently changes the result. With reduce, the default behavior is usually correct.

3. transform_reduce

transform_reduce combines a projection and a reduction. It applies a transformation to each element, then reduces the results.

int total = ::std::transform_reduce(
    v.begin(), v.end(),
    0,
    ::std::plus<>(),
    [](int x) { return x * x; }   // projection: square
);

print("sum of squares = ", total, "\n");

The reduction uses a functional object. The projection may be a lambda or a pointer-to-member.

4. partial_sum

partial_sum computes prefix sums:

::fast_io::vector<int> out(v.size());

::std::partial_sum(
    v.begin(), v.end(),
    out.begin(),
    ::std::plus<>()
);

If v = {1,2,3,4}, then out = {1,3,6,10}.

5. inclusive_scan and exclusive_scan

These are the modern, ranges-friendly versions of prefix operations.

::std::inclusive_scan(
    v.begin(), v.end(),
    out.begin(),
    ::std::plus<>()
);

::std::exclusive_scan(
    v.begin(), v.end(),
    out.begin(),
    0,
    ::std::plus<>()
);

inclusive_scan includes the current element. exclusive_scan does not.

Key takeaways

• accumulate always requires an initial value.
• reduce does not require an initial value and avoids common mistakes.
• reduce is parallel-friendly and uses associative operations.
• transform_reduce combines projection and reduction.
• partial_sum and scans compute prefix results.
• Use functional objects (std::plus<>, std::multiplies<>) for binary operations.
• Use &Item::member for simple projections.