Algorithm (C++)

In the C++ Standard Library, the algorithms library provides various functions that perform algorithmic operations on containers and other sequences, represented by Iterators.^[1]

The C++ standard provides some standard algorithms collected in the <algorithm> standard header.^[2] A handful of algorithms are also in the <numeric> header. All algorithms are in the std namespace.

Execution policies

C++17 provides the ability for many algorithms to optionally take an execution policy, which may allow implementations to execute the algorithm in parallel (i.e. by using threads or SIMD instructions).

There are four different policy types, each indicating different semantics about the order in which element accesses are allowed to be observed relative to each other

sequenced_policy, which indicates that the execution of the algorithm must happen on the thread which invokes the function, and the order of element accesses should execute in sequence. It is equivalent to calling the function without an execution policy
parallel_policy, which indicates that the execution of the algorithm may happen across multiple threads, however within each thread the order of element accesses are made in sequence (i.e. element accesses may not be done concurrently)
parallel_unsequenced_policy, which indicates that the execution of the algorithm may happen across multiple threads, and element accesses do not have to be performed in order within the same thread
unsequenced_policy, which indicates that the execution of the algorithm must happen on the thread which invokes the function, however the order of element accesses may be performed out of sequence

It is up to the user to ensure that the operations performed by the function are thread safe when using policies which may execute across different threads.

Ranges

C++20 adds versions of the algorithms defined in the <algorithm> header which operate on ranges rather than pairs of iterators.

The ranges versions of algorithm functions are scoped within the ranges namespace. They extend the functionality of the basic algorithms by allowing iterator-sentinel pairs to be used instead of requiring that both iterators be of the same type and also allowing interoperability with the objects provided by the ranges header without requiring the user to manually extract the iterators.

Non-modifying sequence operations

Predicate checking algorithms

Checks if a given predicate evaluates to true for some amount of objects in the range, or returns the amount of objects that do

all_of
any_of
none_of
count
count_if
contains

Comparison algorithms

Compares two ranges for some property

mismatch
equal
lexicographical_compare
contains_subrange
starts_with
ends_with
is_permutation

Searching algorithms

Finds the first or last position in a range where the subsequent elements satisfy some predicate

find
find_if
find_if_not
find_last
find_last_if
find_last_if_not
find_end
find_first_of
adjacent_find
search
search_n
partition_point

Binary search algorithms

Provides Binary search operations on ranges. It is undefined behaviour to use these on ranges which are not sorted.

binary_search
upper_bound
lower_bound
equal_range

Maximum/Minimum search algorithms

Finds the maximum or minimum element in a range, as defined by some comparison predicate

max_element
min_element
minmax_element

Property checking algorithms

Checks if an entire range satisfies some property

is_partitioned
is_sorted
is_heap

Modifying sequence operations

Copying algorithms

Transfers the elements from one range into another

copy
copy_if
copy_backward
move
move_backward
reverse_copy
rotate_copy
unique_copy
sample

Partitioning algorithms

Moves the elements of a range in-place so the range is partitioned with respect to some property

unique
remove
remove_if
partition
partition_copy
stable_partition

Sorting algorithms

Sorts or partially sorts a range in-place

sort
partial sort
stable_sort
nth_element

Populating algorithms

Populates a given range without reading the values contained within

fill
generate
iota

Transforming algorithms

Transforms each element of a given range in-place

for_each
transform
replace
replace_if
clamp

Reordering algorithms

Changes the order of elements within a range in-place

shuffle
shift_left
shift_right
reverse
rotate

Heap algorithms

Provides algorithms to create, insert, and remove elements from a max heap

[[Max heap|make_heap]]
[[Max heap|push_heap]]
[[Max heap|pop_heap]]
[[Max heap|sort_heap]]

References

^ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages - C++ §25 Algorithms library [lib.algorithms] para. 1
^ Stroustrup, Bjarne (2009). Programming : principles and practice using C++. Upper Saddle River, NJ: Addison-Wesley. p. 729. ISBN 9780321543721. Retrieved 22 March 2012. The standard library algorithms are found in <algorithm>.