|
|
|
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, BinaryPredicate pred);
// 28.6.10, reverse
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(ExecutionPolicy&& exec, // see 28.4.5
BidirectionalIterator first, BidirectionalIterator last);
template<class BidirectionalIterator, class OutputIterator>
constexpr OutputIterator
reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
OutputIterator result);
template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator>
ForwardIterator
reverse_copy(ExecutionPolicy&& exec, // see 28.4.5
BidirectionalIterator first, BidirectionalIterator last,
ForwardIterator result);
// 28.6.11, rotate
template<class ForwardIterator>
ForwardIterator rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator rotate(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
template<class ForwardIterator, class OutputIterator>
constexpr OutputIterator
rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
rotate_copy(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first, ForwardIterator1 middle,
ForwardIterator1 last, ForwardIterator2 result);
// 28.6.12, sample
template<class PopulationIterator, class SampleIterator,
class Distance, class UniformRandomBitGenerator>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
// 28.6.13, shuffle
template<class RandomAccessIterator, class UniformRandomBitGenerator>
void shuffle(RandomAccessIterator first,
RandomAccessIterator last,
UniformRandomBitGenerator&& g);
// 28.7.4, partitions
template<class InputIterator, class Predicate>
constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate
pred);
§
28.2
892
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool is_partitioned(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last, Predicate pred);
template<class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator partition(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first,
ForwardIterator last,
Predicate pred);
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(ExecutionPolicy&& exec, // see 28.4.5
BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
template<class InputIterator, class OutputIterator1,
class OutputIterator2, class Predicate>
constexpr pair<OutputIterator1, OutputIterator2>
partition_copy(InputIterator first, InputIterator last,
OutputIterator1 out_true, OutputIterator2 out_false,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
class ForwardIterator2, class Predicate>
pair<ForwardIterator1, ForwardIterator2>
partition_copy(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last,
ForwardIterator1 out_true, ForwardIterator2 out_false,
Predicate pred);
template<class ForwardIterator, class Predicate>
constexpr ForwardIterator
partition_point(ForwardIterator first, ForwardIterator last,
Predicate pred);
// 28.7, sorting and related operations
// 28.7.1, sorting
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
void sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
void stable_sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last);
§
28.2
893
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void stable_sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
void partial_sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void partial_sort(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
// see 28.4.5
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(ExecutionPolicy&& exec,
// see 28.4.5
ForwardIterator first, ForwardIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
template<class ForwardIterator>
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr bool is_sorted(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
bool is_sorted(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
bool is_sorted(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ForwardIterator>
constexpr ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last);
§
28.2
894
template<class ForwardIterator, class Compare>
constexpr ForwardIterator
is_sorted_until(ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
is_sorted_until(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator
is_sorted_until(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last,
Compare comp);
// 28.7.2, Nth element
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
void nth_element(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void nth_element(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator
nth,
RandomAccessIterator last, Compare comp);
// 28.7.3, binary search
template<class ForwardIterator, class T>
constexpr ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
template<class ForwardIterator, class T>
constexpr ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr ForwardIterator
upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
template<class ForwardIterator, class T>
constexpr pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
template<class ForwardIterator, class T>
constexpr bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
§ 28.2
895
template<class ForwardIterator, class T, class Compare>
constexpr bool
binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
// 28.7.5, merge
template<class InputIterator1, class InputIterator2, class OutputIterator>
constexpr OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
constexpr OutputIterator
merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
merge(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
merge(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
template<class ExecutionPolicy, class BidirectionalIterator>
void inplace_merge(ExecutionPolicy&& exec, // see 28.4.5
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
void inplace_merge(ExecutionPolicy&& exec, // see 28.4.5
BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
// 28.7.6, set operations
template<class InputIterator1, class InputIterator2>
constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
constexpr bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool includes(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
§
28.2
896
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Compare>
bool includes(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
constexpr OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator, class
Compare>
constexpr OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_union(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_union(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
constexpr OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator, class
Compare>
constexpr OutputIterator
set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_intersection(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_intersection(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
constexpr OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
§ 28.2
897
template<class InputIterator1, class InputIterator2, class OutputIterator, class
Compare>
constexpr OutputIterator
set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_difference(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_difference(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
template<class InputIterator1, class InputIterator2, class OutputIterator>
constexpr OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2, class OutputIterator, class
Compare>
constexpr OutputIterator
set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class Compare>
ForwardIterator
set_symmetric_difference(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator result, Compare comp);
// 28.7.7, heap operations
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
§
28.2
898
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
bool is_heap(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
bool is_heap(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class RandomAccessIterator>
constexpr RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
constexpr RandomAccessIterator
is_heap_until(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
template<class ExecutionPolicy, class RandomAccessIterator>
RandomAccessIterator
is_heap_until(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last);
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
RandomAccessIterator
is_heap_until(ExecutionPolicy&& exec, // see 28.4.5
RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
// 28.7.8, minimum and maximum
template<class T> constexpr const T& min(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& min(const T& a, const T& b, Compare comp);
template<class T>
constexpr T min(initializer_list<T> t);
template<class T, class Compare>
constexpr T min(initializer_list<T> t, Compare comp);
template<class T> constexpr const T& max(const T& a, const T& b);
template<class T, class Compare>
constexpr const T& max(const T& a, const T& b, Compare comp);
template<class T>
constexpr T max(initializer_list<T> t);
template<class T, class Compare>
constexpr T max(initializer_list<T> t, Compare comp);
template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const
T&
b);
template<class T, class Compare>
constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
template<class T>
constexpr pair<T, T> minmax(initializer_list<T> t);
template<class T, class Compare>
constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
template<class ForwardIterator>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
§ 28.2
899
template<class ForwardIterator, class Compare>
constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator
last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator min_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator min_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ForwardIterator>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator
last);
template<class ForwardIterator, class Compare>
constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator
last,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator max_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
ForwardIterator max_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last,
Compare comp);
template<class ForwardIterator>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
constexpr pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
template<class ExecutionPolicy, class ForwardIterator>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class Compare>
pair<ForwardIterator, ForwardIterator>
minmax_element(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator first, ForwardIterator last, Compare comp);
// 28.7.9, bounded value
template<class T>
constexpr const T& clamp(const T& v, const T& lo, const T& hi);
template<class T, class Compare>
constexpr const T& clamp(const T& v, const T& lo, const T& hi, Compare comp);
// 28.7.10, lexicographical comparison
template<class InputIterator1, class InputIterator2>
constexpr bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class Compare>
constexpr bool
lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool
lexicographical_compare(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Compare>
bool
lexicographical_compare(ExecutionPolicy&& exec, // see 28.4.5
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
§
28.2
900
Compare comp);
// 28.7.11, three-way comparison algorithms
template<class T, class U>
constexpr auto compare_3way(const T& a, const U& b);
template<class InputIterator1, class InputIterator2, class Cmp>
constexpr auto
lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
InputIterator2 b2, InputIterator2 e2,
Cmp comp)
-> common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>;
template<class InputIterator1, class InputIterator2>
constexpr auto
lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
InputIterator2 b2, InputIterator2 e2);
// 28.7.12, permutations
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
}
28.3
Algorithms requirements
[algorithms.requirements]
1
All of the algorithms are separated from the particular implementations of data structures and are parame-
terized by iterator types. Because of this, they can work with program-defined data structures, as long as
these data structures have iterator types satisfying the assumptions on the algorithms.
2
For purposes of determining the existence of data races, algorithms shall not modify objects referenced
through an iterator argument unless the specification requires such modification.
3
Throughout this Clause, the names of template parameters are used to express type requirements.
(3.1)
—
If an algorithm’s template parameter is named InputIterator, InputIterator1, or InputIterator2,
the template argument shall satisfy the requirements of an input iterator (27.2.3).
(3.2)
—
If an algorithm’s template parameter is named OutputIterator, OutputIterator1, or Output-
Iterator2, the template argument shall satisfy the requirements of an output iterator (27.2.4).
(3.3)
—
If an algorithm’s template parameter is named ForwardIterator, ForwardIterator1, or Forward-
Iterator2, the template argument shall satisfy the requirements of a forward iterator (27.2.5).
(3.4)
—
If an algorithm’s template parameter is named BidirectionalIterator, BidirectionalIterator1,
or BidirectionalIterator2, the template argument shall satisfy the requirements of a bidirectional
iterator (27.2.6).
(3.5)
—
If an algorithm’s template parameter is named RandomAccessIterator, RandomAccessIterator1, or
RandomAccessIterator2, the template argument shall satisfy the requirements of a random-access
iterator (27.2.7).
4
If an algorithm’s Effects: element specifies that a value pointed to by any iterator passed as an argument is
modified, then that algorithm has an additional type requirement: The type of that argument shall satisfy
the requirements of a mutable iterator (27.2). [Note: This requirement does not affect arguments that are
named OutputIterator, OutputIterator1, or OutputIterator2, because output iterators must always be
mutable.
— end note ]
§ 28.3
901
5
Both in-place and copying versions are provided for certain algorithms.265 When such a version is provided
for algorithm it is called algorithm_copy. Algorithms that take predicates end with the suffix _if (which
follows the suffix _copy).
6
The Predicate parameter is used whenever an algorithm expects a function object (23.14) that, when applied
to the result of dereferencing the corresponding iterator, returns a value testable as true. In other words,
if an algorithm takes Predicate pred as its argument and first as its iterator argument, it should work
correctly in the construct pred(*first) contextually converted to bool (Clause 7). The function object
pred shall not apply any non-constant function through the dereferenced iterator.
7
The BinaryPredicate parameter is used whenever an algorithm expects a function object that when
applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type
T when T is part of the signature returns a value testable as true. In other words, if an algorithm takes
BinaryPredicate binary_pred as its argument and first1 and first2 as its iterator arguments, it should
work correctly in the construct binary_pred(*first1, *first2) contextually converted to bool (Clause
7). BinaryPredicate always takes the first iterator’s value_type as its first argument, that is, in those
cases when T value is part of the signature, it should work correctly in the construct binary_pred(*first1,
value) contextually converted to bool (Clause 7). binary_pred shall not apply any non-constant function
through the dereferenced iterators.
8
[ Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy
those function objects freely. Programmers for whom object identity is important should consider using a
wrapper class that points to a noncopied implementation object such as reference_wrapper<T> (23.14.5),
or some equivalent solution.
— end note ]
9
When the description of an algorithm gives an expression such as *first == value for a condition, the
expression shall evaluate to either true or false in boolean contexts.
10
In the description of the algorithms operators + and - are used for some of the iterator categories for which
they do not have to be defined. In these cases the semantics of a+n is the same as that of
X tmp = a;
advance(tmp, n);
return tmp;
and that of b-a is the same as of
return distance(a, b);
28.4
Parallel algorithms
[algorithms.parallel]
1
This subclause describes components that C++ programs may use to perform operations on containers and
other sequences in parallel.
28.4.1
Terms and definitions
[algorithms.parallel.defns]
1
A parallel algorithm is a function template listed in this document with a template parameter named
ExecutionPolicy.
2
Parallel algorithms access objects indirectly accessible via their arguments by invoking the following functions:
(2.1)
—
All operations of the categories of the iterators that the algorithm is instantiated with.
(2.2)
—
Operations on those sequence elements that are required by its specification.
(2.3)
—
User-provided function objects to be applied during the execution of the algorithm, if required by the
specification.
(2.4)
—
Operations on those function objects required by the specification. [ Note: See 28.1. — end note ]
These functions are herein called element access functions. [Example: The sort function may invoke the
following element access functions:
(2.5)
—
Operations of the random-access iterator of the actual template argument (as per 27.2.7), as implied by
the name of the template parameter RandomAccessIterator.
(2.6)
—
The swap function on the elements of the sequence (as per the preconditions specified in 28.7.1.1).
265) The decision whether to include a copying version was usually based on complexity considerations. When the cost of doing
the operation dominates the cost of copy, the copying version is not included. For example, sort_copy is not included because
the cost of sorting is much more significant, and users might as well do copy followed by sort.
§ 28.4.1
902
(2.7)
—
The user-provided Compare function object.
— end example ]
28.4.2
Requirements on user-provided function objects
[algorithms.parallel.user]
1
Unless otherwise specified, function objects passed into parallel algorithms as objects of type Predicate,
BinaryPredicate, Compare, UnaryOperation, BinaryOperation, BinaryOperation1, BinaryOperation2,
and the operators used by the analogous overloads to these parallel algorithms that could be formed by the
invocation with the specified default predicate or operation (where applicable) shall not directly or indirectly
modify objects via their arguments, nor shall they rely on the identity of the provided objects.
28.4.3
Effect of execution policies on algorithm execution
[algorithms.parallel.exec]
1
Parallel algorithms have template parameters named ExecutionPolicy (23.19) which describe the manner in
which the execution of these algorithms may be parallelized and the manner in which they apply the element
access functions.
2
If an object is modified by an element access function, the algorithm will perform no other unsynchronized
accesses to that object. The modifying element access functions are those which are specified as modifying
the object in the relevant concept. [Note: For example, swap(), ++, --, @=, and assignments modify the
object. For the assignment and @= operators, only the left argument is modified.
— end note ]
3
Unless otherwise stated, implementations may make arbitrary copies of elements (with type T) from sequences
where is_trivially_copy_constructible_v<T> and is_trivially_destructible_v<T> are true. [ Note:
This implies that user-supplied function objects should not rely on object identity of arguments for such input
sequences. Users for whom the object identity of the arguments to these function objects is important should
consider using a wrapping iterator that returns a non-copied implementation object such as reference_-
wrapper<T> (23.14.5) or some equivalent solution.
— end note ]
4
The invocations of element access functions in parallel algorithms invoked with an execution policy object of
type execution::sequenced_policy all occur in the calling thread of execution. [ Note: The invocations
are not interleaved; see 6.8.1.
— end note ]
5
The invocations of element access functions in parallel algorithms invoked with an execution policy object
of type execution::parallel_policy are permitted to execute in either the invoking thread of execution
or in a thread of execution implicitly created by the library to support parallel algorithm execution. If the
threads of execution created by thread (33.3.2) provide concurrent forward progress guarantees (6.8.2.2),
then a thread of execution implicitly created by the library will provide parallel forward progress guarantees;
otherwise, the provided forward progress guarantee is implementation-defined. Any such invocations executing
in the same thread of execution are indeterminately sequenced with respect to each other. [ Note: It is the
caller’s responsibility to ensure that the invocation does not introduce data races or deadlocks.
— end note ]
[ Example:
int a[] = {0,1};
std::vector<int> v;
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int i) {
v.push_back(i*2+1); // incorrect: data race
});
The program above has a data race because of the unsynchronized access to the container v.
— end example ]
[ Example:
std::atomic<int> x{0};
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
x.fetch_add(1, std::memory_order::relaxed);
// spin wait for another iteration to change the value of x
while (x.load(std::memory_order::relaxed) == 1) { } // incorrect: assumes execution order
});
The above example depends on the order of execution of the iterations, and will not terminate if both
iterations are executed sequentially on the same thread of execution.
— end example ] [ Example:
int x = 0;
std::mutex m;
int a[] = {1,2};
§ 28.4.3
903
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m);
++x;
});
The above example synchronizes access to object x ensuring that it is incremented correctly.
— end example ]
6
The invocations of element access functions in parallel algorithms invoked with an execution policy of type
execution::parallel_unsequenced_policy are permitted to execute in an unordered fashion in unspecified
threads of execution, and unsequenced with respect to one another within each thread of execution. These
threads of execution are either the invoking thread of execution or threads of execution implicitly created
by the library; the latter will provide weakly parallel forward progress guarantees. [ Note: This means that
multiple function object invocations may be interleaved on a single thread of execution, which overrides
the usual guarantee from 6.8.1 that function executions do not interleave with one another.
— end note ]
Since execution::parallel_unsequenced_policy allows the execution of element access functions to be
interleaved on a single thread of execution, blocking synchronization, including the use of mutexes, risks
deadlock. Thus, the synchronization with execution::parallel_unsequenced_policy is restricted as
follows: A standard library function is vectorization-unsafe if it is specified to synchronize with another
function invocation, or another function invocation is specified to synchronize with it, and if it is not a memory
allocation or deallocation function. Vectorization-unsafe standard library functions may not be invoked by
user code called from execution::parallel_unsequenced_policy algorithms.
[Note: Implementations
must ensure that internal synchronization inside standard library functions does not prevent forward progress
when those functions are executed by threads of execution with weakly parallel forward progress guarantees.
— end note ] [ Example:
int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par_unseq, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m); // incorrect: lock_guard constructor calls m.lock()
++x;
});
The above program may result in two consecutive calls to m.lock() on the same thread of execution (which
may deadlock), because the applications of the function object are not guaranteed to run on different
threads of execution.
— end example ] [Note: The semantics of the execution::parallel_policy or the
execution::parallel_unsequenced_policy invocation allow the implementation to fall back to sequential
execution if the system cannot parallelize an algorithm invocation due to lack of resources.
— end note ]
7
If an invocation of a parallel algorithm uses threads of execution implicitly created by the library, then the
invoking thread of execution will either
(7.1)
—
temporarily block with forward progress guarantee delegation (6.8.2.2) on the completion of these
library-managed threads of execution, or
(7.2)
—
eventually execute an element access function;
the thread of execution will continue to do so until the algorithm is finished. [ Note: In blocking with forward
progress guarantee delegation in this context, a thread of execution created by the library is considered to
have finished execution as soon as it has finished the execution of the particular element access function that
the invoking thread of execution logically depends on.
— end note ]
8
The semantics of parallel algorithms invoked with an execution policy object of implementation-defined type
are implementation-defined.
28.4.4
Parallel algorithm exceptions
[algorithms.parallel.exceptions]
1
During the execution of a parallel algorithm, if temporary memory resources are required for parallelization
and none are available, the algorithm throws a bad_alloc exception.
2
During the execution of a parallel algorithm, if the invocation of an element access function exits via an
uncaught exception, the behavior is determined by the ExecutionPolicy.
28.4.5
ExecutionPolicy algorithm overloads
[algorithms.parallel.overloads]
1
Parallel algorithms are algorithm overloads. Each parallel algorithm overload has an additional template
type parameter named ExecutionPolicy, which is the first template parameter. Additionally, each parallel
§ 28.4.5
904
algorithm overload has an additional function parameter of type ExecutionPolicy&&, which is the first
function parameter. [ Note: Not all algorithms have parallel algorithm overloads. — end note ]
2
Unless otherwise specified, the semantics of ExecutionPolicy algorithm overloads are identical to their
overloads without.
3
Unless otherwise specified, the complexity requirements of ExecutionPolicy algorithm overloads are relaxed
from the complexity requirements of the overloads without as follows: when the guarantee says “at most
expr” or “exactly expr” and does not specify the number of assignments or swaps, and expr is not already
expressed with O() notation, the complexity of the algorithm shall be O(expr).
4
Parallel algorithms shall not participate in overload resolution unless is_execution_policy_v<decay_-
t<ExecutionPolicy>> is true.
28.5
Non-modifying sequence operations
[alg.nonmodifying]
28.5.1
All of
[alg.all_of]
template<class InputIterator, class Predicate>
constexpr bool all_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool all_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Predicate pred);
1
Returns: true if [first, last) is empty or if pred(*i) is true for every iterator i in the range
[first, last), and false otherwise.
2
Complexity: At most last - first applications of the predicate.
28.5.2
Any of
[alg.any_of]
template<class InputIterator, class Predicate>
constexpr bool any_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Predicate pred);
1
Returns: false if [first, last) is empty or if there is no iterator i in the range [first, last)
such that pred(*i) is true, and true otherwise.
2
Complexity: At most last - first applications of the predicate.
28.5.3
None of
[alg.none_of]
template<class InputIterator, class Predicate>
constexpr bool none_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool none_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Predicate pred);
1
Returns: true if [first, last) is empty or if pred(*i) is false for every iterator i in the range
[first, last), and false otherwise.
2
Complexity: At most last - first applications of the predicate.
28.5.4
For each
[alg.foreach]
template<class InputIterator, class Function>
constexpr Function for_each(InputIterator first, InputIterator last, Function f);
1
Requires: Function shall meet the requirements of MoveConstructible (Table 23). [ Note: Function
need not meet the requirements of CopyConstructible (Table 24).
— end note ]
2
Effects: Applies f to the result of dereferencing every iterator in the range [first, last), starting
from first and proceeding to last - 1. [Note: If the type of first satisfies the requirements of a
mutable iterator, f may apply non-constant functions through the dereferenced iterator. — end note ]
3
Returns: f.
4
Complexity: Applies f exactly last - first times.
5
Remarks: If f returns a result, the result is ignored.
§ 28.5.4
905
template<class ExecutionPolicy, class ForwardIterator, class Function>
void for_each(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Function f);
6
Requires: Function shall meet the requirements of CopyConstructible.
7
Effects: Applies f to the result of dereferencing every iterator in the range [first, last). [ Note: If
the type of first satisfies the requirements of a mutable iterator, f may apply non-constant functions
through the dereferenced iterator.
— end note ]
8
Complexity: Applies f exactly last - first times.
9
Remarks: If f returns a result, the result is ignored. Implementations do not have the freedom granted
under 28.4.3 to make arbitrary copies of elements from the input sequence.
10
[ Note: Does not return a copy of its Function parameter, since parallelization may not permit efficient
state accumulation.
— end note ]
template<class InputIterator, class Size, class Function>
constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
11
Requires: Function shall meet the requirements of MoveConstructible [ Note: Function need not
meet the requirements of CopyConstructible. — end note ]
12
Requires: n >= 0.
13
Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n) in
order.
[Note: If the type of first satisfies the requirements of a mutable iterator, f may apply
non-constant functions through the dereferenced iterator.
— end note ]
14
Returns: first + n.
15
Remarks: If f returns a result, the result is ignored.
template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
ForwardIterator for_each_n(ExecutionPolicy&& exec, ForwardIterator first, Size n,
Function f);
16
Requires: Function shall meet the requirements of CopyConstructible.
17
Requires: n >= 0.
18
Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n).
[ Note: If the type of first satisfies the requirements of a mutable iterator, f may apply non-constant
functions through the dereferenced iterator.
— end note ]
19
Returns: first + n.
20
Remarks: If f returns a result, the result is ignored. Implementations do not have the freedom granted
under 28.4.3 to make arbitrary copies of elements from the input sequence.
28.5.5
Find
[alg.find]
template<class InputIterator, class T>
constexpr InputIterator find(InputIterator first, InputIterator last,
const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
ForwardIterator find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
const T& value);
template<class InputIterator, class Predicate>
constexpr InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator find_if(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class InputIterator, class Predicate>
constexpr InputIterator find_if_not(InputIterator first, InputIterator last,
Predicate pred);
§ 28.5.5
906
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator find_if_not(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
Predicate pred);
1
Returns: The first iterator i in the range [first, last) for which the following corresponding
conditions hold: *i == value, pred(*i) != false, pred(*i) == false. Returns last if no such
iterator is found.
2
Complexity: At most last - first applications of the corresponding predicate.
28.5.6
Find end
[alg.find.end]
template<class ForwardIterator1, class ForwardIterator2>
constexpr ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
constexpr ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_end(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Effects: Finds a subsequence of equal values in a sequence.
2
Returns: The last iterator i in the range [first1, last1 - (last2 - first2)) such that for every
non-negative integer n < (last2 - first2), the following corresponding conditions hold:
*(i +
n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns last1 if [first2,
last2) is empty or if no such iterator is found.
3
Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applica-
tions of the corresponding predicate.
28.5.7
Find first
[alg.find.first.of]
template<class InputIterator, class ForwardIterator>
constexpr InputIterator
find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator, class ForwardIterator,
class BinaryPredicate>
constexpr InputIterator
find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);
§ 28.5.7
907
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_first_of(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Effects: Finds an element that matches one of a set of values.
2
Returns: The first iterator i in the range [first1, last1) such that for some iterator j in the range
[first2, last2) the following conditions hold: *i == *j, pred(*i,*j) != false. Returns last1
if
[first2, last2) is empty or if no such iterator is found.
3
Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate.
28.5.8
Adjacent find
[alg.adjacent.find]
template<class ForwardIterator>
constexpr ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
adjacent_find(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
constexpr ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_find(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
1
Returns: The first iterator i such that both i and i + 1 are in the range [first, last) for which the
following corresponding conditions hold: *i == *(i + 1), pred(*i, *(i + 1)) != false. Returns
last if no such iterator is found.
2
Complexity: For the overloads with no ExecutionPolicy, exactly min((i - first) + 1, (last -
first) - 1) applications of the corresponding predicate, where i is adjacent_find’s return value.
For the overloads with an ExecutionPolicy, O(last - first) applications of the corresponding
predicate.
28.5.9
Count
[alg.count]
template<class InputIterator, class T>
constexpr typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
typename iterator_traits<ForwardIterator>::difference_type
count(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, const T& value);
template<class InputIterator, class Predicate>
constexpr typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
typename iterator_traits<ForwardIterator>::difference_type
count_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, Predicate pred);
1
Effects: Returns the number of iterators i in the range [first, last) for which the following
corresponding conditions hold: *i == value, pred(*i) != false.
2
Complexity: Exactly last - first applications of the corresponding predicate.
§ 28.5.9
908
28.5.10
Mismatch
[mismatch]
template<class InputIterator1, class InputIterator2>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class
ForwardIterator2>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class
ForwardIterator2,
class BinaryPredicate>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class InputIterator1, class InputIterator2>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class
ForwardIterator2>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1
-
first1) below.
2
Returns: A pair of iterators first1 + n and first2 + n, where n is the smallest integer such that,
respectively,
(2.1)
—
!(*(first1 + n) == *(first2 + n)) or
(2.2)
—
pred(*(first1 + n), *(first2 + n)) == false,
or min(last1 - first1, last2 - first2) if no such integer exists.
3
Complexity: At most min(last1 - first1, last2 - first2) applications of the corresponding
predicate.
28.5.11
Equal
[alg.equal]
template<class InputIterator1, class InputIterator2>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
§ 28.5.11
909
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool equal(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class InputIterator1, class InputIterator2>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool equal(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1
-
first1) below.
2
Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if for every
iterator i in the range [first1, last1) the following corresponding conditions hold: *i == *(first2
+ (i - first1)), pred(*i, *(first2 + (i - first1))) != false. Otherwise, returns false.
3
Complexity:
(3.1)
—
For the overloads with no ExecutionPolicy,
(3.1.1)
—
if InputIterator1 and InputIterator2 meet the requirements of random access iterators
(27.2.7) and last1 - first1 != last2 - first2, then no applications of the corresponding
predicate; otherwise,
(3.1.2)
—
at most min(last1 - first1, last2 - first2) applications of the corresponding predicate.
(3.2)
—
For the overloads with an ExecutionPolicy,
(3.2.1)
—
if ForwardIterator1 and ForwardIterator2 meet the requirements of random access iter-
ators and last1 - first1 != last2 - first2, then no applications of the corresponding
predicate; otherwise,
(3.2.2)
—
O(min(last1 - first1, last2 - first2)) applications of the corresponding predicate.
28.5.12
Is permutation
[alg.is_permutation]
template<class ForwardIterator1, class ForwardIterator2>
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
§ 28.5.12
910
template<class ForwardIterator1, class ForwardIterator2>
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Requires: ForwardIterator1 and ForwardIterator2 shall have the same value type. The comparison
function shall be an equivalence relation.
2
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.
3
Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if there exists
a permutation of the elements in the range [first2, first2 + (last1 - first1)), beginning with
ForwardIterator2 begin, such that equal(first1, last1, begin) returns true or equal(first1,
last1, begin, pred) returns true; otherwise, returns false.
4
Complexity: No applications of the corresponding predicate if ForwardIterator1 and ForwardIter-
ator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2.
Otherwise, exactly last1 - first1 applications of the corresponding predicate if equal(first1,
last1, first2, last2) would return true if pred was not given in the argument list or equal(first1,
last1, first2, last2, pred) would return true if pred was given in the argument list; otherwise,
at worst O(N2), where N has the value last1 - first1.
28.5.13
Search
[alg.search]
template<class ForwardIterator1, class ForwardIterator2>
constexpr ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
search(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
constexpr ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
search(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
1
Effects: Finds a subsequence of equal values in a sequence.
2
Returns: The first iterator i in the range [first1, last1 - (last2-first2)) such that for every non-
negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) ==
*(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns first1 if [first2, last2)
is empty, otherwise returns last1 if no such iterator is found.
3
Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding
predicate.
template<class ForwardIterator, class Size, class T>
constexpr ForwardIterator
search_n(ForwardIterator first, ForwardIterator last,
Size count, const T& value);
§ 28.5.13
911
template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
ForwardIterator
search_n(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Size count, const T& value);
template<class ForwardIterator, class Size, class T,
class BinaryPredicate>
constexpr ForwardIterator
search_n(ForwardIterator first, ForwardIterator last,
Size count, const T& value,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
class BinaryPredicate>
ForwardIterator
search_n(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Size count, const T& value,
BinaryPredicate pred);
4
Requires: The type Size shall be convertible to integral type (7.8, 15.3).
5
Effects: Finds a subsequence of equal values in a sequence.
6
Returns: The first iterator i in the range [first, last-count) such that for every non-negative
integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i
+ n),value) != false. Returns last if no such iterator is found.
7
Complexity: At most last - first applications of the corresponding predicate.
template<class ForwardIterator, class Searcher>
constexpr ForwardIterator
search(ForwardIterator first, ForwardIterator last, const Searcher& searcher);
8
Effects: Equivalent to: return searcher(first, last).first;
9
Remarks: Searcher need not meet the CopyConstructible requirements.
28.6
Mutating sequence operations
[alg.modifying.operations]
28.6.1
Copy
[alg.copy]
template<class InputIterator, class OutputIterator>
constexpr OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
1
Requires: result shall not be in the range [first, last).
2
Effects: Copies elements in the range [first, last) into the range [result, result + (last -
first)) starting from first and proceeding to last. For each non-negative integer n < (last -
first), performs *(result + n) = *(first + n).
3
Returns: result + (last - first).
4
Complexity: Exactly last - first assignments.
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(ExecutionPolicy&& policy,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
5
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
6
Effects: Copies elements in the range [first, last) into the range [result, result + (last -
first)). For each non-negative integer n < (last - first), performs *(result + n) = *(first
+ n).
7
Returns: result + (last - first).
8
Complexity: Exactly last - first assignments.
§ 28.6.1
912
template<class InputIterator, class Size, class OutputIterator>
constexpr OutputIterator copy_n(InputIterator first, Size n,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
ForwardIterator2 copy_n(ExecutionPolicy&& exec,
ForwardIterator1 first, Size n,
ForwardIterator2 result);
9
Effects: For each non-negative integer i < n, performs *(result + i) = *(first + i).
10
Returns: result + n.
11
Complexity: Exactly n assignments.
template<class InputIterator, class OutputIterator, class Predicate>
constexpr OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Predicate>
ForwardIterator2 copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, Predicate pred);
12
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
[Note: For the overload with an ExecutionPolicy, there may be a performance cost if iterator_-
traits<ForwardIterator1>::value_type is not MoveConstructible (Table 23). — end note ]
13
Effects: Copies all of the elements referred to by the iterator i in the range [first, last) for which
pred(*i) is true.
14
Returns: The end of the resulting range.
15
Complexity: Exactly last - first applications of the corresponding predicate.
16
Remarks: Stable (20.5.5.7).
template<class BidirectionalIterator1, class BidirectionalIterator2>
constexpr BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
17
Requires: result shall not be in the range (first, last].
18
Effects: Copies elements in the range [first, last) into the range [result - (last-first),
result) starting from last - 1 and proceeding to first.266 For each positive integer n <= (last -
first), performs *(result - n) = *(last - n).
19
Returns: result - (last - first).
20
Complexity: Exactly last - first assignments.
28.6.2
Move
[alg.move]
template<class InputIterator, class OutputIterator>
constexpr OutputIterator move(InputIterator first, InputIterator last,
OutputIterator result);
1
Requires: result shall not be in the range [first, last).
2
Effects: Moves elements in the range [first, last) into the range [result, result + (last -
first)) starting from first and proceeding to last. For each non-negative integer n < (last-first),
performs *(result + n) = std::move(*(first + n)).
3
Returns: result + (last - first).
4
Complexity: Exactly last - first move assignments.
266) copy_backward should be used instead of copy when last is in the range [result - (last - first), result).
§ 28.6.2
913
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 move(ExecutionPolicy&& policy,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
5
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
6
Effects: Moves elements in the range [first, last) into the range [result, result + (last -
first)). For each non-negative integer n < (last - first), performs *(result + n) = std::
move(*(first + n)).
7
Returns: result + (last - first).
8
Complexity: Exactly last - first assignments.
template<class BidirectionalIterator1, class BidirectionalIterator2>
constexpr BidirectionalIterator2
move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
BidirectionalIterator2 result);
9
Requires: result shall not be in the range (first, last].
10
Effects: Moves elements in the range [first, last) into the range [result - (last-first),
result) starting from last - 1 and proceeding to first.267 For each positive integer n <= (last -
first), performs *(result - n) = std::move(*(last - n)).
11
Returns: result - (last - first).
12
Complexity: Exactly last - first assignments.
28.6.3
Swap
[alg.swap]
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
1
Requires: The two ranges [first1, last1) and [first2, first2 + (last1 - first1)) shall not
overlap. *(first1 + n) shall be swappable with (20.5.3.2) *(first2 + n).
2
Effects: For each non-negative integer n < (last1 - first1) performs: swap(*(first1 + n),
*(first2 + n)).
3
Returns: first2 + (last1 - first1).
4
Complexity: Exactly last1 - first1 swaps.
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
5
Requires: a and b shall be dereferenceable. *a shall be swappable with (20.5.3.2) *b.
6
Effects: As if by swap(*a, *b).
28.6.4
Transform
[alg.transform]
template<class InputIterator, class OutputIterator,
class UnaryOperation>
constexpr OutputIterator
transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);
267) move_backward should be used instead of move when last is in the range [result - (last - first), result).
§ 28.6.4
914
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class UnaryOperation>
ForwardIterator2
transform(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, UnaryOperation op);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
constexpr OutputIterator
transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class ForwardIterator, class BinaryOperation>
ForwardIterator
transform(ExecutionPolicy&& exec,
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator result,
BinaryOperation binary_op);
1
Requires: op and binary_op shall not invalidate iterators or subranges, or modify elements in the
ranges
(1.1)
—
[first1, last1],
(1.2)
—
[first2, first2 + (last1 - first1)], and
(1.3)
—
[result, result + (last1 - first1)].268
2
Effects: Assigns through every iterator i in the range [result, result + (last1 - first1)) a
new corresponding value equal to op(*(first1 + (i - result))) or binary_op(*(first1 + (i -
result)), *(first2 + (i - result))).
3
Returns: result + (last1 - first1).
4
Complexity: Exactly last1 - first1 applications of op or binary_op. This requirement also applies
to the overload with an ExecutionPolicy .
5
Remarks: result may be equal to first in case of unary transform, or to first1 or first2 in case of
binary transform.
28.6.5
Replace
[alg.replace]
template<class ForwardIterator, class T>
constexpr void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator, class T>
void replace(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
template<class ForwardIterator, class Predicate, class T>
constexpr void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator, class Predicate, class T>
void replace_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
1
Requires: The expression *first = new_value shall be valid.
2
Effects: Substitutes elements referred by the iterator i in the range [first, last) with new_value,
when the following corresponding conditions hold: *i == old_value, pred(*i) != false.
3
Complexity: Exactly last - first applications of the corresponding predicate.
268) The use of fully closed ranges is intentional.
§ 28.6.5
915
template<class InputIterator, class OutputIterator, class T>
constexpr OutputIterator
replace_copy(InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
ForwardIterator2
replace_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result,
const T& old_value, const T& new_value);
template<class InputIterator, class OutputIterator, class Predicate, class T>
constexpr OutputIterator
replace_copy_if(InputIterator first, InputIterator last,
OutputIterator result,
Predicate pred, const T& new_value);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Predicate, class T>
ForwardIterator2
replace_copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result,
Predicate pred, const T& new_value);
4
Requires: The results of the expressions *first and new_value shall be writable (27.2.1) to the result
output iterator. The ranges [first, last) and [result, result + (last - first)) shall not
overlap.
5
Effects: Assigns to every iterator i in the range [result, result + (last - first)) either new_-
value or *(first + (i - result)) depending on whether the following corresponding conditions
hold:
*(first + (i - result)) == old_value
pred(*(first + (i - result))) != false
6
Returns: result + (last - first).
7
Complexity: Exactly last - first applications of the corresponding predicate.
28.6.6
Fill
[alg.fill]
template<class ForwardIterator, class T>
constexpr void fill(ForwardIterator first, ForwardIterator last, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
void fill(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last, const T& value);
template<class OutputIterator, class Size, class T>
constexpr OutputIterator fill_n(OutputIterator first, Size n, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
ForwardIterator fill_n(ExecutionPolicy&& exec,
ForwardIterator first, Size n, const T& value);
1
Requires: The expression value shall be writable (27.2.1) to the output iterator. The type Size shall
be convertible to an integral type (7.8, 15.3).
2
Effects: The fill algorithms assign value through all the iterators in the range [first, last). The
fill_n algorithms assign value through all the iterators in the range [first, first + n) if n is
positive, otherwise they do nothing.
3
Returns: fill_n returns first + n for non-negative values of n and first for negative values.
4
Complexity: Exactly last - first, n, or 0 assignments, respectively.
28.6.7
Generate
[alg.generate]
template<class ForwardIterator, class Generator>
constexpr void generate(ForwardIterator first, ForwardIterator last,
§ 28.6.7
916
Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Generator>
void generate(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Generator gen);
template<class OutputIterator, class Size, class Generator>
constexpr OutputIterator generate_n(OutputIterator first, Size n, Generator gen);
template<class ExecutionPolicy, class ForwardIterator, class Size, class Generator>
ForwardIterator generate_n(ExecutionPolicy&& exec,
ForwardIterator first, Size n, Generator gen);
1
Requires: gen takes no arguments, Size shall be convertible to an integral type (7.8, 15.3).
2
Effects: The generate algorithms invoke the function object gen and assign the return value of gen
through all the iterators in the range [first, last). The generate_n algorithms invoke the function
object gen and assign the return value of gen through all the iterators in the range [first, first +
n) if n is positive, otherwise they do nothing.
3
Returns: generate_n returns first + n for non-negative values of n and first for negative values.
4
Complexity: Exactly last - first, n, or 0 invocations of gen and assignments, respectively.
28.6.8
Remove
[alg.remove]
template<class ForwardIterator, class T>
constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
ForwardIterator remove(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class Predicate>
constexpr ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator remove_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Predicate pred);
1
Requires: The type of *first shall satisfy the MoveAssignable requirements (Table 25).
2
Effects: Eliminates all the elements referred to by iterator i in the range [first, last) for which the
following corresponding conditions hold: *i == value, pred(*i) != false.
3
Returns: The end of the resulting range.
4
Remarks: Stable (20.5.5.7).
5
Complexity: Exactly last - first applications of the corresponding predicate.
6
[Note: Each element in the range [ret, last), where ret is the returned value, has a valid but
unspecified state, because the algorithms can eliminate elements by moving from elements that were
originally in that range.
— end note ]
template<class InputIterator, class OutputIterator, class T>
constexpr OutputIterator
remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class T>
ForwardIterator2
remove_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, const T& value);
§ 28.6.8
917
template<class InputIterator, class OutputIterator, class Predicate>
constexpr OutputIterator
remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Predicate>
ForwardIterator2
remove_copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, Predicate pred);
7
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
The expression *result = *first shall be valid. [ Note: For the overloads with an ExecutionPolicy,
there may be a performance cost if iterator_traits<ForwardIterator1>::value_type is not Move-
Constructible (Table 23). — end note ]
8
Effects: Copies all the elements referred to by the iterator i in the range [first, last) for which the
following corresponding conditions do not hold: *i == value, pred(*i) != false.
9
Returns: The end of the resulting range.
10
Complexity: Exactly last - first applications of the corresponding predicate.
11
Remarks: Stable (20.5.5.7).
28.6.9
Unique
[alg.unique]
template<class ForwardIterator>
constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator unique(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
1
Requires: The comparison function shall be an equivalence relation. The type of *first shall satisfy
the MoveAssignable requirements (Table 25).
2
Effects: For a nonempty range, eliminates all but the first element from every consecutive group
of equivalent elements referred to by the iterator i in the range [first + 1, last) for which the
following conditions hold: *(i - 1) == *i or pred(*(i - 1), *i) != false.
3
Returns: The end of the resulting range.
4
Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding
predicate.
template<class InputIterator, class OutputIterator>
constexpr OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result);
template<class InputIterator, class OutputIterator,
class BinaryPredicate>
constexpr OutputIterator
unique_copy(InputIterator first, InputIterator last,
OutputIterator result, BinaryPredicate pred);
§ 28.6.9
918
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator2
unique_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, BinaryPredicate pred);
5
Requires:
(5.1)
—
The comparison function shall be an equivalence relation.
(5.2)
—
The ranges [first, last) and [result, result+(last-first)) shall not overlap.
(5.3)
—
The expression *result = *first shall be valid.
(5.4)
—
For the overloads with no ExecutionPolicy, let T be the value type of InputIterator. If
InputIterator meets the forward iterator requirements, then there are no additional requirements
for T. Otherwise, if OutputIterator meets the forward iterator requirements and its value
type is the same as T, then T shall be CopyAssignable (Table 26). Otherwise, T shall be
both CopyConstructible (Table 24) and CopyAssignable. [ Note: For the overloads with an
ExecutionPolicy, there may be a performance cost if the value type of ForwardIterator1 is
not both CopyConstructible and CopyAssignable. — end note ]
6
Effects: Copies only the first element from every consecutive group of equal elements referred to by the
iterator i in the range [first, last) for which the following corresponding conditions hold: *i ==
*(i - 1) or pred(*i, *(i - 1)) != false.
7
Returns: The end of the resulting range.
8
Complexity: For nonempty ranges, exactly last - first - 1 applications of the corresponding
predicate.
28.6.10
Reverse
[alg.reverse]
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
template<class ExecutionPolicy, class BidirectionalIterator>
void reverse(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last);
1
Requires: BidirectionalIterator shall satisfy the requirements of ValueSwappable (20.5.3.2).
2
Effects: For each non-negative integer i < (last - first) / 2, applies iter_swap to all pairs of
iterators first + i, (last - i) - 1.
3
Complexity: Exactly (last - first)/2 swaps.
template<class BidirectionalIterator, class OutputIterator>
constexpr OutputIterator
reverse_copy(BidirectionalIterator first, BidirectionalIterator last,
OutputIterator result);
template<class ExecutionPolicy, class BidirectionalIterator, class ForwardIterator>
ForwardIterator
reverse_copy(ExecutionPolicy&& exec,
BidirectionalIterator first, BidirectionalIterator last,
ForwardIterator result);
4
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
5
Effects: Copies the range [first, last) to the range [result, result + (last - first)) such
that for every non-negative integer i < (last - first) the following assignment takes place: *(result
+ (last - first) - 1 - i) = *(first + i).
6
Returns: result + (last - first).
7
Complexity: Exactly last - first assignments.
28.6.11
Rotate
[alg.rotate]
template<class ForwardIterator>
ForwardIterator
§ 28.6.11
919
rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
rotate(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator middle, ForwardIterator last);
1
Requires: [first, middle) and [middle, last) shall be valid ranges. ForwardIterator shall satisfy
the requirements of ValueSwappable (20.5.3.2). The type of *first shall satisfy the requirements of
MoveConstructible (Table 23) and the requirements of MoveAssignable (Table 25).
2
Effects: For each non-negative integer i < (last - first), places the element from the position
first + i into position first + (i + (last - middle)) % (last - first).
3
Returns: first + (last - middle).
4
Remarks: This is a left rotate.
5
Complexity: At most last - first swaps.
template<class ForwardIterator, class OutputIterator>
constexpr OutputIterator
rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last,
OutputIterator result);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
rotate_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 middle, ForwardIterator1 last,
ForwardIterator2 result);
6
Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.
7
Effects: Copies the range [first, last) to the range [result, result + (last - first)) such
that for each non-negative integer i < (last - first) the following assignment takes place: *(result
+ i) = *(first + (i + (middle - first)) % (last - first)).
8
Returns: result + (last - first).
9
Complexity: Exactly last - first assignments.
28.6.12
Sample
[alg.random.sample]
template<class PopulationIterator, class SampleIterator,
class Distance, class UniformRandomBitGenerator>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
SampleIterator out, Distance n,
UniformRandomBitGenerator&& g);
1
Requires:
(1.1)
—
PopulationIterator shall satisfy the requirements of an input iterator (27.2.3).
(1.2)
—
SampleIterator shall satisfy the requirements of an output iterator (27.2.4).
(1.3)
—
SampleIterator shall satisfy the additional requirements of a random access iterator (27.2.7)
unless PopulationIterator satisfies the additional requirements of a forward iterator (27.2.5).
(1.4)
—
PopulationIterator’s value type shall be writable (27.2.1) to out.
(1.5)
—
Distance shall be an integer type.
(1.6)
—
remove_reference_t<UniformRandomBitGenerator> shall meet the requirements of a uniform
random bit generator type (29.6.1.3) whose return type is convertible to Distance.
(1.7)
—
out shall not be in the range [first, last).
2
Effects: Copies min(last - first, n) elements (the sample) from [first, last) (the population)
to out such that each possible sample has equal probability of appearance. [ Note: Algorithms that
obtain such effects include selection sampling and reservoir sampling.
— end note ]
3
Returns: The end of the resulting sample range.
4
Complexity: O(last - first).
5
Remarks:
§ 28.6.12
920
(5.1)
—
Stable if and only if PopulationIterator satisfies the requirements of a forward iterator.
(5.2)
—
To the extent that the implementation of this function makes use of random numbers, the object
g shall serve as the implementation’s source of randomness.
28.6.13
Shuffle
[alg.random.shuffle]
template<class RandomAccessIterator, class UniformRandomBitGenerator>
void shuffle(RandomAccessIterator first,
RandomAccessIterator last,
UniformRandomBitGenerator&& g);
1
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The
type remove_reference_t<UniformRandomBitGenerator> shall meet the requirements of a uniform
random bit generator (29.6.1.3) type whose return type is convertible to iterator_traits<Random-
AccessIterator>::difference_type.
2
Effects: Permutes the elements in the range [first, last) such that each possible permutation of
those elements has equal probability of appearance.
3
Complexity: Exactly (last - first) - 1 swaps.
4
Remarks: To the extent that the implementation of this function makes use of random numbers, the
object g shall serve as the implementation’s source of randomness.
28.7
Sorting and related operations
[alg.sorting]
1
All the operations in 28.7 have two versions: one that takes a function object of type Compare and one that
uses an operator<.
2
Compare is a function object type (23.14). The return value of the function call operation applied to an
object of type Compare, when contextually converted to bool (Clause 7), yields true if the first argument
of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms
assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the
dereferenced iterator.
3
For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j)
!= false defaults to *i < *j != false. For algorithms other than those described in 28.7.3, comp shall
induce a strict weak ordering on the values.
4
The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term
weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial
ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp
and equiv both be transitive relations:
(4.1)
—
comp(a, b) && comp(b, c) implies comp(a, c)
(4.2)
—
equiv(a, b) && equiv(b, c) implies equiv(a, c)
[ Note: Under these conditions, it can be shown that
(4.3)
—
equiv is an equivalence relation
(4.4)
—
comp induces a well-defined relation on the equivalence classes determined by equiv
(4.5)
—
The induced relation is a strict total ordering.
— end note ]
5
A sequence is sorted with respect to a comparator comp if for every iterator i pointing to the sequence and
every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence,
comp(*(i + n), *i) == false.
6
A sequence [start, finish) is partitioned with respect to an expression f(e) if there exists an integer n
such that for all 0 <= i < (finish - start), f(*(start + i)) is true if and only if i < n.
7
In the descriptions of the functions that deal with ordering relationships we frequently use a notion of
equivalence to describe concepts such as stability. The equivalence to which we refer is not necessarily an
operator==, but an equivalence relation induced by the strict weak ordering. That is, two elements a and b
are considered equivalent if and only if !(a < b) && !(b < a).
§ 28.7
921
|
|