Counting Elements

Introduction

To gain some practice, let’s build an algorithm that counts the number of elements in a container. Our algorithm will be a version of another standard algorithm count_if.

The main idea is to use transform_reduce - a new “fused” algorithm. It first applies some unary function over an element and then performs a reduce operation.

To get the count of elements that satisfy some predicate, we can firstly filter each element (transform). We return 1 if the element passes the filter and 0 otherwise. Then, in the reduction step, we count how many elements returned 1.

Diagram

Here’s a diagram that illustrates the algorithm for a simple case: