Standard Library Numeric Operations Numeric Operations Numeric Ops

New to C++'s standard library algorithms? ⇒ Short Introduction

`#include <numeric>`

Reductions	produce one result based on a sequence of input elements
Scans (Prefix Sums)	produce a sequence of results with the same number of elements as the input sequence

`iota` (fill with ascending numbers) `iota` (fill ascending) iota C++11

cppreference

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

int main () {std::vector<int> v;
v.resize(9,0);
// fill subrange (as shown in image)
iota(begin(v)+2, begin(v)+7, 1);
for (int x : v) { std::cout << x << ' '; }  // 0 0 1 2 3 4 5 0 0
std::cout << '\n';
// fill entire vector
iota(begin(v), end(v), 3);
for (int x : v) { std::cout << x << ' '; }  // 3 4 5 6 7 8 9 10 11
std::cout << '\n';
}

cppreference

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

int main () {std::vector<int> v;
v.resize(5,0);
// NOTE: might not be available yet
// in many standard library implementations!
auto const result = std::ranges::iota(v, 3);
std::cout << result.value << '\n';  // 8
for (int x : v) { std::cout << x << ' '; }  // 3 4 5 6 7
std::cout << '\n';
}

Reductions

`reduce` reduce C++17

The reduction operation ⊕ must be associative and commutative, because the order in which it is applied is not guaranteed.

cppreference

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

int main () {std::vector<int> v {1,9,7,3,2,8};
auto const sum = reduce(begin(v), end(v));  // 1+9+7+3+2+8 = 30
std::cout << "sum: " << sum << '\n';auto const s47 = reduce(begin(v), end(v), 47);  // 47+1+9+7+3+2+8 = 77
std::cout << "s47: " << s47 << '\n';
std::vector<double> w {2.0, 1.5, 3.0, 1.5};
auto const product = reduce(begin(w), end(w), 1.0, std::multiplies<>{});  
// double product = 1.0 * 2.0 * 1.5 * 3.0 * 1.5 = 13.5
std::cout << "product: " << product << '\n';
// execute in parallel: #include <execution>
auto const psum = reduce(std::execution::par, begin(v), end(v));
std::cout << "psum: " << psum << '\n';}

Make sure that the type of the initial value ω is either the same as the input elements' type or a type that can represent more values!

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

int main () {// narrower initial value type might // lead to loss of information:
std::vector<double> v {1.2, 2.4};                     
auto const wtf = reduce(begin(v), end(v), 1);  
std::cout << wtf << '\n';  // 4                    int ^
auto const sum = reduce(begin(v), end(v), 1.0);  
std::cout << sum << '\n';  // 4.6               double ^^^
}

`transform_reduce` transform_reduce C++17

The reduction operation ⊕ must be associative and commutative and the projection f must not have side effects / be stateful, because there is no guaranteed order in which they are applied.

cppreference

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

int main () {std::vector<int> v {3,2,4};
auto f = [](int x) { return x*x; };
auto const rf = transform_reduce(begin(v), end(v), 1, std::plus<>{}, f);  
// rf = 1 + f(3) + f(2) + f(4) = 30
std::cout << "rf: " << rf << '\n';
}

Both operations ⊕ and ⊗ must be associative and commutative because there is no guaranteed order in which they are applied.

cppreference

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

int main () {std::vector<double> x {1.0, 3.0, 5.0};
std::vector<double> y {2.0, 4.0, 8.0};
auto const rx1 = transform_reduce(begin(x), end(x), begin(y), 10.0);  
// rx1 = 10 + (1⋅2)+(3⋅4)+(5⋅8) = 64
std::cout << "rx1: " << rx1 << '\n';auto const rx2 = transform_reduce(
    begin(x), end(x), begin(y), 0.0, 
    std::plus<>{}, std::divides<>{});  
// rx2 = 0.0 + (1/2)+(3/4)+(5/8) = 1.875
std::cout << "rx2: " << rx2 << '\n';
}

Legacy Operations (no parallel execution possible)

`accumulate` (≈ `reduce`) accumulate C++98

Prefer C++17's std::reduce because it can also be executed in parallel.
Use accumulate only with a non-commutative or non-associative reduction operation ⊕.

cppreference

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

int main () {std::vector<int> v {1,9,7,3,2,8};
auto const sum = accumulate(begin(v), end(v), 0);  // 1+9+7+3+2+8 = 30
std::cout << "sum: " << sum << '\n';auto const s47 = accumulate(begin(v), end(v), 47);  // 47+1+9+7+3+2+8 = 77
std::cout << "s47: " << s47 << '\n';
std::vector<double> w {2.0, 1.5, 3.0, 1.5};
auto const product = accumulate(begin(w), end(w), 1.0, std::multiplies<>{});
// double product = 1.0 * 2.0 * 1.5 * 3.0 * 1.5 = 13.5
std::cout << "product: " << product << '\n';
}

Make sure that the type of the initial value ω is either the same as the input elements' type or a type that can represent more values!

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

int main () {// narrower initial value type might // lead to loss of information:
std::vector<double> v {1.2, 2.4};                     
auto const wtf = accumulate(begin(v), end(v), 0);  
std::cout << wtf << '\n';  // 3                  int ^
auto const sum = accumulate(begin(v), end(v), 0.0);  
std::cout << sum << '\n';  // 3.6             double ^^^
}

`inner_product` (≈ `transform_reduce`) inner_product C++98

Prefer C++17's std::transform_reduce because it can also be executed in parallel.

cppreference

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

int main () {std::vector<int> v {4,3,2,1};
std::vector<int> w {10,20,30,40};
auto const ip = inner_product(begin(v), end(v), begin(w), 50);  
// ip = 50 + (4⋅10)+(3⋅20)+(2⋅30)+(1⋅40) = 250
std::cout << "ip: " << ip << '\n';
std::vector<double> num {1.0, 3.0, 5.0};
std::vector<double> den {2.0, 4.0, 8.0};
auto const res = inner_product(
    begin(num), end(num), begin(den), 0.0, 
    std::plus<>{}, std::divides<>{} );  
// res = 0.0 + (1/2)+(3/4)+(5/8) = 1.875
std::cout << "res: " << res << '\n';
}

Scans (Prefix Sums)

Target ranges must be able to receive all produced elements!

This means that, e.g., target containers must be resized properly.

Standard algorithms don't – and in most cases can't – check if the target range is large enough.

Trying to copy elements beyond the target's capacity will invoke undefined behavior!

`adjacent_difference` adjacent_difference

The operation ⊖ must not have side effects / be stateful, because the order in which it is applied is not guaranteed.

cppreference

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

int main () {std::vector<int> in {1,2,6,8,3,6};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
adjacent_difference(begin(in), end(in), begin(out));
for (int x : out) { std::cout << x << ' '; }  // 1 1 4 2 -5 3
std::cout << '\n';

// C++17: can supply custom operation
adjacent_difference(begin(in), end(in), begin(out), std::plus<>{});
for (int x : out) { std::cout << x << ' '; }  // 1 3 8 14 11 9
std::cout << '\n';
adjacent_difference(begin(in), end(in), begin(out), std::multiplies<>{});
for (int x : out) { std::cout << x << ' '; }  // 1 2 12 48 24 18
std::cout << '\n';
}

`inclusive_scan` inclusive_scan C++17

The binary operation ⊕ must be associative, because the order in which it is applied is not guaranteed.

cppreference

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

int main () {std::vector<int> in {2,1,7,5,3};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
inclusive_scan(begin(in), end(in), begin(out));
for (int x : out) { std::cout << x << ' '; }  // 2 3 10 15 18
std::cout << '\n';
inclusive_scan(begin(in), end(in), begin(out), std::minus<>{});
for (int x : out) { std::cout << x << ' '; }  // 2 1 -6 -11 -14
std::cout << '\n';
// with offset '3':
inclusive_scan(begin(in), end(in), begin(out), std::plus<>{}, 3);
for (int x : out) { std::cout << x << ' '; }  // 5 6 13 18 21
std::cout << '\n';
}

`exclusive_scan` exclusive_scan C++17

The binary operation ⊕ must be associative because the order in which it is applied is not guaranteed.

cppreference

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

int main () {std::vector<int> in {2,1,7,5,3};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
exclusive_scan(begin(in), end(in), begin(out), 0);
for (int x : out) { std::cout << x << ' '; }  // 0 2 3 10 15
std::cout << '\n';
// with offset '3':
exclusive_scan(begin(in), end(in), begin(out), 3);
for (int x : out) { std::cout << x << ' '; }  // 3 5 6 13 18
std::cout << '\n';
exclusive_scan(begin(in), end(in), begin(out), 0, std::minus<>{});
for (int x : out) { std::cout << x << ' '; }  // 0 -2 -3 -10 -15
std::cout << '\n';
}

`transform_inclusive_scan` transform_inclusive_scan C++17

The operation ⊕ must be associative and the projection f must not have side effects / be stateful, because the order in which they are applied is not guaranteed.

cppreference

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

int main () {// returns value only if even and 0 if odd
auto even_only = [](int x) { return (x & 1) ? 0 : x; };
std::vector<int> in {2,1,6,4,3};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
transform_inclusive_scan(
  begin(in), end(in), begin(out), std::plus<>{}, even_only);
for (int x : out) { std::cout << x << ' '; }  // 2 2 8 12 12
std::cout << '\n';
// with offset '3':
transform_inclusive_scan(
  begin(in), end(in), begin(out), std::plus<>{}, even_only, 3);
for (int x : out) { std::cout << x << ' '; }  // 5 5 11 15 15
std::cout << '\n';
// with projection f(x) = -x²:
transform_inclusive_scan(
  begin(in), end(in), begin(out), std::plus<>{}, 
  [](int x) { return -(x*x); });
for (int x : out) { std::cout << x << ' '; }  // -4 -5 -41 -57 -66
std::cout << '\n';
}

`transform_exclusive_scan` transform_exclusive_scan C++17

The operation ⊕ must be associative and the projection f must not have side effects / be stateful, because the order in which they are applied is not guaranteed.

cppreference

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

int main () {// returns value only if even and 0 if odd
auto even_only = [](int x) { return (x & 1) ? 0 : x; };
std::vector<int> in {2,1,6,4,3};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
transform_exclusive_scan(
  begin(in), end(in), begin(out), 0, std::plus<>{}, even_only);
for (int x : out) { std::cout << x << ' '; }  // 0 2 2 8 12
std::cout << '\n';
// with offset '3':
transform_exclusive_scan(
  begin(in), end(in), begin(out), 3, std::plus<>{}, even_only);
for (int x : out) { std::cout << x << ' '; }  // 3 5 5 11 15
std::cout << '\n';
// with projection f(x) = -x²:
transform_exclusive_scan(
  begin(in), end(in), begin(out), 0, std::plus<>{}, 
  [](int x) { return -(x*x); });
for (int x : out) { std::cout << x << ' '; }  // 0 -4 -5 -41 -57
std::cout << '\n';
}

Legacy Operations (no parallel execution possible)

`partial_sum` (≈ `inclusive_scan`) partial_sum C++98

Prefer C++17's std::inclusive_scan because it can also be executed in parallel.
Use partial_sum only, if the reduction operation ⊕ is non-associative.

cppreference

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

int main () {std::vector<int> in {1,1,2,2,1,1};
// make sure output can fit results
std::vector<int> out;
out.resize(in.size());
partial_sum(begin(in), end(in), begin(out));
for (int x : out) { std::cout << x << ' '; }  // 1 2 4 6 7 8
std::cout << '\n';
partial_sum(begin(in), end(in), begin(out), std::minus<>{});
for (int x : out) { std::cout << x << ' '; }  // 1 0 -2 -4 -5 -6
std::cout << '\n';
}

Remove

Beginner's Guide / Std.Library 2

Sorted Seq. Ops

Related …

A Tour of C++: Containers and Algorithms

Algorithms Overview Sheet

Last updated: 2022-11-20

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

Standard Library Numeric Operations Numeric Operations Numeric Ops

New to C++'s standard library algorithms? ⇒ Short Introduction

`#include <numeric>`

Reductions

Scans (Prefix Sums)

`iota` (fill with ascending numbers) `iota` (fill ascending) iota C++11

Reductions

`reduce` reduce C++17

`transform_reduce` transform_reduce C++17

Legacy Operations (no parallel execution possible)

`accumulate` (≈ `reduce`) accumulate C++98

`inner_product` (≈ `transform_reduce`) inner_product C++98

Scans (Prefix Sums)

Target ranges must be able to receive all produced elements!

`adjacent_difference` adjacent_difference

`inclusive_scan` inclusive_scan C++17

`exclusive_scan` exclusive_scan C++17

`transform_inclusive_scan` transform_inclusive_scan C++17

`transform_exclusive_scan` transform_exclusive_scan C++17

Legacy Operations (no parallel execution possible)

`partial_sum` (≈ `inclusive_scan`) partial_sum C++98

Related …

Comments…

First Steps

Input & Output

Custom Types – Part 1

Diagnostics

Standard Library – Part 1

Function Objects

Standard Library – Part 2

Code Organization

Custom Types – Part 2

Generic Programming

Memory Management

Software Design Basics

New to C++'s standard library algorithms? ⇒ Short Introduction

#include <numeric>

Reductions

Scans (Prefix Sums)

iota (fill with ascending numbers) iota (fill ascending) iota C++11

Reductions

reduce reduce C++17

transform_reduce transform_reduce C++17

Legacy Operations (no parallel execution possible)

accumulate (≈ reduce) accumulate C++98

inner_product (≈ transform_reduce) inner_product C++98

Scans (Prefix Sums)

Target ranges must be able to receive all produced elements!

adjacent_difference adjacent_difference

inclusive_scan inclusive_scan C++17

exclusive_scan exclusive_scan C++17

transform_inclusive_scan transform_inclusive_scan C++17

transform_exclusive_scan transform_exclusive_scan C++17

Legacy Operations (no parallel execution possible)

partial_sum (≈ inclusive_scan) partial_sum C++98

Related …

Comments…

`#include <numeric>`

`iota` (fill with ascending numbers) `iota` (fill ascending) iota C++11

`reduce` reduce C++17

`transform_reduce` transform_reduce C++17

`accumulate` (≈ `reduce`) accumulate C++98

`inner_product` (≈ `transform_reduce`) inner_product C++98

`adjacent_difference` adjacent_difference

`inclusive_scan` inclusive_scan C++17

`exclusive_scan` exclusive_scan C++17

`transform_inclusive_scan` transform_inclusive_scan C++17

`transform_exclusive_scan` transform_exclusive_scan C++17

`partial_sum` (≈ `inclusive_scan`) partial_sum C++98