C++ Basics: Compute Starting Offsets from Batch Sizes

Use std::exclusive_scan to turn a list of lengths into starting offsets.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as exclusive-scan-batch-offsets-demo.cpp:

#include <array>
#include <iostream>
#include <numeric>

int main()
{
    constexpr std::array<unsigned long long, 4> lengths{3, 0, 2, 4};
    std::array<unsigned long long, 4> offsets{};
    std::exclusive_scan(lengths.begin(), lengths.end(), offsets.begin(), 0ULL);
    for (std::size_t i = 0; i < lengths.size(); ++i) {
        std::cout << "batch " << i << ": offset=" << offsets[i]
                  << ", length=" << lengths[i] << '\n';
    }
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic exclusive-scan-batch-offsets-demo.cpp -o exclusive-scan-batch-offsets-demo &&
./exclusive-scan-batch-offsets-demo

Observed output:

batch 0: offset=0, length=3
batch 1: offset=3, length=0
batch 2: offset=3, length=2
batch 3: offset=5, length=4

Read the result

Each offset sums only the lengths before it. The empty second batch starts at three and consumes no space, so the next batch also starts at three. The final offset is five; the total occupied length is nine.

Apply it carefully

The output needs one element per input. Choose an initial value and element type wide enough for all sums, and reject inputs whose total would overflow. Unsigned arithmetic wraps. The algorithm may regroup additions, so floating-point sums need not reproduce a handwritten left-to-right loop exactly.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- exclusive-scan-batch-offsets-demo.cpp exclusive-scan-batch-offsets-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.