27 Algorithms library [algorithms]

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.

Returns: false if E is false for some iterator i in the range [first, last), and true otherwise.

Complexity: At most last - first applications of the predicate and any projection.

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.

Returns: true if E is true for some iterator i in the range [first, last), and false otherwise.

Complexity: At most last - first applications of the predicate and any projection.

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.

Returns: false if E is true for some iterator i in the range [first, last), and true otherwise.

Complexity: At most last - first applications of the predicate and any projection.

Returns: ranges​::​find(std​::​move(first), last, value, proj) != last.

Returns: first2 == last2 || !ranges​::​search(first1, last1, first2, last2, pred, proj1, proj2).empty().

Preconditions: Function meets the Cpp17MoveConstructible requirements (Table 31).

Effects: Applies f to the result of dereferencing every iterator in the range [first, last), starting from first and proceeding to last - 1.

Returns: f.

Complexity: Applies f exactly last - first times.

Remarks: If f returns a result, the result is ignored.

Preconditions: Function meets the Cpp17CopyConstructible requirements.

Effects: Applies f to the result of dereferencing every iterator in the range [first, last).

Complexity: Applies f exactly last - first times.

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.

Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first, last), starting from first and proceeding to last - 1.

Returns: {last, std​::​move(f)}.

Complexity: Applies f and proj exactly last - first times.

Remarks: If f returns a result, the result is ignored.

Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).

Preconditions: n >= 0 is true.

Function meets the Cpp17MoveConstructible requirements.

Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n) in order.

Returns: first + n.

Remarks: If f returns a result, the result is ignored.

Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).

Preconditions: n >= 0 is true.

Function meets the Cpp17CopyConstructible requirements.

Effects: Applies f to the result of dereferencing every iterator in the range [first, first + n).

Returns: first + n.

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.

Preconditions: n >= 0 is true.

Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first, first + n) in order.

Returns: {first + n, std​::​move(f)}.

Remarks: If f returns a result, the result is ignored.

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.

Returns: The first iterator i in the range [first, last) for which E is true.

Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate and any projection.

Let E be:

• (1.1)
  bool(invoke(proj, *i) == value) for ranges​::​find_last;
• (1.2)
  bool(invoke(pred, invoke(proj, *i))) for ranges​::​find_last_if;
• (1.3)
  bool(!invoke(pred, invoke(proj, *i))) for ranges​::​find_last_if_not.

Returns: Let i be the last iterator in the range [first, last) for which E is true.

Returns {i, last}, or {last, last} if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate and projection.

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)).

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.

Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate and any projections.

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.

Effects: Finds an element that matches one of a set of values.

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.

Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate and any projections.

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.

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.

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\left(\text{last - first}\right)$ applications of the corresponding predicate, and no more than twice as many applications of any projection.

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.

Effects: Returns the number of iterators i in the range [first, last) for which E holds.

Complexity: Exactly last - first applications of the corresponding predicate and any projection.

Let last2 be first2 + (last1 - first1) for the overloads with no parameter last2 or r2.

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.

Let N be min(last1 - first1,  last2 - first2).

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.

Complexity: At most N applications of the corresponding predicate and any projections.

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.

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.

Complexity: If

• (3.1)
  the types of first1, last1, first2, and last2 meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) and last1 - first1 != last2 - first2 for the overloads in namespace std;
• (3.2)
  the types of first1, last1, first2, and last2 pairwise model sized_sentinel_for ([iterator.concept.sizedsentinel]) and last1 - first1 != last2 - first2 for the first overload in namespace ranges,
• (3.3)
  R1 and R2 each model sized_range and ranges​::​distance(r1) != ranges​::​distance(r2) for the second overload in namespace ranges,

then no applications of the corresponding predicate and each projection; otherwise,

• (3.4)
  For the overloads with no ExecutionPolicy, at most min(last1 - first1,  last2 - first2) applications of the corresponding predicate and any projections.
• (3.5)
  For the overloads with an ExecutionPolicy, $O(min(\text{last1 - first1},\text{last2 - first2}\left)\right)$ applications of the corresponding predicate.

Let last2 be first2 + (last1 - first1) for the overloads with no parameter named last2, and let pred be equal_to{} for the overloads with no parameter pred.

Mandates: ForwardIterator1 and ForwardIterator2 have the same value type.

Preconditions: The comparison function is an equivalence relation.

Returns: If last1 - first1 != last2 - first2, return false.

Otherwise return true if there exists a permutation of the elements in the range [first2, last2), beginning with ForwardIterator2 begin, such that equal(first1, last1, begin, pred) returns true; otherwise, returns false.

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, pred) would return true; otherwise, at worst $O\left(N^2\right)$, where N has the value last1 - first1.

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.

Complexity: No applications of the corresponding predicate and projections if

• (7.1)
  for the first overload,
  • (7.1.1)
    S1 and I1 model sized_sentinel_for<S1, I1>,
  • (7.1.2)
    S2 and I2 model sized_sentinel_for<S2, I2>, and
  • (7.1.3)
    last1 - first1 != last2 - first2;
• (7.2)
  for the second overload, R1 and R2 each model sized_range, and ranges​::​distance(r1) != ranges​::​distance(r2).

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 $O\left(N^2\right)$, where N has the value last1 - first1.

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.

Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate.

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.

Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate and projections.

Mandates: The type Size is convertible to an integral type ([conv.integral], [class.conv]).

Let E be pred(*(i + n), value) != false for the overloads with a parameter pred, and *(i + n) == value otherwise.

Returns: The first iterator i in the range [first, last-count) such that for every non-negative integer n less than count the condition E is true.

Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate.

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.

Complexity: At most last - first applications of the corresponding predicate and projection.

Effects: Equivalent to: return searcher(first, last).first;

Remarks: Searcher need not meet the Cpp17CopyConstructible requirements.

Returns: ranges::mismatch(std::move(first1), last1, std::move(first2), last2, pred, proj1, proj2).in2 == last2

Let N1 be last1 - first1 and N2 be last2 - first2.

Returns: false if N1 < N2, otherwise ranges::equal(std::move(first1) + (N1 - N2), last1, std::move(first2), last2, pred, proj1, proj2)

Let N1 be ranges​::​distance(r1) and N2 be ranges​::​distance(r2).

Returns: false if N1 < N2, otherwise ranges::equal(views::drop(ranges::ref_view(r1), N1 - static_cast<decltype(N1)>(N2)), r2, pred, proj1, proj2)

Returns: ranges::fold_left_with_iter(std::move(first), last, std::move(init), f).value

Returns: ranges::fold_left_first_with_iter(std::move(first), last, f).value

Effects: Equivalent to: using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>; if (first == last) return U(std::move(init)); I tail = ranges::next(first, last); U accum = invoke(f, *--tail, std::move(init)); while (first != tail) accum = invoke(f, *--tail, std::move(accum)); return accum;

Let U be decltype(ranges​::​fold_right(first, last, iter_value_t<I>(*first), f)).

Effects: Equivalent to: if (first == last) return optional<U>(); I tail = ranges::prev(ranges::next(first, std::move(last))); return optional<U>(in_place, ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), std::move(f)));

Let U be decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>.

Effects: Equivalent to: if (first == last) return {std::move(first), U(std::move(init))}; U accum = invoke(f, std::move(init), *first); for (++first; first != last; ++first) accum = invoke(f, std::move(accum), *first); return {std::move(first), std::move(accum)};

Remarks: The return type is fold_left_with_iter_result<I, U> for the first overload and fold_left_with_iter_result<borrowed_iterator_t<R>, U> for the second overload.

Let U be decltype(ranges::fold_left(std::move(first), last, iter_value_t<I>(*first), f))

Effects: Equivalent to: if (first == last) return {std::move(first), optional<U>()}; optional<U> init(in_place, *first); for (++first; first != last; ++first) *init = invoke(f, std::move(*init), *first); return {std::move(first), std::move(init)};

Remarks: The return type is fold_left_first_with_iter_result<I, optional<U>> for the first overload and fold_left_first_with_iter_result<borrowed_iterator_t<R>, optional<U>> for the second overload.