std::search

equality (1)	template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);
predicate (2)	template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

equality (1)

template <class ForwardIterator1, class ForwardIterator2>   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,                            ForwardIterator2 first2, ForwardIterator2 last2);

predicate (2)

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>   ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,                            ForwardIterator2 first2, ForwardIterator2 last2,                            BinaryPredicate pred);

Search range for subsequence

Searches the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element, or last1 if no occurrences are found.

The elements in both ranges are compared sequentially using operator== (or pred, in version (2)): A subsequence of [first1,last1) is considered a match only when this is true for all the elements of [first2,last2).

This function returns the first of such occurrences. For an algorithm that returns the last instead, see find_end.

The behavior of this function template is equivalent to:

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)
{
  if (first2==last2) return first1;  // specified in C++11
  
  while (first1!=last1)
  {
    ForwardIterator1 it1 = first1;
    ForwardIterator2 it2 = first2;
    while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version 2
        ++it1; ++it2;
        if (it2==last2) return first1;
        if (it1==last1) return last1;
    }
    ++first1;
  }
  return last1;
}

Parameters

first1, last1: Forward iterators to the initial and final positions of the searched sequence. The range used is [first1,last1), which contains all the elements between first1 and last1, including the element pointed by first1 but not the element pointed by last1.
first2, last2: Forward iterators to the initial and final positions of the sequence to be searched for. The range used is [first2,last2).
For (1), the elements in both ranges shall be of types comparable using operator== (with the elements of the first range as left-hand side operands, and those of the second as right-hand side operands).
pred: Binary function that accepts two elements as arguments (one of each of the two sequences, in the same order), and returns a value convertible to bool. The returned value indicates whether the elements are considered to match in the context of this function.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Return value

An iterator to the first element of the first occurrence of [first2,last2) in [first1,last1).
If the sequence is not found, the function returns last1.

If [first2,last2) is an empty range, the result is unspecified.

If [first2,last2) is an empty range, the function returns first1.

Example

// search algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::search
#include <vector>       // std::vector

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  std::vector<int> haystack;

  // set some values:        haystack: 10 20 30 40 50 60 70 80 90
  for (int i=1; i<10; i++) haystack.push_back(i*10);

  // using default comparison:
  int needle1[] = {40,50,60,70};
  std::vector<int>::iterator it;
  it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4);

  if (it!=haystack.end())
    std::cout << "needle1 found at position " << (it-haystack.begin()) << '\n';
  else
    std::cout << "needle1 not found\n";

  // using predicate comparison:
  int needle2[] = {20,30,50};
  it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate);

  if (it!=haystack.end())
    std::cout << "needle2 found at position " << (it-haystack.begin()) << '\n';
  else
    std::cout << "needle2 not found\n";

  return 0;
}

Output:

needle1 found at position 3
needle2 not found

Complexity

Up to linear in count1*count2 (where countX is the distance between firstX and lastX): Compares elements until a matching subsequence is found.

Data races

Some (or all) of the objects in both ranges are accessed (possibly more than once).

Exceptions

Throws if any of the element comparisons (or pred) throws or if any of the operations on iterators throws.
Note that invalid arguments cause undefined behavior.