Numeric algorithms

The algorithms in <numeric> turn a range into one value. std::accumulate is the general fold: a start value, a binary operation and every element in order. The rest are named cases of the same idea: a sum, a product, a dot product, a running total.

They are one line each and they replace a loop that a reader has to decode. This lesson writes the four that cover most uses, and then the call that forgets the starting value.

The start value is also the type of the result: an int start on doubles truncates at every step, which is the one mistake this family of algorithms makes easy and it produces no warning.

std::accumulate guarantees the order and therefore works for strings and for any operation that is not commutative; std::reduce may reorder, which is the price of the parallel overload that lesson 117 measures.

accumulate

std::accumulate takes a start value and adds every element to it. The type of the start value is the type of the result, which is why the third argument matters.

The program sums a vector of ints and multiplies another with a custom operation. The multiplication starts from 1, because 0 would make every product 0.

The addition is left to right and in order, so accumulate works for any associative operation and for strings, where it concatenates. It is the general fold of lesson 041 in run-time form.

#include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::cout << std::accumulate(values.begin(), values.end(), 0) << ' '; std::cout << std::accumulate(values.begin(), values.end(), 1, [](int a, int b) { return a * b; }) << '\n'; }

g++ -std=c++23 -Wall -Wextra accumulate.cpp -o accumulate
./accumulate

10 24

reduce

std::reduce does the same job and may reorder the operations, which lets the implementation run it in parallel when the execution policy asks for it. The operation must be associative and commutative for the result to be predictable.

The program reduces a vector of ints and a vector of doubles. The double version starts from 0.0, so the fractional part is not lost.

For a sum of numbers, reduce and accumulate agree. For a string concatenation they do not, because concatenation is not commutative, and accumulate is the correct choice there.

#include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::cout << std::reduce(values.begin(), values.end()) << ' '; std::cout << std::reduce(values.begin(), values.end(), 0.0) << '\n'; }

g++ -std=c++23 -Wall -Wextra reduce.cpp -o reduce
./reduce

10 10

inner_product

std::inner_product multiplies two ranges element by element and adds the products. It is the dot product of two vectors, and it takes two operations: one for the products and one for the addition.

The program computes the dot product of two vectors of three elements and prints 32. The ranges must have at least as many elements as the first one, which the caller guarantees.

With a custom pair of operations the same algorithm computes a weighted sum or a distance. The defaults are + and *, which is the common case.

#include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> a{1, 2, 3}; std::vector<int> b{4, 5, 6}; std::cout << std::inner_product(a.begin(), a.end(), b.begin(), 0) << '\n'; }

g++ -std=c++23 -Wall -Wextra inner_product.cpp -o inner_product
./inner_product

32

iota and partial_sum

std::iota fills a range with consecutive values starting from the given one. It is the standard way to build an index sequence, and it writes through the iterators like any algorithm.

std::partial_sum turns a range into its running totals: each output element is the sum of the input up to that position. The program builds 1 to 5 with iota and prints the partial sums, which are the triangular numbers.

Both are in <numeric> and both work on any mutable range. partial_sum has an overload with a custom operation, so the same call computes a running product.

#include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values(5); std::iota(values.begin(), values.end(), 1); std::vector<int> sums(values.size()); std::partial_sum(values.begin(), values.end(), sums.begin()); for (int value : sums) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra iota.cpp -o iota_demo
./iota_demo

1 3 6 10 15

The missing start value

accumulate has no default start value: the third argument is required, because the type of the result comes from it. Calling it with two iterators leaves the compiler with no matching overload.

The program sums a vector without the initial value, and the message says there is no matching function for the call and shows the two candidates, both of which take three or four arguments.

The fix is 0 for a sum of ints, 0.0 for doubles or std::string{} for a concatenation. The choice of the start value is also the choice of the result type, so it is worth a second look.

#include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3}; return std::accumulate(values.begin(), values.end()); }

g++ -std=c++23 -Wall -Wextra no_start.cpp -o no_start

no_start.cpp: In function 'int main()':
no_start.cpp:7:27: error: no matching function for call to 'accumulate(std::vector<int>::iterator, std::vector<int>::iterator)'
7 | return std::accumulate(values.begin(), values.end());
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
no_start.cpp:7:27: note: there are 2 candidates
In file included from /usr/include/c++/15.2.0/numeric:64,
from no_start.cpp:1:
/usr/include/c++/15.2.0/bits/stl_numeric.h:134:5: note: candidate 1: 'template<class _InputIterator, class _Tp> constexpr _Tp std::accumulate(_InputIterator, _InputIterator, _Tp)'
134 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
| ^~~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_numeric.h:134:5: note: candidate expects 3 arguments, 2 provided
/usr/include/c++/15.2.0/bits/stl_numeric.h:161:5: note: candidate 2: 'template<class _InputIterator, class _Tp, class _BinaryOperation> constexpr _Tp std::accumulate(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
161 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
| ^~~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_numeric.h:161:5: note: candidate expects 4 arguments, 2 provided

Exercises

  1. Sum a vector of doubles with an int start value and then with 0.0, and compare the results.
  2. Concatenate a vector of strings with accumulate and a lambda.
  3. Use partial_sum with std::multiplies to print the running factorials of 1 to 6.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does std::accumulate need that the range algorithms do not?

    Answer

    A start value

    The fold starts from the value, which is also the result for an empty range.

  2. What does std::reduce allow that accumulate does not?

    Answer

    The operation to be applied in any order

    The regrouping is what makes a parallel reduce possible.

  3. What does std::inner_product compute?

    Answer

    The sum of the products of two ranges

    It pairs the elements and combines the products with the default plus.

  4. What does std::iota do?

    Answer

    It fills a range with consecutive values

    The start value is written, then incremented for each element.

  5. What does this program print? #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::cout << std::accumulate(values.begin(), values.end(), 0) << ' '; std::cout << std::accumulate(values.begin(), values.end(), 4, [](int a, int b) { return a * b; }); }

    Answer

    10 96

    The first fold adds to zero, and the second multiplies the elements starting from four.

  6. What does this program print? #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::cout << std::reduce(values.begin(), values.end()) << ' '; std::cout << std::reduce(values.begin(), values.end(), 0); }

    Answer

    10 10

    The default reduce adds the elements, and the second call starts from zero and gives the same sum.

  7. What does this program print? #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> a{1, 2, 3}; std::vector<int> b{4, 5, 6}; std::cout << std::inner_product(a.begin(), a.end(), b.begin(), 0); }

    Answer

    32

    The products 4, 10 and 18 are added, and the total is 32.

  8. What does this program print? #include <iostream> #include <numeric> #include <vector> int main() { std::vector<int> values(5); std::iota(values.begin(), values.end(), 1); std::vector<int> sums; std::partial_sum(values.begin(), values.end(), std::back_inserter(sums)); for (int v : sums) std::cout << v << ' '; }

    Answer

    1 3 6 10 15

    The iota fills 1 to 5, and the partial sums add one element at a time.

  9. What does the compiler report for this call? #include <numeric> #include <vector> int main() { std::vector<int> values{1, 2, 3}; return std::accumulate(values.begin(), values.end()); }

    Answer

    no matching function for call to 'accumulate(std::vector<int>::iterator, std::vector<int>::iterator)'

    The start value is a required argument, and without it the call has no candidate.

  10. Why is reduce allowed to change the result for floating point?

    Answer

    The grouping changes, and floating point addition is not associative

    Any regrouping is allowed, and the last bits depend on the order of the additions.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev