The Reduce and Accumulate Algorithms

In this lesson and the next, we introduce a range of algorithms that are designed to simplify large collections of objects into simpler outputs.

For example, we might have a collection of objects representing bank transactions, and we want to generate a simple object that includes some aggregate data. That could perhaps include information like:

• What was the total amount of all transactions
• How many transactions were there
• What is the average transaction value

In this lesson, we’ll introduce the std::reduce() and std::accumulate() algorithms, which remain the most popular way of implementing logic like this.

In the next lesson, we’ll introduce fold algorithms, which were added to the language in C++23, and give us more ways to accomplish tasks like this.

Using std::reduce()

The std::reduce() algorithm is available within the standard library’s <numeric> header.

The most basic form of a std::reduce() call involves two iterators, denoting the first and last element of our input.

The algorithm will return the result of adding all the objects in that range together:

1#include <numeric> 
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::reduce(Numbers.begin(), 
10                Numbers.end())}; 
11
12  std::cout << "Result: " << Result;
13}

1Result: 15

std::reduce() Initial Value and Operators

std::reduce() also has an overload that accepts an additional two arguments, so four in total:

1. An iterator pointing at the beginning of the input
2. An iterator pointing at the end of the input
3. An initial value to use for the algorithm (we cover this in more detail later)
4. A function / callable that determines how our objects are combined. It accepts two objects from our input as arguments and returns a single value

We can recreate the default behavior of adding everything in the range by passing 0 as the initial value (third argument) and a function that implements the addition operator as the fourth argument.

The standard library includes std::plus, which can help us with this. It returns a callable that simply accepts two arguments and returns the result of calling the + operator with them:

1#include <numeric>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::reduce(Numbers.begin(),
10                Numbers.end(), 0, 
11                std::plus{} 
12    )
13  };
14
15  std::cout << "Result: " << Result;
16}

1Result: 15

Below, we change the behavior of std::reduce() to multiply the values in our input, rather than add them:

1#include <numeric>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::reduce(Numbers.begin(),
10                Numbers.end(), 1,
11                std::multiplies{} 
12  )};
13
14  std::cout << "Result: " << Result;
15}

1Result: 120

With multiplication, we set the initial value to 1, as that is the identity value for multiplication.

1#include <numeric>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::reduce(Numbers.begin() + 1, 
10                Numbers.end(),
11                Numbers[0], 
12                std::plus{}
13  )};
14
15  std::cout << "Result: " << Result;
16}

1Result: 15

User-Defined Operators with std::reduce()

Of course, for the operator argument of std::reduce(), we’re not just limited to what is in the standard library. We can provide any callable (eg, a function, lambda, or functor) and pass it as the fourth argument.

Below, we pass an operator that will add the absolute values of the objects in our input:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5int main(){
6  std::vector Nums{1, -2, 3, -4, 5};
7
8  int Result{
9    std::reduce(
10      Nums.begin(), Nums.end(), 0,
11      [](int x, int y){ 
12        return std::abs(x) + std::abs(y); 
13      } 
14    )
15  };
16
17  std::cout << "Result: " << Result;
18}

1Result: 15

std::reduce() Multithreading and Non-Deterministic Results

The std::reduce() algorithm is designed to be usable in multi-threaded environments. We cover multi-threading in detail later in the course, but for now, there is an implication we should be aware of.

Specifically, we cannot assume the objects in our input are always combined in the same order.

For example, if our operator function is func and our input is a collection comprising of a, b, and c, the std::reduce() algorithm might return the result of:

• func(a, func(b, c))
• func(b, func(a, c))
• func(func(c, a), b)
• or any other permutation

As such, std::reduce() is most commonly used with an operator that will return the same result, regardless of how its operands are combined or grouped. The words commutative and associative are sometimes used to describe these operators.

If the operator we use with std::reduce() is not commutative or not associative, the algorithm will be non-deterministic. That is, it may give a different return value each time it is run, even though the inputs are the same.

Using std::accumulate()

std::accumulate() is also available within <numeric>, and has a very similar use case as std::reduce(). The key difference is that std::accumulate() guarantees that the operands in our input range are combined in a consistent order - left to right.

This means its output will be deterministic, even if the operator isn’t commutative or associative.

The trade-off is this guaranteed sequencing is that std::accumulate() is single-threaded so, for larger tasks, it can be slower than std::reduce()

Similar to std::reduce(), the std::accumulate() algorithm combines elements using the + operator by default. The only difference is that the initial value isn’t optional:

1#include <iostream>
2#include <numeric> 
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::accumulate(Numbers.begin(), 
10                    Numbers.end(), 0)}; 
11
12  std::cout << "Result: " << Result;
13}

1Result: 15

We can change the operator in the usual way, by providing a 4th argument, and updating the initial value (the third argument) if needed:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  int Result{
9    std::accumulate(Numbers.begin(),
10                    Numbers.end(), 1,
11                    std::multiplies{})};
12
13  std::cout << "Result: " << Result;
14}

1120

Accumulating to a Different Type

Because of the guaranteed sequencing, std::accumulate() makes it easy to return a type that is different from the types of our input.

The type that will be returned is the type of our initial value - the third argument.

Below, we accumulate our integers to a float:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5int main(){
6  std::vector Nums{1, 2, 3};
7
8  std::cout << std::accumulate(
9    Nums.begin(), Nums.end(), 0.5f);
10};

16.5

When providing a custom operator for a scenario where the input and output types are different, it’s worth reviewing what its signature will be:

• Its first parameter will have the type of the initial value - what we passed as the third argument to std::accumulate()
• Its second parameter will have the type of our input objects
• Its return type will be the same as the first parameter type / initial value

The following example includes a lambda that implements the correct signature where we’re accumulating int objects to a float:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5int main(){
6  std::vector Nums{1, -2, 3};
7
8  auto Fun{
9    [](float f, int i) -> float{
10      return std::abs(f) + std::abs(i);
11    }};
12
13  std::cout << std::accumulate(
14    Nums.begin(), Nums.end(), 0.5f, Fun);
15};

16.5

In this more complex example, we accumulate our integers into a custom Accumulator type:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5struct Accumulator {
6  int Total{0};
7  int Count{0};
8
9  static Accumulator Add(Accumulator A, int V){
10    return {A.Total + V, A.Count + 1};
11  }
12
13  void Log(){
14    std::cout
15      << "Count: " << Count
16      << "\nSum: " << Total;
17    if (Count > 0) {
18      std::cout
19        << "\nAverage: "
20        << static_cast<float>(Total) / Count;
21    }
22  }
23};
24
25int main(){
26  std::vector Nums{99, 65, 26, 72, 17};
27
28  std::accumulate(
29    Nums.begin(), Nums.end(),
30    Accumulator{}, Accumulator::Add
31  ).Log();
32};

1Count: 5
2Sum: 279
3Average: 55.8

The std::reduce() algorithm can also reduce objects to a different type, including a custom type. However, it can involve a bit more effort to ensure everything is set up to work deterministically in a multi-threaded environment.

We cover those considerations in a dedicated section later in the course.

Changing the Accumulation Order

The std::accumulate() algorithm will always process elements in the input range from left to right. Many sequential containers over reverse iterators - rbegin() and rend() which allows std::accumulate() (and any other iterator-based algorithm) to proceed in reverse order:

1#include <iostream>
2#include <numeric>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3};
7
8  auto Log{
9    [](int x, int y){
10      std::cout << y << ", ";
11      return 0;
12    }};
13
14  std::cout << "Forward: ";
15  std::accumulate(
16    Numbers.begin(), Numbers.end(), 0, Log);
17
18  std::cout << "\nReverse: ";
19  std::accumulate(
20    Numbers.rbegin(), Numbers.rend(), 0, Log);
21}

1Forward: 1, 2, 3,
2Reverse: 3, 2, 1,

If reverse iterators are not available, we can also prepare our input using one of the other algorithms we covered earlier. For example, we can reverse our input using std::ranges::reverse(), or randomize it using std::ranges::shuffle(). We covered both of these in our earlier lesson on movement algorithms:

Movement Algorithms

An introduction to the 7 movement algorithms in the C++ standard library: move(), move_backward(), rotate(), reverse(), shuffle(), shift_left(), and shift_right().

Range-Based Techniques

C++23 includes std::ranges::fold_left(), which is effectively equivalent to std::accumulate(). We cover this and other fold algorithms in the next lesson.

A range-based variation of std::reduce() is likely to come in a future C++ version.

But for now, std::reduce() and std::accumulate() are iterator-based algorithms and are not directly compatible with ranges.

However, even though they don’t work with ranges directly, we can still use range-based techniques in the surrounding code to accomplish more complex tasks.

For example, below, we use a view to create a range that only includes the odd numbers of our input - 1 and 3 in this case. We then use the iterators the view provides to accumulate() only those odd numbers:

1#include <iostream>
2#include <numeric>
3#include <vector>
4#include <ranges>
5
6int main(){
7  std::vector Numbers{1, 2, 3};
8
9  auto V{
10    std::views::filter(Numbers, [](int i){
11      return i % 2 == 1;
12    })};
13
14  std::cout << "Result: "
15    << std::accumulate(V.begin(), V.end(), 0);
16}

1Result: 4

Summary

In this lesson, we've introduced how to simplify collections into single values using the std::reduce() and std::accumulate() algorithms.

Main Points Learned

• The std::reduce() algorithm, introduced in C++17, allows for parallel reduction of a sequence of values using a binary operation, potentially in a non-deterministic order.
• std::accumulate() operates sequentially from left to right, ensuring deterministic results even with non-commutative or non-associative operations, at the trade-off of being single-threaded.
• Identity values and their importance in initializing the reduce and accumulate operations, with examples including 0 for addition and 1 for multiplication.
• The use of custom operators with std::reduce() and std::accumulate() to perform complex accumulation tasks.
• Techniques for accumulating to different types, including custom types, with std::accumulate().
• How to reverse the accumulation order with std::accumulate() using reverse iterators.
• Introduction to range-based techniques and the anticipation of future C++ standards including range-based variations of these algorithms.

Next Lesson

C++23 Fold Algorithms

An introduction to the 6 new folding algorithms added in C++23, providing alternatives to std::reduce and std::accumulate

ContinueView Course