C++ / ITERATORS, ALGORITHMS, AND RANGES
Numeric algorithms: accumulate and partial sums
Fold a range into one value with accumulate, write running totals with partial_sum, and pick the accumulator type on purpose.
What you will learn
- The init argument's type is the accumulator type, not the element type.
- Use partial_sum for running totals and adjacent_difference to turn totals into deltas.
- Write a fold whose binary op takes (accumulator, element) and returns the accumulator.
- Use exclusive_scan for start offsets; reduce only when the op is associative.
Understanding Numeric algorithms: accumulate and partial sums
The folds live in <numeric>, and std::accumulate is the most general of them: it holds one carried value and repeatedly performs acc = acc + *it, or acc = op(acc, *it), for every element in order, then returns acc. The mental model that matters is that acc is an ordinary variable whose type comes from the third argument, not from the elements, so 0 gives you an int accumulator even over a vector<double>. The narrowing conversion then happens on every assignment rather than once at the end, which explains almost every surprise this algorithm produces. Decide what type the answer should have, then write the init literal in that type: 0, 0.0, 0LL, std::string{}.
std::partial_sum runs the same in-order fold but publishes the accumulator after each step, so n inputs produce exactly n outputs and out[i] is the fold over in[0..i]. Because each output element is written only after the matching input has already been read into the accumulator, the standard explicitly allows result to equal first, which makes in-place prefix sums legal. std::adjacent_difference is the inverse operation: it writes in[0], then in[i] - in[i-1], so totals turn back into deltas and a partial_sum over those deltas rebuilds the totals. Note that both algorithms accumulate in the input iterator's value type, so a wider destination container does not save an int sum from overflowing.
accumulate and partial_sum are specified to visit elements in order, which is why folding with std::minus or with string concatenation has exactly one defined answer, and also why neither can be parallelised. C++17's std::reduce and std::inclusive_scan/std::exclusive_scan give that guarantee up so they may regroup the operation: reduce requires an op that is associative and commutative, the scans require associativity, and both accept an execution policy. std::transform_reduce fuses a mapping step into the fold, so a dot product or a sum of squares needs no intermediate container; its strictly ordered sibling is std::inner_product.
<functional>
<iostream>
<numeric>
<vector>
int main() {
std::vector<double> price{19.99, 5.50, 3.25, 12.00};
// The third argument fixes the accumulator's type.
std::cout << "init 0: " << std::accumulate(price.begin(), price.end(), 0) << '\n';
std::cout << "init 0.0: " << std::accumulate(price.begin(), price.end(), 0.0) << '\n';
// One running total per input element.
std::vector<double> running(price.size());
std::partial_sum(price.begin(), price.end(), running.begin());
std::cout << "running:";
for (double r : running) std::cout << ' ' << r;
std::cout << '\n';
// Strictly left to right, so a non-associative op has one answer.
std::vector<int> n{10, 3, 2};
std::cout << "minus fold: "
<< std::accumulate(n.begin(), n.end(), 100, std::minus<int>{}) << '\n';
}
accumulate and partial_sum are the same in-order fold, one returning the final accumulator and one writing it out at every step, and the init argument decides what type that accumulator has.
Worked examples
Prefix sums in place, then undone
partial_sum and adjacent_difference are inverses, and both may write over their own input.
<iostream>
<numeric>
<vector>
int main() {
std::vector<int> daily{3, 1, 4, 1, 5};
std::partial_sum(daily.begin(), daily.end(), daily.begin());
std::cout << "totals:";
for (int x : daily) std::cout << ' ' << x;
std::cout << '\n';
std::adjacent_difference(daily.begin(), daily.end(), daily.begin());
std::cout << "deltas:";
for (int x : daily) std::cout << ' ' << x;
std::cout << '\n';
}
Example explained
Line 1Passing daily.begin() as the destination is legal: for both algorithms the standard says result may be equal to first.
Line 2partial_sum can do this because element i is written after in[i] has been folded into the accumulator.
Line 3adjacent_difference can do it because it copies *i into a temporary before overwriting the slot, so the previous value is not lost.
Line 4The second call restores the original numbers, which is why deltas are a lossless way to store a series of totals.
Inclusive versus exclusive scan
How the two C++17 scans differ and why exclusive_scan is what you want for start offsets.
<iostream>
<numeric>
<vector>
int main() {
std::vector<int> len{4, 2, 7, 1}; // byte sizes of four records
std::vector<int> incl(len.size()), excl(len.size());
std::inclusive_scan(len.begin(), len.end(), incl.begin());
std::exclusive_scan(len.begin(), len.end(), excl.begin(), 0);
std::cout << "inclusive:";
for (int x : incl) std::cout << ' ' << x;
std::cout << "\nexclusive:";
for (int x : excl) std::cout << ' ' << x;
std::cout << '\n';
}
Example explained
Line 1inclusive_scan without an op behaves like partial_sum: element i already contains len[i].
Line 2exclusive_scan needs an explicit init because out[0] cannot be len[0]; it shifts the sums right by one.
Line 3That shift makes excl[i] the byte offset where record i begins, so the grand total 14 is never written anywhere.
Line 4Both scans may reassociate the operation, which is why they accept an execution policy and partial_sum does not.
Folding structs with a custom op
The binary op's two parameters can have different types, which is what makes accumulate a fold rather than a sum.
<iostream>
<iterator>
<numeric>
<string>
<vector>
struct Item { std::string name; int qty; };
int main() {
std::vector<Item> cart{{"nut", 4}, {"bolt", 10}, {"washer", 6}};
int total = std::accumulate(cart.begin(), cart.end(), 0,
[](int sum, const Item& it) { return sum + it.qty; });
std::string names = std::accumulate(std::next(cart.begin()), cart.end(),
cart.front().name,
[](std::string acc, const Item& it) { return acc + ", " + it.name; });
std::cout << "total: " << total << '\n';
std::cout << "names: " << names << '\n';
}
Example explained
Line 1The first lambda parameter is the running accumulator (int, std::string) and the second is the element (const Item&).
Line 2The accumulator type is deduced from init, so 0 makes an int fold and cart.front().name makes a std::string fold.
Line 3Seeding with the first name and starting at std::next(cart.begin()) is what avoids a leading ", " separator.
Line 4The op returns the new accumulator instead of mutating anything; modifying the elements from inside the op is not allowed.
Important notes
The binary op must not modify the elements or invalidate the iterators; since C++20 the accumulator is fed in as std::move(acc), so folding into a std::string no longer copies the whole prefix on each step.
The parameter orders differ: exclusive_scan takes init before the binary op, inclusive_scan takes it after, and exclusive_scan never writes the grand total, so compute that separately if you need it.
Common mistakes
Letting the init literal pick the wrong type: std::accumulate(v.begin(), v.end(), 0) over a vector<double> holding four 0.5 values yields 0, because each addition is converted back to int on assignment; the mirror image is seeding a string fold with "", which deduces const char* and fails to compile.
Calling partial_sum with an empty or too-small destination, for example an unresized vector's begin(): it writes one element per input past the end of the buffer, which is undefined behaviour rather than an error you will see.
Reaching for std::reduce as a drop-in faster accumulate with a non-associative op such as subtraction or string concatenation: the result is unspecified because reduce is free to regroup the operands, even without an execution policy.
Try it yourself
Change, predict, then run
Given std::vector<int> temps{12, 15, 11, 19, 14}, print the mean using a single accumulate call with a 0.0 init, then print the day-to-day changes with adjacent_difference and check that a partial_sum over those changes reproduces the original readings.
Open the C++ workspaceCheck your understanding
You call std::accumulate(v.begin(), v.end(), 0) on a std::vector<double> holding {0.5, 0.5, 0.5, 0.5}. What comes back, and why?
- 2, because the additions happen in double and the conversion to int happens once at the end
- 2.0, because accumulate deduces the accumulator type from the iterator's value type
- 0, because the accumulator is an int and each 0.5 is truncated away as it is assigned back
- A compile error, because the init type must match the element type
Show answer
The accumulator type is deduced from init, so acc is an int variable and the loop runs acc = acc + *i four times: the addition promotes to double, but the assignment converts back, so 0 + 0.5 stores 0 every time. Option 0 describes a double accumulator, which is exactly what init 0.0 gives you; with an int accumulator there is no double variable to hold the running value, so there is no single conversion at the end.