Scan Operations

Overview

Scan algorithms live in <numeric> and come in two generations. C++98 introduced std::partial_sum, which computes a strict left-to-right fold at each position. C++17 added four new algorithms — std::inclusive_scan, std::exclusive_scan, std::transform_inclusive_scan, and std::transform_exclusive_scan — formulated to allow parallel execution.

The key difference between generations is not just parallelism. std::partial_sum applies the binary operation in guaranteed left-to-right order, so the operation need not be associative. The C++17 algorithms require an associative binary operation — not necessarily commutative — which gives the scheduler freedom to split and merge sub-ranges arbitrarily. Passing a non-associative operation to a C++17 scan with a parallel execution policy is undefined behaviour.

The inclusive/exclusive axis describes what element is counted at position i:

• Inclusive: output[i] accumulates input[0..i] — the current element is included.
• Exclusive: output[i] accumulates input[0..i-1] — the current element is excluded; output[0] takes an explicit init value.

For input {1, 2, 3, 4} with addition and init = 0:

inclusive: {1, 3, 6, 10}
exclusive: {0, 1, 3, 6}

The exclusive form shifts the scan forward by one slot. This makes it the natural choice for computing per-segment write offsets in parallel algorithms: each worker reads its starts[i] without a separate coordination pass.

Syntax

#include <numeric>
#include <execution>  // C++17: execution policies

// C++98 — sequential; op need not be associative
template<class InIt, class OutIt>
OutIt partial_sum(InIt first, InIt last, OutIt result);

template<class InIt, class OutIt, class BinaryOp>
OutIt partial_sum(InIt first, InIt last, OutIt result, BinaryOp op);

// C++17 — inclusive scan; op must be associative
template<class InIt, class OutIt>
OutIt inclusive_scan(InIt first, InIt last, OutIt result);

template<class InIt, class OutIt, class BinaryOp>
OutIt inclusive_scan(InIt first, InIt last, OutIt result, BinaryOp op);

template<class InIt, class OutIt, class BinaryOp, class T>
OutIt inclusive_scan(InIt first, InIt last, OutIt result, BinaryOp op, T init);

// C++17 — exclusive scan; init is mandatory
template<class InIt, class OutIt, class T>
OutIt exclusive_scan(InIt first, InIt last, OutIt result, T init);

template<class InIt, class OutIt, class T, class BinaryOp>
OutIt exclusive_scan(InIt first, InIt last, OutIt result, T init, BinaryOp op);

// C++17 — transform then inclusive scan
template<class InIt, class OutIt, class BinaryOp, class UnaryOp>
OutIt transform_inclusive_scan(InIt first, InIt last, OutIt result,
                                BinaryOp binary_op, UnaryOp unary_op);

template<class InIt, class OutIt, class BinaryOp, class UnaryOp, class T>
OutIt transform_inclusive_scan(InIt first, InIt last, OutIt result,
                                BinaryOp binary_op, UnaryOp unary_op, T init);

// C++17 — transform then exclusive scan; note: init precedes the ops
template<class InIt, class OutIt, class T, class BinaryOp, class UnaryOp>
OutIt transform_exclusive_scan(InIt first, InIt last, OutIt result,
                                T init, BinaryOp binary_op, UnaryOp unary_op);

Every C++17 algorithm has an overload family prefixed with an ExecutionPolicy argument (std::execution::seq, par, par_unseq).

Examples

Segment offset computation

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> sizes{3, 1, 4, 1, 5, 9};

    std::vector<int> ends(sizes.size());
    std::inclusive_scan(sizes.begin(), sizes.end(), ends.begin()); // C++17
    // ends: {3, 4, 8, 9, 14, 23}

    std::vector<int> starts(sizes.size());
    std::exclusive_scan(sizes.begin(), sizes.end(), starts.begin(), 0); // C++17
    // starts: {0, 3, 4, 8, 9, 14}

    for (std::size_t i = 0; i < sizes.size(); ++i)
        std::cout << "[" << starts[i] << ", " << ends[i] << ")\n";
}

The exclusive/inclusive pair together provides both endpoints of each half-open interval in a single pass — the canonical pattern for partitioning a flat buffer among variable-length segments.

Running product with partial_sum

#include <numeric>
#include <vector>
#include <functional>

// C++98: compute factorials in-place — [1!, 2!, 3!, 4!, 5!]
std::vector<int> v{1, 2, 3, 4, 5};
std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>{});
// v: {1, 2, 6, 24, 120}

Because std::partial_sum is strictly sequential, it is safe for non-associative operations. Avoid substituting inclusive_scan here without verifying associativity.

Parallel prefix sum on large data

#include <numeric>
#include <execution>  // C++17
#include <vector>

std::vector<double> data(10'000'000);
// ... fill data ...

std::vector<double> prefix(data.size());
std::inclusive_scan(
    std::execution::par_unseq,   // C++17: parallel + vectorisable
    data.begin(), data.end(),
    prefix.begin()
);

With par_unseq, the runtime may reorder and interleave operations freely. For IEEE 754 doubles, this means results can diverge from a sequential scan at the ULP level due to floating-point non-associativity.

Fused transform scan: cumulative energy

#include <numeric>
#include <vector>

std::vector<double> signal{1.0, 2.0, 3.0, 4.0, 5.0};
std::vector<double> energy(signal.size());

// C++17: square each element, then accumulate — no intermediate buffer
std::transform_inclusive_scan(
    signal.begin(), signal.end(),
    energy.begin(),
    std::plus<double>{},                      // accumulation op
    [](double x) { return x * x; }           // per-element transform
);
// energy: {1, 5, 14, 30, 55}

Fusing the transform with the scan avoids a temporary allocation and improves cache utilisation relative to a separate std::transform followed by std::inclusive_scan.

Exclusive scan with a non-additive identity

#include <numeric>
#include <limits>
#include <vector>
#include <algorithm>

// Prefix-max: output[i] = max of input[0..i-1]
std::vector<int> vals{3, 1, 4, 1, 5, 9, 2, 6};
std::vector<int> prefix_max(vals.size());

std::exclusive_scan(                          // C++17
    vals.begin(), vals.end(),
    prefix_max.begin(),
    std::numeric_limits<int>::min(),          // identity for max
    [](int a, int b) { return std::max(a, b); }
);
// prefix_max: {INT_MIN, 3, 3, 4, 4, 5, 9, 9}

Best Practices

Prefer the C++17 algorithms over partial_sum for new code. inclusive_scan and exclusive_scan make the inclusive/exclusive distinction explicit, support execution policies, and compose cleanly with the rest of the C++17 parallel algorithm suite. Reserve partial_sum only when the operation is non-associative or when you must target C++14 and earlier.

Always supply a correct identity element for non-additive operations. For exclusive_scan and transform_exclusive_scan, init seeds the very first output slot. An incorrect identity silently corrupts every output element. For multiplication use 1; for bitwise AND use ~0; for max use std::numeric_limits<T>::min().

In-place writes are legal. All scan algorithms allow result == first when the range is contiguous, which avoids a second allocation:

std::inclusive_scan(v.begin(), v.end(), v.begin()); // C++17, in-place: valid

Match the execution policy to your operation's cost. par_unseq pays off on large contiguous ranges with cheap, branchless binary ops. For operations with significant per-element overhead (virtual calls, heap allocation), par without unseq is often the better choice.

Common Pitfalls

exclusive_scan has no overload without init. Unlike inclusive_scan, every exclusive_scan overload requires an explicit initial value. Failing to provide it or passing the wrong type is a compile error; passing a semantically wrong value is a silent correctness bug.

partial_sum and inclusive_scan are not interchangeable for floating-point. On a conforming implementation both are correct, but they are not required to produce the same bit pattern. More critically, passing a non-associative op to inclusive_scan with par or par_unseq is undefined behaviour — the standard is explicit on this.

Argument order diverges between transform_inclusive_scan and transform_exclusive_scan. In transform_inclusive_scan, init is the last argument (and optional). In transform_exclusive_scan, init precedes both the binary and unary operations. This asymmetry is a persistent source of compile errors; always consult the signature before writing.

Parallelism does not guarantee reproducibility. A parallel scan over double may produce results that differ from a sequential one by more than floating-point rounding noise, depending on the scheduler's choice of merge order. For reproducibility-critical domains, pass std::execution::seq explicitly.

Inclusive vs Exclusive: Side-by-Side

The inclusive/exclusive distinction is the single most important concept to internalise before reaching for any scan. The table below fixes it concretely for input [1, 2, 3, 4] with addition.

The exclusive result is the inclusive result shifted right by one slot, with init filling the vacated first position. This shift is precisely what makes the exclusive form useful for write-offset computation: starts[i] is the byte (or element) address where segment i should begin writing, with no need to subtract anything afterward.

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> input{1, 2, 3, 4};

    std::vector<int> incl(input.size());
    std::inclusive_scan(input.begin(), input.end(), incl.begin());
    // incl: {1, 3, 6, 10}

    std::vector<int> excl(input.size());
    std::exclusive_scan(input.begin(), input.end(), excl.begin(), 0);
    // excl: {0, 1, 3, 6}

    // Together they give both endpoints of every half-open interval:
    for (std::size_t i = 0; i < input.size(); ++i)
        std::cout << "segment " << i << ": [" << excl[i] << ", " << incl[i] << ")\n";
    // segment 0: [0, 1)
    // segment 1: [1, 3)
    // segment 2: [3, 6)
    // segment 3: [6, 10)
}

Using both scans together gives every half-open interval in the flattened buffer — a single allocation can hold all variable-length segments without any per-segment pointer indirection.

transform_inclusive_scan and transform_exclusive_scan

The transform variants fuse a per-element unary transformation with the subsequent scan, saving an intermediate allocation and the cache pressure of writing and re-reading a temporary array.

Argument order warning. The two signatures are not symmetric:

// transform_inclusive_scan: binary_op before unary_op; init is LAST and OPTIONAL
transform_inclusive_scan(first, last, result, binary_op, unary_op);
transform_inclusive_scan(first, last, result, binary_op, unary_op, init);

// transform_exclusive_scan: init is THIRD (before both ops); init is MANDATORY
transform_exclusive_scan(first, last, result, init, binary_op, unary_op);

This asymmetry is a known rough edge in the C++17 interface. Swapping init with the ops is a silent logic error that compiles if the types are compatible — always check the signature.

Example: word lengths to byte offsets for string packing

Given a list of words to be packed into a flat buffer, the exclusive scan of their lengths gives each word's start offset. This is a classic use of the fused form — transform from std::string to std::size_t length, then exclusive-scan to produce offsets, all in one pass.

#include <numeric>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>

int main() {
    std::vector<std::string> words{"hello", "world", "foo", "bar"};
    // lengths:  {5, 5, 3, 3}  (total = 16 bytes)

    std::vector<std::size_t> offsets(words.size());
    std::transform_exclusive_scan(
        words.begin(), words.end(),
        offsets.begin(),
        std::size_t{0},                                    // init
        std::plus<std::size_t>{},                          // binary_op
        [](const std::string& s) { return s.size(); }     // unary_op
    );
    // offsets: {0, 5, 10, 13}

    // Compute total size from the last offset + last length
    std::size_t total = offsets.back() + words.back().size();
    std::string packed(total, '\0');

    for (std::size_t i = 0; i < words.size(); ++i)
        std::memcpy(packed.data() + offsets[i], words[i].data(), words[i].size());
    // packed: "helloworldfoobar"

    std::cout << packed << '\n';
}

The same pattern generalises to any serialisation scenario: binary protocol messages, arena allocators, GPU kernel argument buffers.

Example: inclusive form for cumulative word lengths

#include <numeric>
#include <string>
#include <vector>
#include <iostream>

int main() {
    std::vector<std::string> words{"hello", "world", "foo", "bar"};

    std::vector<std::size_t> ends(words.size());
    std::transform_inclusive_scan(
        words.begin(), words.end(),
        ends.begin(),
        std::plus<std::size_t>{},                          // binary_op
        [](const std::string& s) { return s.size(); }     // unary_op
    );
    // ends: {5, 10, 13, 16}  -- the exclusive end of each packed word
}

Parallel Execution: How It Works

All four C++17 scan algorithms accept an ExecutionPolicy as their first argument. Passing std::execution::par or std::execution::par_unseq signals that the implementation may divide the range among threads and vectorise individual sub-ranges.

The work-efficient two-pass algorithm

A naive parallel prefix scan processes each output element independently, performing O(n log n) total additions. The work-efficient algorithm used in practice achieves O(n) total work at O(log n) depth via two passes:

Pass 1 — Upsweep (reduce phase). Treat the array as a binary tree of pairs. In each of log₂ n rounds, every active node accumulates its right child with its own value, halving the active node count. After log₂ n rounds, position n−1 holds the total reduction.

Pass 2 — Downsweep. Place the identity value at position n−1, then propagate downward. In each round, every active node sends its current value to its left child and the sum of its current value and its left child to its right child, doubling the active count. After log₂ n rounds every position holds its correct exclusive-scan output.

The net result: two passes over the data, each touching O(n) elements, with no element touched more than O(log n) times across all rounds. The standard library implementation may use this algorithm internally or a segmented variant that assigns contiguous chunks to threads and merges the partial scans in a second step.

#include <numeric>
#include <execution>
#include <vector>

// Parallel prefix sum over 10 million elements
std::vector<long long> data(10'000'000);
// ... fill with values ...

std::vector<long long> prefix(data.size());
std::inclusive_scan(
    std::execution::par,          // parallel, order within thread is sequential
    data.begin(), data.end(),
    prefix.begin()
);

Use std::execution::par (not par_unseq) when the binary operation involves any branching or non-trivially-vectorisable logic. Reserve par_unseq for branchless, SIMD-friendly operations such as integer addition or bitwise OR.

Floating-point non-determinism

For double or float, IEEE 754 arithmetic is not associative: (a + b) + c does not equal a + (b + c) in general. A parallel scan is free to merge partial results in any order across threads, so the output can differ from a sequential scan by more than floating-point rounding noise — and may differ between runs on the same hardware.

This is not a bug in the implementation; it is a deliberate consequence of the C++17 specification, which grants implementations the freedom to reorder associative operations to enable parallelism. If you need reproducible floating-point results, pass std::execution::seq explicitly.

// Reproducible but sequential
std::inclusive_scan(std::execution::seq, data.begin(), data.end(), prefix.begin());

// Fast but non-reproducible for floating-point
std::inclusive_scan(std::execution::par, data.begin(), data.end(), prefix.begin());

Practical Use Cases

Running totals and financial time series

#include <numeric>
#include <vector>

// Daily revenues → cumulative revenue to date
std::vector<double> daily{1200.0, 800.0, 1500.0, 950.0, 2100.0};
std::vector<double> cumulative(daily.size());
std::inclusive_scan(daily.begin(), daily.end(), cumulative.begin());
// cumulative: {1200, 2000, 3500, 4450, 6550}

Histogram cumulative distribution function (CDF)

An image histogram records how many pixels fall into each intensity bucket. The CDF — used for histogram equalisation — is the inclusive scan of those counts. The normalised CDF tells you, for each intensity level, what fraction of pixels are at or below that level.

#include <numeric>
#include <vector>
#include <algorithm>

std::vector<int> histogram(256, 0);
// ... tally pixel intensities into histogram ...

std::vector<int> cdf(256);
std::inclusive_scan(histogram.begin(), histogram.end(), cdf.begin());
// cdf[i] = number of pixels with intensity <= i

int total_pixels = cdf[255];
// Equalised intensity for pixel with value v: (cdf[v] * 255) / total_pixels

Work-stealing task scheduling

When splitting a heterogeneous task list among threads, each thread needs to know its slice of a shared output buffer. Exclusive scan of task sizes gives each thread its start offset with no synchronisation beyond the initial scan.

#include <numeric>
#include <execution>
#include <vector>

// tasks[i].output_size() is the number of results task i will produce
std::vector<int> sizes(tasks.size());
std::transform(tasks.begin(), tasks.end(), sizes.begin(),
               [](const Task& t) { return t.output_size(); });

std::vector<int> starts(tasks.size());
std::exclusive_scan(
    std::execution::par,
    sizes.begin(), sizes.end(),
    starts.begin(),
    0
);
// starts[i] = total output elements before task i — no locks needed

After the scan, threads can write directly to output[starts[i]..starts[i]+sizes[i]) without any mutual exclusion.

See Also

• std::reduce (C++17) — parallel-capable total reduction without prefix output
• std::transform_reduce (C++17) — fused transform and fold over one or two ranges
• std::adjacent_difference (C++98) — inverse operation; produces per-element differences from a prefix-sum sequence
• std::inner_product (C++98) — dot product and generalised fold over two ranges simultaneously