count()
, count_if()
, any_of()
, none_of()
, and all_of()
Let's take a look at some useful counting algorithms available in the standard library. To access these, we need the <algorithm>
header:
#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!
binary_search()
, lower_bound()
, upper_bound()
, and equal_range()
The standard library search functions covered in the previous lesson, like std::ranges::find()
, are examples of linear search. We can imagine the algorithm simply progressing through our container in a straight line, checking every object in turn until it finds what we’re looking for or reaches the end of the container.
If our containers have many objects or we’re searching frequently, this can degrade our performance. These are $O(n)$ algorithms - that is, they scale linearly with the size of the collection we’re searching. If we double the number of objects, the algorithm takes twice as long to complete on average.
If our container is sorted, we can instead use binary search algorithms, which have better performance.
std::ranges::subrange
When we want to create a non-owning view of some underlying container, we typically use the std::ranges::subrange
type from the <ranges>
header.
This lesson will provide a thorough overview of this type—how to create it, how to use it, and how to combine it with many of the other features introduced earlier in the chapter.
find()
, find_if()
, find_if_not()
, find_first_of()
, adjacent_find()
, search_n()
, search()
, and find_end()
.In this lesson, we cover the 8 most useful searching algorithms within the standard library: find
, find_if
, find_if_not
, find_first_of
, adjacent_find
, search_n
, search
, and find_end
.
All the algorithms in this section are available within the <algorithm>
header:
#include <algorithm>
We use these algorithms to traverse through our containers to find objects, or sequences of objects, in different ways.
This lesson introduces the 5 main standard library algorithms that are used when working with sets. A set is a collection of objects that does not include any duplicates. For example, the numbers 1
, 2
, and 3
are a set.
Within maths and computer science writing, a set is often denoted as a comma-separated list surrounded by braces, and we’ll use the same convention here.
For example, the set containing the numbers 1
, 2
, and 3
would be written
Some additional points are worth noting:
std::reduce()
and std::accumulate()
algorithmsIn 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:
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.
std::reduce
and std::accumulate
Similar to std::reduce()
and std::accumulate()
from the previous lesson, these algorithms are designed to work on collections of objects and to return a single result.
For example, if we had a collection of objects in our shopping basket and wanted to calculate the total cost of all the objects, the fold algorithms would be ideal.
They offer additional options over std::reduce()
and std::accumulate()
. Most notably, there are six different variants, giving us more control over how our collection is combined.
They are also range-based algorithms, which gives us more control over how we define the collection of objects we want to use as input.
All the algorithms in this lesson are available within the <algorithm>
header:
#include <algorithm>
In this lesson, we cover all of the main standard library algorithms that are used to compare two collections:
equal()
: Determine if two collections contain the same objects, in the same orderis_permutation()
: Determine if two collections contain the same objects, in any ordermismatch()
: Find the first position where two collections deviate from each otherlexicographical_compare()
: Determine if one collection is "less than" another collection.lexicographical_compare_three_way()
: Determine if one collection is less than, greater than or equal to another collectionstarts_with()
: Check if the objects in one collection match the objects at the start of another collectionends_with()
: Check if the objects in one collection match the objects at the end of another collectionincludes()
: Check if one collection contains another collection - that is, if one is a subset or superset of the otherAs a general goal, we want our code to be descriptive. In the very first lesson, we discussed the importance of having descriptive identifiers - which include variables and function names. A variable called Health
is more descriptive than one called x
.
The idea of custom types takes that idea further. Types like Distance
and Temperature
are inherently more descriptive than types like int
and float
.
In this lesson, we’ll see how we can even make values more descriptive. In the following code, it’s clear we’re adding a value of 3
to a variable called Distance
:
Distance += 3;
But three what? Three centimeters? Three meters? Three kilometers?
With user-defined literals, we can be more expressive:
Distance += 3_meters;
Distance += 4_kilometers;
Distance += 5_miles;
Behind the scenes, these literals are calling functions that we can define to meet our specific requirements. Let's see how we can set this up
Let's imagine we have the following custom type, which simply stores a value, and implements an ==
operator:
class Number {
public:
bool operator==(const Number& Other) const {
std::cout << "Hello from the == operator\n";
return Value == Other.Value;
}
int Value;
};
We create two objects of this type, and compare them using the !=
operator:
int main(){
Number A{1};
Number B{2};
if (A != B) { std::cout << "Not equal!"; }
}
Our type doesn’t have the !=
operator, so we’d expect this to fail. In C++17 and earlier, that’s exactly what happens:
error: binary '!=': 'Number' does not define this operator
But, from C++20 onwards, this program will compile, and run as we expect:
Hello from the == operator
Not equal!
This works because, behind the scenes, the compiler has rewritten our expression.