Counting Algorithms

Let's take a look at some useful counting algorithms available in the standard library. To access these, we need the <algorithm> header:

1#include <algorithm>

In this lesson, we cover the 5 most useful counting algorithms: count(), count_if(), any_of(), none_of() and all_of(). Let's get started!

std::ranges::count()

The std::ranges::count algorithm requires two arguments - the range we want to run the algorithm in, and the element we want to count within that range.

Whether or not an element matches what we’re looking for is determined by an equality check. Therefore, the type of elements in our collection must implement the equality operator, ==

In this example, we count the number of 4s in our vector of integers:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers { 1, 2, 3, 4, 4, 5 };
7  auto Fours { std::ranges::count(Numbers, 4) };
8  std::cout << "Count of fours: " << Fours;
9}

1Count of fours: 2

Return Type

The return type of these algorithms can be somewhat cryptic. For count(), the return type is a template:

1std::ranges::range_difference_t

Given we’re counting elements in a std::vector<int> in this case, the type returned from count() would be even more verbose:

1std::ranges::range_difference_t<std::vector<int>> Fours
2{
3  std::ranges::count(Numbers, 4)
4};

It’s common to just use auto in this scenario, as we did in the original example. Alternatively, it’s reasonable to implicitly cast the return value to something simpler, like a 64-bit integer or size_t:

1int64_t Fours { std::ranges::count(Numbers, 4) };

std::ranges::count_if()

The basic std::ranges::count() algorithm uses the equality operator == to determine if an element in our container matches the object we’re looking for.

The std::ranges::count_if() algorithm lets us change this behavior. Rather than using the == operator to determine if two objects are equal, count_if() uses a function, which we provide as an argument.

The function will be called for every object in the collection, receiving that object as an argument. Our function should return true if we want this object to be included in the count, and false otherwise. A function that returns a boolean is also known as a predicate.

Below, we have a predicate that returns true if a provided argument is even. We pass this predicate to std::ranges::count_if() to count the number of elements in our range that are even:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers { 1, 2, 3, 4, 4, 5 };
7  auto isEven{[](int x) { return x % 2 == 0; }};
8  auto EvenCount {
9    std::ranges::count_if(Numbers, isEven)
10  };
11  std::cout << "Even Count: " << EvenCount;
12}

1Even Count: 3

std::ranges::any_of()

The std::ranges::any_of() algorithm also accepts a predicate function. The algorithm will return true if our predicate returns true for any element in the range.

In the following example, we return true if any number in our collection is even:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers { 1, 2, 3, 4, 4, 5 };
7  auto isEven{[](int x) { return x % 2 == 0; } };
8  bool IncludesEven {
9    std::ranges::any_of(Numbers, isEven)};
10
11  std::cout << "An even number "
12            << (IncludesEven ? "is" : "is not")
13            << " included";
14}

1An even number is included

1bool IncludesEven {
2  std::ranges::count_if(Numbers, isEven) > 0
3};

std::ranges::none_of()

The std::ranges::none_of() algorithm will run a predicate on everything in our collection, and return true if every predicate returns false.

If our predicate returns true for any element in the collection, the algorithm will stop evaluating further elements, and return false.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers { 1, 2, 3, 4, 4, 5 };
7  auto isEven{ [](int x) { return x % 2 == 0; } };
8  bool NoEvenNumbers {
9    std::ranges::none_of(Numbers, isEven)};
10
11  std::cout << "The range contains "
12    << (NoEvenNumbers ? "no" : "some")
13    << " even numbers";
14}

1The range contains some even numbers

This algorithm will return true if the range has no elements:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers { };
7  auto isEven { [](int x) { return x % 2 == 0; } };
8  bool Result {
9    std::ranges::none_of(Numbers, isEven)};
10
11  std::cout << Result ? "true" : "false";
12}

1true

std::ranges::all_of()

The std::ranges::all_of() algorithm will run a predicate on everything in our collection, and return true if every invocation of the predicate returns true.

If our predicate returns false for any element in the collection, the algorithm will stop evaluating further elements, and return false.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers { 1, 2, 3, 4, 4, 5 };
7  auto isEven{[](int x) { return x % 2 == 0; }};
8  bool AllEvenNumbers {
9    std::ranges::all_of(Numbers, isEven)};
10
11  std::cout << "The range is "
12            << (AllEvenNumbers ? "all" : "NOT all")
13            << " even numbers";
14}

1The range is NOT all even numbers

Note, that this algorithm will return true if the range has no elements:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers{};
7  auto isEven{[](int x) { return x % 2 == 0; }};
8  bool Result{
9    std::ranges::all_of(Numbers, isEven)};
10
11  std::cout << Result ? "true" : "false";
12}

1true

Using Member Functions as Predicates

Typically when using these algorithms, the predicates we need will be class methods of the objects contained within our range. When that is the case, we generally don’t need to define a predicate function. We can just pass a reference to the class method:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Player Class|Show
5class Player {/*...*/};
18
19int main() {
20  std::vector Party {
21    Player{"Roderick", 100},
22    Player{"Anna", 200},
23    Player{"Robert", 500}
24  };
25
26  bool EveryoneAlive{std::ranges::all_of(
27    Party, &Player::isAlive)};
28
29  std::cout << "Everyone "
30            << (EveryoneAlive ? "is" : "is not")
31            << " alive";
32}

1Everyone is alive

Projection

All the algorithms in this lesson accept an additional optional argument, which can be a projection function. We cover projection in detail here:

Projection Functions

Learn to use projection functions to apply range-based algorithms on derived data

In this example, we project the objects in our container to their absolute value before running the count() algorithm. Two of those projections are equal to 1, so our algorithm returns 2:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int Projector(int x) { return std::abs(x); }
6
7int main() {
8  std::vector Nums{-2, -1, 0, 1, 2};
9
10  auto Count {std::ranges::count(
11      Nums, 1, Projector)};  
12
13  std::cout << "Count: " << Count;
14}

1Count: 2

In this example, we use Player::GetName() as our projection function, projecting our Player objects to a std::string before comparing them to the "Anna" string:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Player Class|Show
5class Player {/*...*/};
18
19int main() {
20  std::vector Party {
21    Player{"Roderick", 100},
22    Player{"Anna", 200},
23    Player{"Robert", 500}
24  };
25
26  auto AnnaCount{std::ranges::count(
27    Party, "Anna", &Player::GetName)};
28
29  std::cout << "AnnaCount: " << AnnaCount;
30}

1AnnaCount: 1

Using Iterators

As we covered in the introduction to range-based algorithms, std::ranges::count() and all the other algorithms we covered in this lesson allow us to define our range as an iterator-sentinel pair.

Below, we use this technique to exclude the first and last objects from our count:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4};
7  auto Fours{std::ranges::count(
8    Numbers.begin() + 1, Numbers.end() - 1, 4)};
9
10  std::cout << "Count of fours: " << Fours;
11}

1Count of fours: 1

The concept of a range was introduced in C++20. When targeting older specifications, we can use alternative versions of these algorithms that work directly with iterators instead.

These are available by omitting the ranges qualification from the identifiers. For example, the iterator variant of std::ranges::count() is available as std::count():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4, 5};
7  auto Fours{std::count(
8    Numbers.begin(), Numbers.end(), 4)};
9
10  std::cout << "Count of fours: " << Fours;
11}

1Count of fours: 2

Summary

In this lesson, we explored the counting algorithms that are part of the C++20 std::ranges library, and available by including the <algorithm> header.

Key Takeaways

• Understanding of std::ranges::count() for counting specific elements in a range.
• Use of std::ranges::count_if() to count elements that meet a predicate condition.
• Application of std::ranges::any_of(), none_of(), and all_of() for conditional checks across elements.
• Insight into the performance benefits of using specific algorithms like any_of() over alternatives like count_if() in certain scenarios.
• Using predicates in customizing the behavior of counting algorithms.
• How to use member functions as predicates for more complex conditions.
• The role of projection functions in transforming elements before applying counting algorithms.
• Review of using iterator-sentinel pairs for defining custom ranges.

Next Lesson

Minimum and Maximum Algorithms

An introduction to the 7 minimum and maximum algorithms in the C++ standard library: clamp(), min(), min_element(), max(), max_element(), minmax(), and minmax_element().

ContinueView Course