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
- Ordinary 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
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
- Printing vector in reverse
- 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 `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
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
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
Searching
| pub | ranges::find (since C++20) | Finds the first element satisfying specific criteria. |
| pub | find | Finds the first element satisfying specific criteria. |
| pub | ranges::find_if (since C++20) | Finds the first element satisfying specific predicate. |
| pub | find_if | Finds the first element satisfying specific predicate. |
| pub | ranges::find_if_not (since C++20) | Finds the first element **not** satisfying specific predicate. |
| pub | find_if_not (since C++11) | Finds the first element **not** satisfying specific predicate. |
| pub | ranges::find_first_of (since C++20) | Searches for any of the elements from one range in another. |
| pub | find_first_of | Searches for any of the elements from one range in another. |
| pub | ranges::find_end (since C++20) | Finds the last sequence of elements in a certain range. |
| pub | find_end | Finds the last sequence of elements in a certain range. |
| pub | ranges::find_last (since C++20) | Finds the last element equal to some value. |
| pub | ranges::find_last_if (since C++20) | Finds the last element satisfying specific criteria. |
| pub | ranges::find_last_if_not (since C++20) | Finds the last element **not** satisfying specific criteria. |
| pub | ranges::adjacent_find (since C++20) | Finds the first two adjacent items that satisfy a condition. |
| pub | adjacent_find | Finds the first two adjacent items that satisfy a condition. |
| pub | ranges::search (since C++20) | Search for a range of elements. |
| pub | search | Search for a range of elements. |
| pub | ranges::search_n (since C++20) | Searches a range for a consecutive sequence of an element. |
| pub | search_n | Searches a range for a consecutive sequence of an element. |
Determining conditions
| pub | ranges::all_of (since C++20) | Checks if all elements in a range hold a condition. |
| pub | all_of (since C++11) | Checks if all elements in a range hold a condition. |
| pub | ranges::any_of (since C++20) | Checks if any elements in a range hold a condition. |
| pub | any_of (since C++11) | Checks if any elements in a range hold a condition. |
| pub | ranges::none_of (since C++20) | Checks if no elements in a range hold a condition. |
| pub | none_of (since C++11) | Checks if no elements in a range hold a condition. |
| 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. |
| pub | ranges::mismatch (since C++20) | Finds the first position where two ranges differ. |
| pub | mismatch | Finds the first position where two ranges differ. |
| pub | ranges::starts_with (since C++20) | Checks whether a range starts with another range. |
| pub | ranges::ends_with (since C++20) | Checks whether a range ends with another range. |
Other non-modifying
| pub | ranges::for_each (since C++20) | Applies a function to a range of elements. |
| pub | for_each | Applies a function to a range of elements. |
| pub | ranges::for_each_n (since C++20) | Applies a function to a range of elements consisting of an iterator and a size. |
| pub | for_each_n (since C++17) | Applies a function to a range of elements consisting of an iterator and a size. |
Random operations
| pub | random_shuffle (removed in C++17) | Deprecated in C++14 and removed in C++17, use std::shuffle instead. Randomly re-orders elements in a range. |
| pub | ranges::shuffle (since C++20) | Randomly re-orders elements in a range. |
| pub | shuffle (since C++11) | Randomly re-orders elements in a range. Preffered method over std::random_shuffle. |
| pub | ranges::sample (since C++20) | Selects n random elements from a sequence. |
| pub | sample (since C++17) | Selects n random elements from a sequence. |
Modifying
| pub | swap | Swaps the values of two objects. |
| pub | ranges::copy (since C++20) | Copies a range of elements to a new location. |
| pub | copy | Copies a range of elements to a new location. |
| pub | ranges::copy_if (since C++20) | Copies elements from a range that satisfy a condition to a new location. |
| pub | copy_if (since C++11) | Copies elements from a range that satisfy a condition to a new location. |
| pub | ranges::copy_n (since C++20) | Copies a number elements from a range to a new location. |
| pub | copy_n (since C++11) | Copies a number elements from a range to a new location. |
| pub | ranges::copy_backward (since C++20) | Copies a range of elements in backwards order. |
| pub | copy_backward | Copies a range of elements in backwards order. |
| pub | ranges::move (since C++20) | Moves a range of elements to a new location. |
| pub | move | Moves a range of elements to a new location. |
| pub | ranges::move_backward (since C++20) | Moves a range of elements to a new location in backwards order. |
| pub | move_backward | Moves a range of elements to a new location in backwards order. |
| 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. |
| pub | ranges::reverse_copy (since C++20) | Creates a reversed copy of a range. |
| pub | reverse_copy | Creates a reversed copy of a range. |
| pub | ranges::fill (since C++20) | Copy-assigns the given value to every element in a range. |
| pub | fill | Copy-assigns the given value to every element in a range. |
| pub | ranges::fill_n (since C++20) | Copy-assigns a value to a number of elements. |
| pub | fill_n | Copy-assigns a value to a number of elements. |
| pub | ranges::generate (since C++20) | Assigns the results of successive function calls to every element in a range. |
| pub | generate | Assigns the results of successive function calls to every element in a range. |
| pub | ranges::remove (since C++20) | Removes elements equal to value. |
| pub | remove | Removes elements equal to value. |
| pub | ranges::remove_if (since C++20) | Removes elements satisfying specific criteria. |
| pub | remove_if | Removes elements satisfying specific criteria. |
| pub | ranges::remove_copy (since C++20) | Copies a range of elements omitting those that are equal to value. |
| pub | remove_copy | Copies a range of elements omitting those that are equal to value. |
| pub | ranges::remove_copy_if (since C++20) | Copies a range of elements omitting those that satisfy a predicate. |
| pub | remove_copy_if | Copies a range of elements omitting those that satisfy a predicate. |
| pub | ranges::replace (since C++20) | Replaces old values with new values. |
| pub | replace | Replaces old values with new values. |
| pub | ranges::replace_if (since C++20) | Replaces values satisfying a predicate with new values. |
| pub | replace_if | Replaces values satisfying a predicate with new values. |
| pub | ranges::replace_copy (since C++20) | Copies a range, replacing elements equal to old value with new value. |
| pub | replace_copy | Copies a range, replacing elements equal to old value with new value. |
| pub | ranges::replace_copy_if (since C++20) | Copies a range, replacing elements that satisfy a predicate with new value. |
| pub | replace_copy_if | Copies a range, replacing elements that satisfy a predicate with new value. |
| pub | ranges::swap_ranges (since C++20) | Swaps two ranges. |
| pub | swap_ranges | Swaps two ranges. |
| pub | iter_swap | Swaps the values of the elements the given iterators are pointing to. |
| pub | ranges::rotate (since C++20) | Rotates elements in a range. |
| pub | rotate | Rotates elements in a range. |
| pub | ranges::rotate_copy (since C++20) | Copies and rotates a range of elements. |
| pub | rotate_copy | Copies and rotates a range of elements. |
| pub | ranges::shift_left (since C++23) | Shifts elements in a range left. |
| pub | shift_left (since C++20) | Shifts elements in a range left. |
| pub | ranges::shift_right (since C++23) | Shifts elements in a range right. |
| pub | shift_right (since C++20) | Shifts elements in a range right. |
| pub | ranges::unique (since C++20) | Removes consecutive duplicates of an element in a range. |
| pub | unique | Removes consecutive duplicates of an element in a range. |
| pub | ranges::unique_copy (since C++20) | Creates a copy of range with no consecutive duplicates. |
| pub | unique_copy | Creates a copy of range with no consecutive duplicates. |
Partitioning
| pub | ranges::is_partitioned (since C++20) | Determines if the range is partitioned by the given predicate. |
| pub | is_partitioned (since C++11) | Determines if the range is partitioned by the given predicate. |
| pub | ranges::partition (since C++20) | Divides a range of elements into two groups based on a predicate. |
| pub | partition (since C++11) | Divides a range of elements into two groups based on a predicate. |
| pub | ranges::partition_copy (since C++20) | Copies a range dividing the elements into two groups. |
| pub | partition_copy (since C++11) | Copies a range dividing the elements into two groups. |
| pub | ranges::stable_partition (since C++20) | Divides elements into two groups while preserving their relative order. |
| pub | stable_partition | Divides elements into two groups while preserving their relative order. |
| pub | ranges::partition_point (since C++20) | Locates the partition point of a range. |
| pub | partition_point (since C++11) | Locates the partition point of a range. |
Sorting
| pub | ranges::sort (since C++20) | Sorts a range into (by default) ascending order. |
| pub | sort | Sorts a range into (by default) ascending order. |
| pub | ranges::stable_sort (since C++20) | Sorts a range into (by default) ascending order while preserving the order between equal elements. |
| pub | stable_sort | Sorts a range into (by default) ascending order while preserving the order between equal elements. |
| pub | ranges::partial_sort (since C++20) | Sorts the first N elements of a range. |
| pub | partial_sort | Sorts the first N elements of a range. |
| pub | ranges::partial_sort_copy (since C++20) | Copies and partially sorts a range of elements. |
| pub | partial_sort_copy | Copies and partially sorts a range of elements. |
| pub | ranges::stable_sort (since C++20) | Partially sorts the given range making sure that it is partitioned by the given element. |
| pub | stable_sort | Partially sorts the given range making sure that it is partitioned by the given element. |
| pub | ranges::is_sorted (since C++20) | Checks whether a range is sorted. |
| pub | is_sorted | Checks whether a range is sorted. |
| pub | ranges::is_sorted_until (since C++20) | Finds the largest sorted subrange. |
| pub | is_sorted_until | Finds the largest sorted subrange. |
Binary search (on sorted ranges)
| pub | ranges::binary_search (since C++20) | Searches for an element in a partially-ordered range. |
| pub | binary_search | Searches for an element in a partially-ordered range. |
| pub | ranges::lower_bound (since C++20) | Returns an iterator to the first element not less than the given value. |
| pub | lower_bound | Returns an iterator to the first element not less than the given value. |
| pub | ranges::upper_bound (since C++20) | Returns an iterator to the first element greater than the given value. |
| pub | upper_bound | Returns an iterator to the first element greater than the given value. |
| pub | ranges::equal_range (since C++20) | Returns range of elements matching a specific key. |
| pub | equal_range | Returns range of elements matching a specific key. |
Set (on sorted ranges)
| pub | ranges::includes (since C++20) | Returns true if a sequence is a subsequence of another. |
| pub | includes | Returns true if a sequence is a subsequence of another. |
| pub | ranges::set_difference (since C++20) | Computes the difference between two sets. |
| pub | set_difference | Computes the difference between two sets. |
| pub | ranges::set_intersection (since C++20) | Computes the intersection between two sets. |
| pub | set_intersection | Computes the intersection between two sets. |
| pub | ranges::set_symmetric_difference (since C++20) | Computes the symmetric difference between two sets. |
| pub | set_symmetric_difference | Computes the symmetric difference between two sets. |
| pub | ranges::set_union (since C++20) | Computes the union between two sets. |
| pub | set_union | Computes the union between two sets. |
Other operations on sorted ranges
| pub | ranges::merge (since C++20) | Merges two sorted ranges. |
| pub | merge | Merges two sorted ranges. |
| pub | ranges::inplace_merge (since C++20) | Merges two sorted ranges in-place. |
| pub | inplace_merge | Merges two sorted ranges in-place. |
Heap
| pub | ranges::is_heap (since C++20) | Checks if the given range is a max heap. |
| pub | is_heap | Checks if the given range is a max heap. |
| pub | ranges::is_heap_until (since C++20) | Checks if the given range is a max heap. |
| pub | is_heap_until | Checks if the given range is a max heap. |
| pub | ranges::make_heap (since C++20) | Creates a max heap out of a range of elements. |
| pub | make_heap | Creates a max heap out of a range of elements. |
| pub | ranges::push_heap (since C++20) | Adds an element to a max heap. |
| pub | push_heap | Adds an element to a max heap. |
| pub | ranges::pop_heap (since C++20) | Adds an element to a max heap. |
| pub | pop_heap | Adds an element to a max heap. |
| pub | ranges::sort_heap (since C++20) | Turns a max heap into a range of elements sorted in ascending order. |
| pub | sort_heap | Turns a max heap into a range of elements sorted in ascending order. |
Min/max
| 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. |
| pub | ranges::max_element (since C++20) | Returns the largest element in a range. |
| pub | max_element | Returns the largest element in a range. |
| pub | ranges::min_element (since C++20) | Returns the smallest element in a range. |
| pub | min_element | Returns the smallest element in a range. |
| pub | ranges::minmax (since C++20) | Returns the smallest and largest from the given values. |
| pub | minmax | Returns the smallest and largest from the given values. |
| pub | ranges::minmax_element (since C++20) | Returns the smallest and the largest elements in a range. |
| pub | minmax_element | Returns the smallest and the largest elements in a range. |
| pub | ranges::clamp (since C++20) | Clamps a value between a pair of boundary values. |
| pub | clamp | Clamps a value between a pair of boundary values. |
Comparison
| pub | ranges::equal (since C++20) | Determines if two sets of elements are the same. |
| pub | equal | Determines if two sets of elements are the same. |
| pub | ranges::lexicographical_compare (since C++20) | Returns true if one range is lexicographically less than another. |
| pub | lexicographical_compare | Returns true if one range is lexicographically less than another. |
| pub | lexicographical_compare_three_way | Compares two ranges using three-way comparison. |
Permutation
| pub | ranges::is_permutation (since C++20) | Determines if a sequence is a permutation of another sequence. |
| pub | is_permutation (since C++11) | Determines if a sequence is a permutation of another sequence. |
| pub | ranges::next_permutation (since C++20) | Generates the next greater lexicographic permutation of a range of elements. |
| pub | next_permutation (since C++11) | Generates the next greater lexicographic permutation of a range of elements. |
| pub | ranges::prev_permutation (since C++20) | Generates the prev smaller lexicographic permutation of a range of elements. |
| pub | prev_permutation (since C++11) | Generates the prev smaller lexicographic permutation of a range of elements. |
Numeric
| pub | ranges::iota (since C++23) | Fills a range with successive increments of the starting value. |
| pub | iota (since C++11) | Fills a range with successive increments of the starting value. |
| pub | accumulate | Sums up or folds/reduces a range of elements. |
| pub | inner_product | Computes the inner product of two ranges of elements. |
| pub | adjacent_difference | Computes the differences between adjacent elements in a range. |
| pub | partial_sum | Computes the partial sum of a range of elements. |
| pub | reduce (since C++17) | Similar to std::accumulate, except out of order. |
| pub | exclusive_scan (since C++17) | Similar to std::partial_sum, excludes the ith input element from the ith sum. |
| pub | inclusive_scan (since C++17) | Similar to std::partial_sum, includes the ith input element from the ith sum. |
| pub | transform_reduce (since C++17) | Applies an invocable, then reduces out of order. |
| pub | transform_exclusive_scan (since C++17) | Applies an invocable, then calculates exclusive scan. |
| pub | transform_inclusive_scan (since C++17) | Applies an invocable, then calculates inclusive scan. |
Operations on uninitialized memory
| pub | uninitialized_copy | Copies a range of objects to an uninitialized area of memory. |
| pub | uninitialized_copy | Copies a range of objects to an uninitialized area of memory. |
| pub | uninitialized_copy_n | Copies an amount of elements from a range to an uninitialized area of memory. |
| pub | uninitialized_copy_n | Copies an amount of elements from a range to an uninitialized area of memory. |
| pub | uninitialized_fill | Fills an uninitialized range. |
| pub | uninitialized_fill | Fills an uninitialized range. |
| pub | uninitialized_fill_n | Fills an uninitialized range defined by start and count. |
| pub | uninitialized_fill_n | Fills an uninitialized range defined by start and count. |
| pub | uninitialized_fill_n | Fills an uninitialized range defined by start and count. |
| pub | uninitialized_fill_n | Fills an uninitialized range defined by start and count. |
| pub | uninitialized_move (since C++17) | Moves a number of objects to an uninitialized area of memory. |
| pub | uninitialized_move | Moves a number of objects to an uninitialized area of memory. |
| pub | uninitialized_move_n (since C++17) | Moves a number of objects to an uninitialized area of memory. |
| pub | uninitialized_move_n | Moves a number of objects to an uninitialized area of memory. |
| pub | uninitialized_default_construct (since C++17) | Constructs objects by default-initialization in an uninitialized area of memory, defined by a range. |
| pub | uninitialized_default_construct | Moves a number of objects to an uninitialized area of memory. |
| pub | uninitialized_default_construct_n (since C++17) | Constructs objects by default-initialization in an uninitialized area of memory, defined by a start and a count. |
| pub | uninitialized_default_construct_n | Constructs objects by default-initialization in an uninitialized area of memory, defined by a start and a count. |
| pub | uninitialized_value_construct (since C++17) | Constructs objects by value-initialization in an uninitialized area of memory, defined by a range. |
| pub | uninitialized_value_construct | Constructs objects by value-initialization in an uninitialized area of memory, defined by a range. |
| pub | uninitialized_value_construct_n (since C++17) | Constructs objects by value-initialization in an uninitialized area of memory, defined by a start and size. |
| pub | uninitialized_value_construct_n | Constructs objects by value-initialization in an uninitialized area of memory, defined by a start and size. |
| pub | destroy (since C++17) | Destroys a range of objects. |
| pub | destroy | Destroys a range of objects. |
| pub | destroy_n (since C++17) | Destroys a number of objects. |
| pub | destroy_n | Destroys a number of objects. |
| pub | destroy_at (since C++17) | Destroys an object at a given address. |
| pub | destroy_at | Destroys an object at a given address. |
| pub | construct_at (since C++17) | Creates an object at a given address. |
| pub | construct_at | Creates an object at a given address. |
C algorithms
| pub | qsort | Sorts a range of elements with unspecified type. |
| pub | bsearch | Searches an array for an element of unspecified type. |