Algorithms Library
Algorithms Library
com
Algorithms library
The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements. Note that a range is
defined as [ first , last ) where last refers to the element past the last element to inspect or modify.
Constrained algorithms
C++20 provides constrained versions of most algorithms in the namespace std::ranges. In these algorithms, a range can be specified as either an iterator-
sentinel pair or as a single range argument, and projections and pointer-to-member callables are supported. Additionally, the return types of most algorithms
(since C++20)
have been changed to return all potentially useful information computed during the execution of the algorithm.
(since C++17)
Execution policies
Most algorithms have overloads that accept execution policies. The standard library algorithms support several execution policies, and the library provides
corresponding execution policy types and objects. Users may select an execution policy statically by invoking a parallel algorithm with an execution policy
object of the corresponding type.
Standard library implementations (but not the users) may define additional execution policies as an extension. The semantics of parallel algorithms invoked
with an execution policy object of implementation-defined type is implementation-defined.
Parallel version of algorithms (except for std::for_each and std::for_each_n) are allowed to make arbitrary copies of elements from ranges, as long as both
std::is_trivially_copy_constructible_v<T> and std::is_trivially_destructible_v<T> are true , where T is the type of elements.
Defined in header <execution>
Defined in namespace std::execution
sequenced_policy (C++17)
parallel_policy (C++17) execution policy types
parallel_unsequenced_policy (C++17) (class)
unsequenced_policy (C++20)
seq (C++17)
par (C++17) global execution policy objects
par_unseq (C++17) (constant)
unseq (C++20)
Defined in namespace std
test whether a class represents an execution policy
is_execution_policy (C++17)
(class template)
[Link] 1/14
14/10/2024, 15:09 Algorithms library - [Link]
Feature-test macro Value Std Feature
__cpp_lib_parallel_algorithm 201603L (C++17) Parallel algorithms
201603L (C++17) Execution policies
__cpp_lib_execution
201902L (C++20) std::execution::unsequenced_policy
Batch operations
Search operations
[Link] 2/14
14/10/2024, 15:09 Algorithms library - [Link]
searches for any one of a set of elements
ranges::find_first_of (C++20)
(niebloid)
finds the first two adjacent items that are equal (or satisfy a given predicate)
adjacent_find
(function template)
finds the first two adjacent items that are equal (or satisfy a given predicate)
ranges::adjacent_find (C++20)
(niebloid)
count returns the number of elements satisfying specific criteria
count_if (function template)
Fold operations
[Link] 3/14
14/10/2024, 15:09 Algorithms library - [Link]
Copy operations
Swap operations
Transformation operations
replace replaces all values satisfying specific criteria with another value
replace_if (function template)
[Link] 4/14
14/10/2024, 15:09 Algorithms library - [Link]
ranges::replace (C++20) replaces all values satisfying specific criteria with another value
ranges::replace_if (C++20) (niebloid)
replace_copy copies a range, replacing elements satisfying specific criteria with another value
replace_copy_if (function template)
ranges::replace_copy (C++20) copies a range, replacing elements satisfying specific criteria with another value
ranges::replace_copy_if (C++20) (niebloid)
Generation operations
Removing operations
remove_copy copies a range of elements omitting those that satisfy specific criteria
remove_copy_if (function template)
ranges::remove_copy (C++20) copies a range of elements omitting those that satisfy specific criteria
ranges::remove_copy_if (C++20) (niebloid)
removes consecutive duplicate elements in a range
unique
(function template)
removes consecutive duplicate elements in a range
ranges::unique (C++20)
(niebloid)
creates a copy of some range of elements that contains no consecutive duplicates
unique_copy
(function template)
creates a copy of some range of elements that contains no consecutive duplicates
ranges::unique_copy (C++20)
(niebloid)
Order-changing operations
[Link] 5/14
14/10/2024, 15:09 Algorithms library - [Link]
reverses the order of elements in a range
reverse
(function template)
reverses the order of elements in a range
ranges::reverse (C++20)
(niebloid)
creates a copy of a range that is reversed
reverse_copy
(function template)
creates a copy of a range that is reversed
ranges::reverse_copy (C++20)
(niebloid)
rotates the order of elements in a range
rotate
(function template)
rotates the order of elements in a range
ranges::rotate (C++20) (niebloid)
copies and rotate a range of elements
rotate_copy
(function template)
copies and rotate a range of elements
ranges::rotate_copy (C++20)
(niebloid)
shift_left shifts elements in a range
(C++20)
shift_right (function template)
Sampling operations
Requirements
Some algorithms require the sequence represented by the arguments to be “sorted” or “partitioned”. The behavior is undefined if the requirement is not met.
A sequence is sorted with respect to a comparator comp if for every iterator iter pointing to the sequence and every non-negative integer n such that
(until C++20)
iter + n [1] is a valid iterator pointing to an element of the sequence, comp(*(iter + n), *iter) == false [1].
A sequence is sorted with respect to comp and proj for a comparator comp and projection proj if for every iterator iter pointing to the sequence and
every non-negative integer n such that iter + n [1] is a valid iterator pointing to an element of the sequence,
bool(std::invoke(comp, std::invoke(proj, *(iter + n)), (since C++20)
[1]
std::invoke(proj, *iter))) is false .
A sequence is sorted with respect to a comparator comp if the sequence is sorted with respect to comp and std::identity{} (the identity projection).
[Link] 6/14
14/10/2024, 15:09 Algorithms library - [Link]
A sequence [ start , finish ) is partitioned with respect to an expression f(e) if there exists an integer n such that for all i in [
0,
std::distance(start, finish) ), f(*(start + i)) [1] is true if and only if i < n .
1. ↑ 1.0 1.1 1.2 1.3 1.4 iter + n simply means “the result of iter being incremented n times”, regardless of whether iter is a random access iterator.
Partitioning operations
Sorting operations
[Link] 7/14
14/10/2024, 15:09 Algorithms library - [Link]
finds the largest sorted subrange
is_sorted_until (C++11)
(function template)
finds the largest sorted subrange
ranges::is_sorted_until (C++20)
(niebloid)
partially sorts the given range making sure that it is partitioned by the given
nth_element element
(function template)
partially sorts the given range making sure that it is partitioned by the given
ranges::nth_element (C++20) element
(niebloid)
[Link] 8/14
14/10/2024, 15:09 Algorithms library - [Link]
computes the symmetric difference between two sets
ranges::set_symmetric_difference (C++20)
(niebloid)
Heap operations
A random access range [ first , last ) is a heap with respect to a comparator comp if bool(comp(first[(i - 1) / 2], first[i])) is false for all
(until C++20)
integer i in (
0, last - first ).
A random access range [ first , last ) is a heap with respect to comp and proj for a comparator comp and projection proj if
bool(std::invoke(comp, std::invoke(proj, first[(i - 1) / 2]),
std::invoke(proj, first[i])) is false for all integer i in (
0, last - first ). (since C++20)
A random access range [ first , last ) is a heap with respect to a comparator comp if the range is a heap with respect to comp and std::identity{}
(the identity projection).
[Link] 9/14
14/10/2024, 15:09 Algorithms library - [Link]
checks if the given range is a max heap
ranges::is_heap (C++20)
(niebloid)
finds the largest subrange that is a max heap
is_heap_until (C++11)
(function template)
finds the largest subrange that is a max heap
ranges::is_heap_until (C++20)
(niebloid)
Minimum/maximum operations
Permutation operations
[Link] 10/14
14/10/2024, 15:09 Algorithms library - [Link]
generates the next greater lexicographic permutation of a range of elements
next_permutation
(function template)
generates the next greater lexicographic permutation of a range of elements
ranges::next_permutation (C++20)
(niebloid)
generates the next smaller lexicographic permutation of a range of elements
prev_permutation
(function template)
generates the next smaller lexicographic permutation of a range of elements
ranges::prev_permutation (C++20)
(niebloid)
determines if a sequence is a permutation of another sequence
is_permutation (C++11)
(function template)
determines if a sequence is a permutation of another sequence
ranges::is_permutation (C++20) (niebloid)
Numeric operations
Defined in header <numeric>
fills a range with successive increments of the starting value
iota (C++11)
(function template)
fills a range with successive increments of the starting value
ranges::iota (C++23)
(niebloid)
sums up or folds a range of elements
accumulate
(function template)
computes the inner product of two ranges of elements
inner_product
(function template)
computes the differences between adjacent elements in a range
adjacent_difference
(function template)
computes the partial sum of a range of elements
partial_sum
(function template)
similar to std::accumulate, except out of order
reduce (C++17) (function template)
exclusive_scan (C++17) similar to std::partial_sum, excludes the ith input element from the ith sum
(function template)
inclusive_scan (C++17) similar to std::partial_sum, includes the ith input element in the ith sum
(function template)
applies an invocable, then reduces out of order
transform_reduce (C++17)
(function template)
applies an invocable, then calculates exclusive scan
transform_exclusive_scan (C++17)
(function template)
applies an invocable, then calculates inclusive scan
transform_inclusive_scan (C++17)
(function template)
[Link] 11/14
14/10/2024, 15:09 Algorithms library - [Link]
copies a number of objects to an uninitialized area of
uninitialized_copy_n (C++11) memory
(function template)
copies a number of objects to an uninitialized area of
ranges::uninitialized_copy_n (C++20) memory
(niebloid)
copies an object to an uninitialized area of memory,
uninitialized_fill defined by a range
(function template)
copies an object to an uninitialized area of memory,
ranges::uninitialized_fill (C++20) defined by a range
(niebloid)
copies an object to an uninitialized area of memory,
uninitialized_fill_n defined by a start and a count
(function template)
copies an object to an uninitialized area of memory,
ranges::uninitialized_fill_n (C++20) defined by a start and a count
(niebloid)
moves a range of objects to an uninitialized area of
uninitialized_move (C++17) memory
(function template)
moves a range of objects to an uninitialized area of
ranges::uninitialized_move (C++20) memory
(niebloid)
moves a number of objects to an uninitialized area of
uninitialized_move_n (C++17) memory
(function template)
moves a number of objects to an uninitialized area of
ranges::uninitialized_move_n (C++20) memory
(niebloid)
constructs objects by default-initialization in an
uninitialized_default_construct (C++17) uninitialized area of memory, defined by a range
(function template)
constructs objects by default-initialization in an
ranges::uninitialized_default_construct (C++20) uninitialized area of memory, defined by a range
(niebloid)
constructs objects by default-initialization in an
uninitialized area of memory, defined by a start and a
uninitialized_default_construct_n (C++17)
count
(function template)
constructs objects by default-initialization in an
ranges::uninitialized_default_construct_n (C++20) uninitialized area of memory, defined by a start and count
(niebloid)
constructs objects by value-initialization in an uninitialized
uninitialized_value_construct (C++17) area of memory, defined by a range
(function template)
constructs objects by value-initialization in an uninitialized
ranges::uninitialized_value_construct (C++20) area of memory, defined by a range
(niebloid)
constructs objects by value-initialization in an uninitialized
uninitialized_value_construct_n (C++17) area of memory, defined by a start and a count
(function template)
Notes
C library
Defined in header <cstdlib>
sorts a range of elements with unspecified type
qsort
(function)
searches an array for an element of unspecified type
bsearch
(function)
[Link] 13/14
14/10/2024, 15:09 Algorithms library - [Link]
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
See also
[Link] 14/14