Summary

Algorithms

The C++ algorithm library is a collection of functions that are designed to make it easier to write correct, efficient, expressive and reusable code.

It provides a set of common, highly optimized algorithms that can be used to perform a variety of tasks, such as searching for an item in a list, sorting a collection of data, or manipulating the contents of a container.

One of the main benefits of using the algorithm library is that it allows you to write code that is easier to understand and less error prone. All the algorithms have almost universally recognized names which helps understanding what certain parts of code using them do without having to do a lot of digging. Because the algorithms from the standard library have been thoroughly tested and optimized, you can rely on them to work correctly and efficiently. This can save you time and effort when developing software and it can help to reduce the risk of introducing bugs into your code.

Another benefit of the algorithm library is that it promotes code reuse. By using the algorithms provided by the library, you can avoid having to reimplement common operations, which can save time and make it easier to maintain your code.

Overall, the C++ algorithm library is an important tool for C++ programmers that makes it easier to write reliable, efficient, and reusable code.

Usage

To use the algorithms you have to include the <algorithm> header, like so:

#include <algorithm>

Then you can use them in code:

Rangified version

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = { 5, 12, 2137, 1, -5, 22, 96 };
    std::ranges::sort(numbers);

    for(int number : numbers) {
        std::cout << number << ' ';
    }
}

Result (console)

-5 1 5 12 22 96 2137

Ordinary version

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = { 5, 12, 2137, 1, -5, 22, 96 };
    std::sort(numbers.begin(), numbers.end());

    for(int number : numbers) {
        std::cout << number << ' ';
    }
}

Result (console)

-5 1 5 12 22 96 2137

Rangified vs ordinary version

As you can see in the example above, there are two versions of algorithms. The rangified one and the ordinary one. The rangified version came to C++ with the C++20 standard. If you have a new enough compiler, you should be able to use it.

The basic difference between the two is that the ordinary version only accepts iterators, while the rangified version is more convenient and allows one to pass the whole range and enables the use of projections.

The rangified version is also less error-prone, as you can't pass invalid iterators by mistake (it also handles a few advanced things better than the ordinary version).

All that being said, using the rangified version is more beneficial and convenient, so if you have a possibility of choosing so, prefer the rangified version.

Ranges and iterators

Iterators

Iteration is the action of repeating a process, in case of containers, iteration means traversing the container in a particular order while obtaining each of it's elements.

Iterators are special objects with pointer semantics (having semantics of something basically means acting like something, pointer semantics mean that the iterator objects act like pointers in most ways, they can be dereferenced, incremented, etc.. Pointers are also valid iterators), that are used to iterate over containers (like strings, arrays, maps, sets, etc.).

They are obtained via the begin() and end() functions, and their variants:

• cbegin()/cend() - return a const iterator to a container (you cannot change the contents via it)
• rbegin()/rend() - return a reverse iterator to a container (iteration in reverse order)
• crbegin()/crend() - return a const reverse iterator to a container (iteration in reverse order and you cannot change the contents via it)

Not every container has all the variations, for example std::unordered_set doesn't have the r and cr versions.

Different iterators have different types and they work a little bit differently, but the most basic things you can do with an iterator is:

• increment it (it++ and ++it), which traverses onto the next object in a container
• dereference it (*it), which returns the value that the iterator points to

Here are a few examples of using iterators with std::vector:

Printing vector

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = { 5, 12, 2137, 1, -5, 22, 96 };

    // We obtain the iterator here,
    // we use  the `c` version because we don't intend to change the contents of the vector,
    // we only want to print it
    std::vector<int>::const_iterator begin = numbers.cbegin();
    std::vector<int>::const_iterator end = numbers.cend();

    // here we first check if begin is not equal to end, if it is, then we've traversed the entire container
    // if it's not, we print the number
    // then we increment the iterator
    for(; begin != end; ++begin) {
        // *begin means "access the element the iterator points to"
        std::cout << *begin << ' ';
    }
}

Result (console)

5 12 2137 1 -5 22 96

Printing vector in reverse

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = { 5, 12, 2137, 1, -5, 22, 96 };

    // We obtain the reverse iterator here,
    // we use  the `c` version because we don't intend to change the contents of the vector,
    // we only want to print it
    std::vector<int>::const_reverse_iterator begin = numbers.crbegin();
    std::vector<int>::const_reverse_iterator end = numbers.crend();

    // here we first check if begin is not equal to end, if it is, then we've traversed the entire container
    // if it's not, we print the number
    // then we increment the iterator
    for(; begin != end; ++begin) {
        // *begin means "access the element the iterator points to"
        std::cout << *begin << ' ';
    }
}

Result (console)

96 22 -5 1 2137 12 5

Zeroing vector

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = { 5, 12, 2137, 1, -5, 22, 96 };

    // We obtain the iterator here,
    // we use the ordinary version because we do intend to change the contents of the vector,
    std::vector<int>::iterator begin = numbers.begin();
    std::vector<int>::iterator end = numbers.end();

    // here we first check if begin is not equal to end, if it is, then we've traversed the entire container
    // if it's not, we print the number
    // then we increment the iterator
    for(; begin != end; ++begin) {
        // *begin means "access the element the iterator points to"
        *begin = 0;
    }

    // Let's print out the container and see the result:

    // NOTE: we have to reassign the value to begin because we've changed it while iterating over it
    begin = numbers.begin();
    for(; begin != end; ++begin) {
        // *begin means "access the element the iterator points to"
        *begin = 0;
    }
}

Result (console)

0 0 0 0 0 0 0

Now, notice how we had to manually specify the type (std::vector<int>::iterator, std::vector<int>::reverse_iterator, etc.) every time. It is not very convenient. For that purpose you can use the auto placeholder:

auto begin = numbers.begin();

auto begin = numbers.rbegin();

auto begin = numbers.crbegin();

auto deduces the type for us and it has no performance penalty. The code is easier to read that way, so if you can, prefer it. Read more about it here: auto.

Ranges

Now what exactly is a range? The exact definition and inner workings in C++ are a little bit complicated, but a range can be defined as anything that we can iterate over. An array, vector, string, map, etc..

All rangified algorithms accept a range. The same way iterators can be different types and have slightly different behaviours, some ranges also differ from others and cannot be used with some algorithms.

List of algorithms

Non-modifying

Rangified

Rangified

pub	ranges::count (since C++20)	Returns the number of certain elements.
pub	count	Returns the number of certain elements.
pub	ranges::count_if (since C++20)	Returns the number of elements satisfying specific criteria.
pub	count_if	Returns the number of elements satisfying specific criteria.

Modifying

Rangified

Rangified

pub	ranges::transform (since C++20)	Applies a function to a range of elements.
pub	transform	Applies a function to a range of elements.
pub	ranges::reverse (since C++20)	Reverses the order of elements.
pub	reverse	Reverses the order of elements.

Partitioning

Sorting

Rangified

pub	ranges::sort (since C++20)	Sorts a range into (by default) ascending order.
pub	sort	Sorts a range into (by default) ascending order.

Binary search

Other operations on sorted ranges

Set

Heap

Min/max

Rangified

Rangified

pub	ranges::min (since C++20)	Returns the smallest of the given values.
pub	min	Returns the smallest of the given values.
pub	ranges::max (since C++20)	Returns the greatest of the given values.
pub	max	Returns the greatest of the given values.

Comparison

Permutation

Numeric

Operations on uninitialized memory

C algorithms