25 Algorithms library [algorithms]

25.6 Non-modifying sequence operations [alg.nonmodifying]

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

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.

🔗

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 = {});

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.

🔗

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

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

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.

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 = {});

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.

🔗

template<class ForwardIterator, class Searcher>
  constexpr ForwardIterator
    search(ForwardIterator first, ForwardIterator last, const Searcher& searcher);

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

Remarks: Searcher need not meet the Cpp17CopyConstructible requirements.