28 Algorithms library [algorithms]

28.5 Non-modifying sequence operations [alg.nonmodifying]

28.5.1 All of [alg.all_of]

template <class InputIterator, class Predicate> 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> 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> 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> 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.
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 [algorithms.parallel.exec] 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> 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 [algorithms.parallel.exec] to make arbitrary copies of elements from the input sequence.

28.5.5 Find [alg.find]

template<class InputIterator, class T> 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> 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> InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred); 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> 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> 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) applications of the corresponding predicate.

28.5.7 Find first [alg.find.first.of]

template<class InputIterator, class ForwardIterator> 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> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred); 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> 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> 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, applications of the corresponding predicate.

28.5.9 Count [alg.count]

template<class InputIterator, class T> 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> 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.10 Mismatch [mismatch]

template<class InputIterator1, class InputIterator2> 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> 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> 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> 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> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> bool equal(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> 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> 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> 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 ([random.access.iterators]) and last1 - first1 != last2 - first2, then no applications of the corresponding predicate; otherwise,
    • (3.1.2)
      at most applications of the corresponding predicate.
  • (3.2)
    For the overloads with no ExecutionPolicy,
    • (3.2.1)
      if ForwardIterator1 and ForwardIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2, then no applications of the corresponding predicate; otherwise,
    • (3.2.2)
      applications of the corresponding predicate.

28.5.12 Is permutation [alg.is_permutation]

template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> 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 ForwardIterator2 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 , where N has the value last1 - first1.

28.5.13 Search [alg.search]

template<class ForwardIterator1, class ForwardIterator2> 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> 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> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); template<class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred); 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 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 ([conv.integral], [class.conv]).
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> 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.