Transforming and Accumulating

Part I · Module 20 · Chapter 20.7 · Transforming and Accumulating

1. transform Produces a Range

std::vector<int> cyc{100, 250, 75, 400};
std::vector<double> us(cyc.size());
std::transform(cyc.begin(), cyc.end(), us.begin(), [](int c){ return c / 1000.0; });

cycles -> microseconds: 0.100 0.250 0.075 0.400

std::transform(b, e, out, f) applies f to each element of [b, e) and writes the results starting at out. The output type need not match the input type — here int in, double out — because the destination is a separate range.

It returns an iterator one past the last element written, which is what you need if the destination is larger than the result.

There is a two-range form that applies a binary operation element-wise:

std::transform(a.begin(), a.end(), b.begin(), sum.begin(), std::plus<int>{});

element-wise a+b: 11 22 33

And the destination may be the source, which transforms in place:

in place (dest == source): 1 4 9

That is explicitly allowed for transform — the standard says the operation must not invalidate iterators or modify elements other than the one being written, and writing to the element you just read satisfies it. Note this is not true of every algorithm: std::copy requires the ranges not to overlap in the forward direction, and std::copy_backward exists for the case where they do.

The function must be pure. std::transform makes no promise about the order in which it applies f, so a function with side effects or internal state produces an unspecified result. This is the same requirement Chapter 20.5 §2 placed on predicates, and for the same reason.

2. The Destination Must Have Room

This is the first trap and it is a quiet one.

std::vector<int> src{1,2,3,4};
std::vector<int> dst;                        // EMPTY
std::transform(src.begin(), src.end(), dst.begin(), f);   // writes into nothing

An algorithm has only iterators. It cannot ask the destination how big it is, it cannot grow it, and it does not check — so writing four elements through dst.begin() on an empty vector writes into unallocated storage. There is no diagnostic.

The fix is an insert iterator, from Chapter 20.1 §9:

std::transform(src.begin(), src.end(), std::back_inserter(dst), [](int x){ return x*10; });

with back_inserter, dst grew to 4: 10 20 30 40

std::back_inserter(dst) returns an output iterator whose assignment calls dst.push_back. The container grows as the algorithm writes.

So the rule is: either size the destination first (dst.resize(src.size()), or construct it with the size) or use an insert iterator. The two are not interchangeable in cost — resize is one allocation if you know the size, while back_inserter is the growth pattern Chapter 19.3 §4 measured at 11 allocations for 1,000 elements, which a reserve fixes:

dst.reserve(src.size());
std::transform(src.begin(), src.end(), std::back_inserter(dst), f);

3. accumulate Folds a Range to One Value

std::vector<int> v{1,2,3,4};
std::accumulate(v.begin(), v.end(), 0);                              // sum
std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>{});      // product
std::accumulate(w.begin(), w.end(), std::string{},
                [](const std::string& a, const std::string& b){ return a + b; });

sum          = 10
product      = 24
max          = 4
concatenated = abc

std::accumulate(b, e, init) computes init + e0 + e1 + …. With a fourth argument it uses that operation instead of +, which makes it a general left fold: start with init, combine with each element in turn, return the result.

Two things about the init argument, and they are the whole chapter.

It is the identity element for the operation: 0 for addition, 1 for multiplication, an empty string for concatenation, the first element for a maximum. Getting that wrong gives a wrong answer that is obvious — a product seeded with 0 is 0.

And it determines the accumulator's type, which gives a wrong answer that is not obvious at all.

4. The Init Value Picks the Type

std::vector<double> lat{1.5, 2.5, 3.25, 0.75};     // true sum: 8.00
auto bad  = std::accumulate(lat.begin(), lat.end(), 0);      // int accumulator
auto good = std::accumulate(lat.begin(), lat.end(), 0.0);

values: 1.5 2.5 3.25 0.75   true sum = 8.00
accumulate(..., 0)   = 6      <-- int accumulator TRUNCATES each add
accumulate(..., 0.0) = 8.00

Six instead of eight. The signature is roughly:

template <class It, class T>
T accumulate(It first, It last, T init)
{ for (; first != last; ++first) init = init + *first; return init; }

T is deduced from init, so 0 makes T = int. Then init + *first is int + double, which is double — and assigning it back to an int truncates. Every iteration. Not once at the end: 0 + 1.5 = 1.5 becomes 1; 1 + 2.5 = 3.5 becomes 3; 3 + 3.25 = 6.25 becomes 6; 6 + 0.75 = 6.75 becomes 6.

Each truncation is a legal implicit conversion, which is why §5 is about what the compiler had to say.

The integer form of the same mistake is overflow:

1000 x 10,000,000  int32 accumulator = 1410065408  <-- OVERFLOWED (UB)
                   int64 accumulator = 10000000000
int32 max is 2147483647; the true sum is 10,000,000,000

Same cause — the accumulator's type came from the literal — with a different symptom. And unlike the floating-point case, signed overflow is undefined behaviour, which §5 shows makes it detectable.

So the rule: write the init value with the type you want the result to have, explicitly. 0.0 for a double sum, 0LL or std::int64_t{0} for a wide integer sum, std::string{} for a concatenation. Chapter 20.10 §4 writes 0LL for exactly this reason, with a comment pointing here.

5. What the Compiler Said

The floating-point truncation was put to the compiler with increasing severity:

-Wall -Wextra -Wpedantic          : nothing
-Wconversion -Wfloat-conversion   : 0 warnings
-Weverything                      : 0 warnings naming the truncation

Nothing, at any level. -Wfloat-conversion exists precisely to catch a double being assigned to an int, and it did not fire — because the assignment is not in your code. It is inside accumulate's loop, in a template instantiated with T = int, in a system header. Clang does not report conversion warnings from system headers by default, and there is nothing at your call site to warn about: you passed an int to a parameter of type T, which is exactly what the signature asked for.

The integer overflow is different, because it is undefined behaviour rather than a legal conversion, and UndefinedBehaviorSanitizer finds it:

__numeric/accumulate.h:32:21: runtime error: signed integer overflow:
2140000000 + 10000000 cannot be represented in type 'int'

It names the file, the line, the two operands and the type. Note it exited 0 — UBSan reports and continues by default — so a test checking only the exit status would still pass.

That gives this module's third detection pattern. Chapter 20.3's erase bug: silent everywhere. Chapter 20.6's comparator: caught by everything. Chapter 20.5's unsorted search: undetectable in principle. And this chapter: the float case undetectable by any static or dynamic tool, the integer case caught precisely by one. The discriminator each time is what kind of wrong the code is, not how wrong.

6. There Is No transform_if

copy_if(even)        : 2 4 6 8
then transform(sq)   : 4 16 36 64

The library has copy_if and transform and no combination of the two. Filtering and mapping in one call is not available in C++17, and the standard two-step is to copy_if into an intermediate and then transform it.

That costs a container and a pass. Three responses:

Accept it. For most data the intermediate is irrelevant, and reserve removes the allocation concern.

Write the loop. Chapter 20.4 §6 lists this as a legitimate case: one pass, no temporary, and the composed version is not clearer.

Use C++20 ranges. v | std::views::filter(p) | std::views::transform(f) is lazy — it does one pass and allocates nothing, because the views compose into a single iteration rather than materialising intermediates. This is the correct answer where it is available and it is the main practical reason to want C++20.

Note that std::transform into a back_inserter with a predicate inside the lambda does not work, because transform writes one output per input — a lambda that "skips" an element has nothing to return.

7. The Numeric Family

inner_product        = 32  (1*4 + 2*5 + 3*6)
partial_sum          : 1 3 6
adjacent_difference  : 10 4 1 15   (first element is copied, then gaps)
iota(100)            : 100 101 102 103 104

std::inner_product(b1, e1, b2, init) is the sum of pairwise products — a dot product. Like accumulate, init sets the type, and the same trap applies. Both operations can be replaced, which makes it a general two-range fold.

std::partial_sum(b, e, out) writes the running totals: output i is the sum of inputs 0 through i. Useful for cumulative distributions and for turning a histogram into a CDF.

std::adjacent_difference(b, e, out) is the inverse: output 0 is a copy of input 0, and output i is input i minus input i−1. The measured 10 4 1 15 from timestamps 10 14 15 30 is the idiomatic use — turning absolute timestamps into inter-arrival gaps, with the first element preserved so that partial_sum of the result reconstructs the original.

std::iota(b, e, start) fills a range with consecutively increasing values. Its main use is generating an index vector, which is Chapter 20.6 §9's sort-the-indices pattern.

std::reduce (C++17) is accumulate without the ordering guarantee — it may reassociate and combine in any order, which is what permits a parallel execution policy. For integers that is harmless; for floating point the result may differ in the last bits, because floating-point addition is not associative. std::transform_reduce fuses a transform and a reduce in one pass, which is the closest the standard library comes to §6's missing operation for the reduction case.

8. accumulate Is a Left Fold

accumulate (strict left-to-right) = 7.485470860550343
std::reduce may reassociate, so for floating point it may differ
in the last bits -- that freedom is what permits parallelism.

std::accumulate is specified to apply the operation strictly left to right, which means it is not reorderable and therefore not parallelisable. That is a guarantee, not an oversight: it lets you use a non-associative or non-commutative operation and know what you will get.

// relies on left-to-right: subtracting each element from the running total
auto remaining = std::accumulate(costs.begin(), costs.end(), budget,
                                 [](int acc, int c){ return acc - c; });

std::reduce drops that guarantee to gain parallelism, which is why the two exist separately rather than one being a better version of the other. Use accumulate when order matters or when the operation is not associative; use reduce when it is and you want the option of a policy.

For floating-point summation neither is numerically ideal — both lose precision when values differ by orders of magnitude. If the accuracy of a long float sum matters, Kahan summation or sorting by magnitude first is the answer, and that is a numerical-methods question rather than an algorithm-selection one.

9. The Table

10. What to Actually Do

• Write the init value with the type you want. 0.0, 0LL, std::int64_t{0}, std::string{} — never a bare 0 for anything but an int result.
• Prefer the explicit form std::int64_t{0} over 0LL when the width matters to a reader.
• Size the destination or use back_inserter. Never write through begin() of an empty container.
• reserve before a back_inserter loop when the count is known.
• Keep the transform function and the predicate pure. The order and count of applications are unspecified.
• Use accumulate when order matters, reduce when it does not and you may want a policy.
• Reach for transform_reduce rather than a temporary when you are mapping then folding.
• Accept the intermediate for filter-then-map, or write the loop, or use C++20 views — in that order of preference.
• Use adjacent_difference for inter-arrival gaps and partial_sum to reconstruct.
• Comment the init value where the width is load-bearing, because nothing else will flag it.

11. Mistakes Worth Making Once

accumulate(v.begin(), v.end(), 0) over doubles. Measured 6 instead of 8.00, with nothing from -Weverything.

The same over a sum exceeding INT_MAX. Measured 1410065408; UBSan names it, nothing else does.

transform into an empty destination. No storage, no diagnostic.

Calling std::remove's relatives and forgetting they do not resize — Chapter 20.3 §7, the same shape of mistake.

Seeding a product with 0. Returns 0, which is at least obvious.

A transform function with side effects. The order of application is unspecified.

Expecting std::reduce to give bit-identical results to accumulate on floats. It may reassociate.

Reaching for transform with a filtering lambda. One output per input; there is nothing to return for a skipped element.

12. Interview Relevance

The frozen curriculum marks this chapter High, and the accumulator question is a good one precisely because the answer is counter-intuitive.

"What does std::accumulate(v.begin(), v.end(), 0) return for a vector<double>?" An int, with every partial sum truncated. The strong answer gives the measured 6-for-8.00 and explains that T is deduced from the init value.

"Would the compiler warn?" No — not with -Wall, -Wextra, -Wconversion, -Wfloat-conversion or -Weverything, because the narrowing is inside a system-header template and the call site is well-formed. Knowing this is unusual and lands well.

"What about the integer version?" Signed overflow, which is undefined behaviour and which UBSan catches by name. The contrast — legal narrowing invisible, undefined overflow detected — is the insight.

"What does transform require of its destination?" That it already has room, or that it is an insert iterator. The algorithm cannot check.

"Is there a transform_if?" No. Two steps with a temporary, a loop, or C++20 views; transform_reduce covers the fused reduction case.

"What is the difference between accumulate and reduce?" accumulate is a strict left fold and is not reorderable; reduce may reassociate, which permits parallelism and can change a floating-point result.

"Why does adjacent_difference copy the first element?" So that partial_sum of the output reconstructs the input exactly.

13. What You Should Be Able to Say Now

• That transform writes one output per input and the destination must have room or be an insert iterator.
• That transform in place is explicitly allowed while std::copy on overlapping ranges is not.
• That accumulate's init value is both the identity element and the type declaration.
• That summing four doubles totalling 8.00 with a 0 init returned 6, truncating at every step.
• That -Wall, -Wextra, -Wconversion, -Wfloat-conversion and -Weverything all reported nothing, and the structural reason why.
• That the integer twin is undefined behaviour and UBSan names it exactly — and exits 0 anyway.
• That there is no transform_if, and the three responses to that.
• That accumulate is a strict left fold and reduce may reassociate.

14. Exercises

Exercise 1 — the truncation. Reproduce §4 and then find a set of four doubles for which the 0 init happens to give the right answer. Explain what makes those values safe.

Exercise 2 — the flags. Compile the 0-init version with every warning flag you can find, including -Weverything, and confirm the silence. Then move the accumulation loop into your own file and see which flags fire.

Exercise 3 — the overflow. Reproduce the integer case under UBSan, note the exit code, and write a test that would fail on it. Then fix it with an explicit std::int64_t{0}.

Exercise 4 — destinations. Transform a 1,000-element range four ways: pre-sized destination, resize then begin(), back_inserter, and reserve plus back_inserter. Count allocations for each.

Exercise 5 — the missing algorithm. Implement filter-then-map three ways and compare passes, allocations and readability. If you have C++20, add the ranges version.

Exercise 6 — folds. Use accumulate to compute a maximum, a minimum, a count of elements satisfying a predicate, and a comma-separated string. State the identity element for each.

Exercise 7 — timestamps. Turn a vector of absolute timestamps into gaps with adjacent_difference, then back with partial_sum, and assert the round trip is exact.

Exercise 8 — left fold. Write a fold that is order-dependent, compute it with accumulate and with reduce, and explain any difference.

15. Summary

• transform writes one output per input, may change the type, has a two-range form, and may write in place.
• The destination must already have room, or be an insert iterator — the algorithm has only iterators and cannot check.
• accumulate's init value is the identity element AND the accumulator's type.
• Measured: four doubles totalling 8.00, summed with accumulate(..., 0), returned 6 — truncated at every one of four steps.
• Measured: -Wall -Wextra -Wpedantic, -Wconversion -Wfloat-conversion and -Weverything all reported NOTHING, because the narrowing is inside a system-header template and the call site is well-formed.
• Measured: the integer twin overflowed to 1410065408, and UBSan named it — "2140000000 + 10000000 cannot be represented in type 'int'" at accumulate.h:32:21 — while exiting 0.
• So write the init value deliberately: 0.0, 0LL, std::int64_t{0}, std::string{}.
• There is no transform_if — two steps, a loop, or C++20 views; transform_reduce fuses the reduction case.
• accumulate is a strict left fold and so is not reorderable; reduce may reassociate, which buys parallelism and can change a float result.
• Measured: adjacent_difference copies the first element, so partial_sum reconstructs the input.

Every algorithm in the last four chapters took a callable — a predicate for find_if and count_if, a comparator for sort, a function for transform, an operation for accumulate — and every example wrote that callable as a lambda without explaining what one is. Chapter 20.8 explains it. A lambda is a class the compiler writes for you, its captures are that class's data members, and the capture list is the one part of the syntax that is a real decision rather than a formality: the chapter measures the size of the resulting object for seven different capture lists, and measures what happens when a captured reference outlives the thing it referred to.