Algorithms

The use of containers from the standard library is widely employed among C++ programmers. It's rare to find C++ code bases without references to std::vector or std::string, for example. However, in my experience, standard library algorithms are much less frequently used, even though they offer the same kind of benefits as containers:

• They can be used as building blocks when solving complex problems
• They are well documented (including references, books, and videos)
• Many C++ programmers are already familiar with them
• Their space and runtime costs are known (complexity guarantees)
• Their implementations are well crafted and efficient

If this wasn't enough, C++ features such as lambdas, execution policies, concepts, and ranges have all made the standard algorithms more powerful and, at the same time, friendlier to use.

In this chapter, we will take a look at how we can write efficient algorithms in C++ using the...

Introducing the standard library algorithms

Integrating the standard library algorithms into your C++ vocabulary is important. In this introduction, I will present a set of common problems that can be solved effectively by using the standard library algorithms.

C++20 comes with a dramatic change to the Algorithm library by the introduction of the Ranges library and the language feature of C++ concepts. So, before we start, we need a brief background of the history of the C++ standard library.

Evolution of the standard library algorithms

You have probably heard about STL algorithms or STL containers. And hopefully, you have heard about the new Ranges library introduced with C++20. There have been a lot of additions to the standard library in C++20. And before going further, I need to clear up some terminology. We'll start with the STL.

The STL, or the Standard Template Library, was initially the name of a library added to the C++ standard library in the 1990s...

Iterators and ranges

As seen in the previous examples, the standard library algorithms operate on iterators and ranges rather than container types. This section will focus on iterators and the new concept of ranges introduced in C++20. Using containers and algorithms correctly becomes easy once you have grasped iterators and ranges.

Introducing iterators

Iterators form the basis of the standard library algorithms and ranges. Iterators are the glue between data structures and algorithms. As you have already seen, C++ containers store their elements in very different ways. Iterators provide a generic way to navigate through the elements in a sequence. By having algorithms operate on iterators rather than container types, the algorithms become more generic and flexible since they do not depend on the type of container and the way the containers arrange their elements in memory.

At its core, an iterator is an object that represents a position in a sequence. It has two main...

Features of the standard algorithms

To get a better understanding of the standard algorithms, it's good to know a bit about the features and common patterns used by all algorithms in the <algorithm> header. As already stated, the algorithms under the std and std::ranges namespaces have a lot in common. We will start here with the general principles that are true for both the std algorithms and the constrained algorithms under std::range. Then, in the next section, we will move on to discuss the features that are specific to the constrained algorithms found under std::ranges.

Algorithms do not change the size of the container

Functions from <algorithm> can only modify the elements in a specified range; elements are never added or deleted from the underlying container. Therefore, these functions never alter the size of the container that they operate on.

For example, std::remove() or std::unique() do not actually remove elements from a container (despite...

Writing and using generic algorithms

The Algorithm library contains generic algorithms. To keep things as concrete as possible here, I will show an example of how a generic algorithm can be implemented. This will provide you with some insights into how to use the standard algorithms and at the same time demonstrate that implementing a generic algorithm is not that hard. I will intentionally avoid explaining all the details about the example code here, because we will spend a lot of time on generic programming later on in this book.

In the examples that follow, we will transform a simple non-generic algorithm into a full-fledged generic algorithm.

Non-generic algorithms

A generic algorithm is an algorithm that can be used with various ranges of elements, not only one specific type, such as std::vector. The following algorithm is an example of a non-generic algorithm that only works with std::vector<int>:

auto contains(const std::vector<int>& arr...

Best practices

Let's consider practices that will help you out when working with the algorithms we've been discussing. I will start by highlighting the importance of actually exploiting the standard algorithms.

Using the constrained algorithms

The constrained algorithms under std::ranges introduced with C++20 offer some benefits over the iterator-based algorithms under std. The constrained algorithms do the following:

• Support projections, which simplifies custom comparisons of elements.
• Support ranges instead of iterator pairs. There is no need to pass begin() and end() iterators as separate arguments.
• Are easy to use correctly and provide descriptive error messages during compilation as a result of being constrained by C++ concepts.

It's my recommendation to start using the constrained algorithms over the iterator-based algorithms.

You may have noticed that this book uses iterator-based algorithms in a lot of places...

Summary

In this chapter, you learned how to use the basic concepts in the Algorithm library, the advantages of using them as building blocks instead of handwritten for-loops, and why using the standard Algorithm library is beneficial for optimizing your code at a later stage. We also discussed the guarantees and trade-offs of the standard algorithms, meaning that you can, from now on, use them with confidence.

By using the advantages of the algorithms instead of manual for-loops, your code base is well prepared for the parallelization techniques that will be discussed in the coming chapters of this book. One key feature that the standard algorithms are missing is the possibility to compose algorithms, something that was highlighted when we tried to avoid unnecessary container copies. In the next chapter, you will learn how to use views from the C++ Ranges library to overcome this limitation of standard algorithms.