25 Algorithms library [algorithms]

25.6 Non-modifying sequence operations [alg.nonmodifying]

25.6.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); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {});
1
#
Let E be:
  • (1.1)
    pred(*i) for the overloads in namespace std;
  • (1.2)
    invoke(pred, invoke(proj, *i)) for the overloads in namespace ranges.
2
#
Returns: false if E is false for some iterator i in the range [first, last), and true otherwise.
3
#
Complexity: At most last - first applications of the predicate and any projection.

25.6.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); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {});
1
#
Let E be:
  • (1.1)
    pred(*i) for the overloads in namespace std;
  • (1.2)
    invoke(pred, invoke(proj, *i)) for the overloads in namespace ranges.
2
#
Returns: true if E is true for some iterator i in the range [first, last), and false otherwise.
3
#
Complexity: At most last - first applications of the predicate and any projection.

25.6.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); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {});
1
#
Let E be:
  • (1.1)
    pred(*i) for the overloads in namespace std;
  • (1.2)
    invoke(pred, invoke(proj, *i)) for the overloads in namespace ranges.
2
#
Returns: false if E is true for some iterator i in the range [first, last), and true otherwise.
3
#
Complexity: At most last - first applications of the predicate and any projection.

25.6.4 For each [alg.foreach]

🔗
template<class InputIterator, class Function> constexpr Function for_each(InputIterator first, InputIterator last, Function f);
1
#
Preconditions: Function meets the Cpp17MoveConstructible requirements (Table 28).
[ Note
:
Function need not meet the requirements of Cpp17CopyConstructible (Table 29).
— 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 meets 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
#
Preconditions: Function meets the Cpp17CopyConstructible requirements.
7
#
Effects: Applies f to the result of dereferencing every iterator in the range [first, last).
[ Note
:
If the type of first meets 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<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirectly_­unary_­invocable<projected<I, Proj>> Fun> constexpr ranges::for_each_result<I, Fun> ranges::for_each(I first, S last, Fun f, Proj proj = {}); template<input_­range R, class Proj = identity, indirectly_­unary_­invocable<projected<iterator_t<R>, Proj>> Fun> constexpr ranges::for_each_result<borrowed_iterator_t<R>, Fun> ranges::for_each(R&& r, Fun f, Proj proj = {});
11
#
Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first, last), starting from first and proceeding to last - 1.
[ Note
:
If the result of invoke(proj, *i) is a mutable reference, f may apply non-constant functions.
— end note
 ]
12
#
Returns: {last, std​::​move(f)}.
13
#
Complexity: Applies f and proj exactly last - first times.
14
#
Remarks: If f returns a result, the result is ignored.
15
#
[ Note
:
The overloads in namespace ranges require Fun to model copy_­constructible.
— end note
 ]
🔗
template<class InputIterator, class Size, class Function> constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
16
#
Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).
17
#
Preconditions: Function meets the Cpp17MoveConstructible requirements.
[ Note
:
Function need not meet the requirements of Cpp17CopyConstructible.
— end note
 ]
18
#
Preconditions: n >= 0 is true.
19
#
Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n) in order.
[ Note
:
If the type of first meets the requirements of a mutable iterator, f may apply non-constant functions through the dereferenced iterator.
— end note
 ]
20
#
Returns: first + n.
21
#
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);
22
#
Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).
23
#
Preconditions: Function meets the Cpp17CopyConstructible requirements.
24
#
Preconditions: n >= 0 is true.
25
#
Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n).
[ Note
:
If the type of first meets the requirements of a mutable iterator, f may apply non-constant functions through the dereferenced iterator.
— end note
 ]
26
#
Returns: first + n.
27
#
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.
🔗
template<input_iterator I, class Proj = identity, indirectly_­unary_­invocable<projected<I, Proj>> Fun> constexpr ranges::for_each_n_result<I, Fun> ranges::for_each_n(I first, iter_difference_t<I> n, Fun f, Proj proj = {});
28
#
Preconditions: n >= 0 is true.
29
#
Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first, first + n) in order.
[ Note
:
If the result of invoke(proj, *i) is a mutable reference, f may apply non-constant functions.
— end note
 ]
30
#
Returns: {first + n, std​::​move(f)}.
31
#
Remarks: If f returns a result, the result is ignored.
32
#
[ Note
:
The overload in namespace ranges requires Fun to model copy_­constructible.
— end note
 ]

25.6.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); template<class ExecutionPolicy, class ForwardIterator, class Predicate> ForwardIterator find_if_not(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred); template<input_­iterator I, sentinel_­for<I> S, class T, class Proj = identity> requires indirect_­binary_­predicate<ranges::equal_to, projected<I, Proj>, const T*> constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); template<input_­range R, class T, class Proj = identity> requires indirect_­binary_­predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> constexpr borrowed_iterator_t<R> ranges::find(R&& r, const T& value, Proj proj = {}); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr borrowed_iterator_t<R> ranges::find_if(R&& r, Pred pred, Proj proj = {}); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr borrowed_iterator_t<R> ranges::find_if_not(R&& r, Pred pred, Proj proj = {});
1
#
Let E be:
  • (1.1)
    *i == value for find;
  • (1.2)
    pred(*i) != false for find_­if;
  • (1.3)
    pred(*i) == false for find_­if_­not;
  • (1.4)
    bool(invoke(proj, *i) == value) for ranges​::​find;
  • (1.5)
    bool(invoke(pred, invoke(proj, *i))) for ranges​::​find_­if;
  • (1.6)
    bool(!invoke(pred, invoke(proj, *i))) for ranges​::​find_­if_­not.
2
#
Returns: The first iterator i in the range [first, last) for which E is true.
Returns last if no such iterator is found.
3
#
Complexity: At most last - first applications of the corresponding predicate and any projection.

25.6.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); template<forward_­iterator I1, sentinel_­for<I1> S1, forward_­iterator I2, sentinel_­for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<I1, I2, Pred, Proj1, Proj2> constexpr subrange<I1> ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<forward_­range R1, forward_­range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> constexpr borrowed_subrange_t<R1> ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let:
  • (1.1)
    pred be equal_­to{} for the overloads with no parameter pred;
  • (1.2)
    E be:
    • (1.2.1)
      pred(*(i + n), *(first2 + n)) for the overloads in namespace std;
    • (1.2.2)
      invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))) for the overloads in namespace ranges;
  • (1.3)
    i be last1 if [first2, last2) is empty, or if (last2 - first2) > (last1 - first1) is true, or if there is no iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n < (last2 - first2), E is true. Otherwise i is the last such iterator in [first1, last1 - (last2 - first2)).
2
#
Returns:
  • (2.1)
    i for the overloads in namespace std.
  • (2.2)
    {i, i + (i == last1 ? 0 : last2 - first2)} for the overloads in namespace ranges.
3
#
Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate and any projections.

25.6.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); 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); template<input_­iterator I1, sentinel_­for<I1> S1, forward_­iterator I2, sentinel_­for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<I1, I2, Pred, Proj1, Proj2> constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, forward_­range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> constexpr borrowed_iterator_t<R1> ranges::find_first_of(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let E be:
  • (1.1)
    *i == *j for the overloads with no parameter pred;
  • (1.2)
    pred(*i, *j) != false for the overloads with a parameter pred and no parameter proj1;
  • (1.3)
    bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j))) for the overloads with parameters pred and proj1.
2
#
Effects: Finds an element that matches one of a set of values.
3
#
Returns: The first iterator i in the range [first1, last1) such that for some iterator j in the range [first2, last2) E holds.
Returns last1 if [first2, last2) is empty or if no such iterator is found.
4
#
Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate and any projections.

25.6.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); template<forward_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­binary_­predicate<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to> constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); template<forward_­range R, class Proj = identity, indirect_­binary_­predicate<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred = ranges::equal_to> constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
1
#
Let E be:
  • (1.1)
    *i == *(i + 1) for the overloads with no parameter pred;
  • (1.2)
    pred(*i, *(i + 1)) != false for the overloads with a parameter pred and no parameter proj;
  • (1.3)
    bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1)))) for the overloads with both parameters pred and proj.
2
#
Returns: The first iterator i such that both i and i + 1 are in the range [first, last) for which E holds.
Returns last if no such iterator is found.
3
#
Complexity: For the overloads with no ExecutionPolicy, exactly
applications of the corresponding predicate, where i is adjacent_­find's return value.
For the overloads with an ExecutionPolicy, applications of the corresponding predicate, and no more than twice as many applications of any projection.

25.6.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); template<input_­iterator I, sentinel_­for<I> S, class T, class Proj = identity> requires indirect_­binary_­predicate<ranges::equal_to, projected<I, Proj>, const T*> constexpr iter_difference_t<I> ranges::count(I first, S last, const T& value, Proj proj = {}); template<input_­range R, class T, class Proj = identity> requires indirect_­binary_­predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> constexpr range_difference_t<R> ranges::count(R&& r, const T& value, Proj proj = {}); template<input_­iterator I, sentinel_­for<I> S, class Proj = identity, indirect_­unary_­predicate<projected<I, Proj>> Pred> constexpr iter_difference_t<I> ranges::count_if(I first, S last, Pred pred, Proj proj = {}); template<input_­range R, class Proj = identity, indirect_­unary_­predicate<projected<iterator_t<R>, Proj>> Pred> constexpr range_difference_t<R> ranges::count_if(R&& r, Pred pred, Proj proj = {});
1
#
Let E be:
  • (1.1)
    *i == value for the overloads with no parameter pred or proj;
  • (1.2)
    pred(*i) != false for the overloads with a parameter pred but no parameter proj;
  • (1.3)
    invoke(proj, *i) == value for the overloads with a parameter proj but no parameter pred;
  • (1.4)
    bool(invoke(pred, invoke(proj, *i))) for the overloads with both parameters proj and pred.
2
#
Effects: Returns the number of iterators i in the range [first, last) for which E holds.
3
#
Complexity: Exactly last - first applications of the corresponding predicate and any projection.

25.6.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); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<I1, I2, Pred, Proj1, Proj2> constexpr ranges::mismatch_result<I1, I2> ranges::mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> constexpr ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>> ranges::mismatch(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let last2 be first2 + (last1 - first1) for the overloads with no parameter last2 or r2.
2
#
Let E be:
  • (2.1)
    !(*(first1 + n) == *(first2 + n)) for the overloads with no parameter pred;
  • (2.2)
    pred(*(first1 + n), *(first2 + n)) == false for the overloads with a parameter pred and no parameter proj1;
  • (2.3)
    !invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n))) for the overloads with both parameters pred and proj1.
3
#
Let N be .
4
#
Returns: { first1 + n, first2 + n }, where n is the smallest integer in [0, N) such that E holds, or N if no such integer exists.
5
#
Complexity: At most N applications of the corresponding predicate and any projections.

25.6.11 Equal [alg.equal]

🔗
template<class InputIterator1, class InputIterator2> constexpr 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> 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); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<I1, I2, Pred, Proj1, Proj2> constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1
#
Let:
  • (1.1)
    last2 be first2 + (last1 - first1) for the overloads with no parameter last2 or r2;
  • (1.2)
    pred be equal_­to{} for the overloads with no parameter pred;
  • (1.3)
    E be:
    • (1.3.1)
      pred(*i, *(first2 + (i - first1))) for the overloads with no parameter proj1;
    • (1.3.2)
      invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1)))) for the overloads with parameter proj1.
2
#
Returns: If last1 - first1 != last2 - first2, return false.
Otherwise return true if E holds for every iterator i in the range [first1, last1) Otherwise, returns false.
3
#
Complexity: If the types of first1, last1, first2, and last2: and last1 - first1 != last2 - first2, then no applications of the corresponding predicate and each projection; otherwise,
  • (3.3)
    For the overloads with no ExecutionPolicy, at most applications of the corresponding predicate and any projections.
  • (3.4)
    For the overloads with an ExecutionPolicy, applications of the corresponding predicate.

25.6.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); 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
#
Mandates: ForwardIterator1 and ForwardIterator2 have the same value type.
2
#
Preconditions: The comparison function is an equivalence relation.
3
#
Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.
4
#
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.
5
#
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.
🔗
template<forward_­iterator I1, sentinel_­for<I1> S1, forward_­iterator I2, sentinel_­for<I2> S2, class Proj1 = identity, class Proj2 = identity, indirect_­equivalence_­relation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = ranges::equal_to> constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<forward_­range R1, forward_­range R2, class Proj1 = identity, class Proj2 = identity, indirect_­equivalence_­relation<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to> constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
6
#
Returns: If last1 - first1 != last2 - first2, return false.
Otherwise return true if there exists a permutation of the elements in the range [first2, last2), bounded by [pfirst, plast), such that ranges​::​equal(first1, last1, pfirst, plast, pred, proj1, proj2) returns true; otherwise, returns false.
7
#
Complexity: No applications of the corresponding predicate and projections if:
  • (7.1)
    S1 and I1 model sized_­sentinel_­for<S1, I1>,
  • (7.2)
    S2 and I2 model sized_­sentinel_­for<S2, I2>, and
  • (7.3)
    last1 - first1 != last2 - first2.
Otherwise, exactly last1 - first1 applications of the corresponding predicate and projections if ranges​::​equal(​first1, last1, first2, last2, pred, proj1, proj2) would return true; otherwise, at worst , where N has the value last1 - first1.

25.6.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
#
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.
2
#
Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate.
🔗
template<forward_­iterator I1, sentinel_­for<I1> S1, forward_­iterator I2, sentinel_­for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<I1, I2, Pred, Proj1, Proj2> constexpr subrange<I1> ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<forward_­range R1, forward_­range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_­comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> constexpr borrowed_subrange_t<R1> ranges::search(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
3
#
Returns:
  • (3.1)
    {i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n less than last2 - first2 the condition 
    bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
    is true.
  • (3.2)
    Returns {last1, last1} if no such iterator exists.
4
#
Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate and projections.
🔗
template<class ForwardIterator, class Size, class T> constexpr ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); 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);
5
#
Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).
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<forward_­iterator I, sentinel_­for<I> S, class T, class Pred = ranges::equal_to, class Proj = identity> requires indirectly_­comparable<I, const T*, Pred, Proj> constexpr subrange<I> ranges::search_n(I first, S last, iter_difference_t<I> count, const T& value, Pred pred = {}, Proj proj = {}); template<forward_­range R, class T, class Pred = ranges::equal_to, class Proj = identity> requires indirectly_­comparable<iterator_t<R>, const T*, Pred, Proj> constexpr borrowed_subrange_t<R> ranges::search_n(R&& r, range_difference_t<R> count, const T& value, Pred pred = {}, Proj proj = {});
8
#
Returns: {i, i + count} where i is the first iterator in the range [first, last - count) such that for every non-negative integer n less than count, the following condition holds: invoke(pred, invoke(proj, *(i + n)), value).
Returns {last, last} if no such iterator is found.
9
#
Complexity: At most last - first applications of the corresponding predicate and projection.
🔗
template<class ForwardIterator, class Searcher> constexpr ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher& searcher);
10
#
Effects: Equivalent to: return searcher(first, last).first;
11
#
Remarks: Searcher need not meet the Cpp17CopyConstructible requirements.