search


function template
<algorithm>
template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 search ( 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 );

Find subsequence in range

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

The sequence of elements in [first2,last2) is compared to the possible subsequences of successive elements within [first1,last1) by either applying the == comparison operator or the template parameter comp (for the second version).

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)
{
  ForwardIterator1 it1, limit;
  ForwardIterator2 it2;

  limit=first1; advance(limit,1+distance(first1,last1)-distance(first2,last2));

  while (first1!=limit)
  {
    it1 = first1; it2 = first2;
    while (*it1==*it2)        // or: while (pred(*it1,*it2)) for the pred version
      { ++it1; ++it2; if (it2==last2) return first1; }
    ++first1;
  }
  return last1;
}


A similar algorithm function, but returning the last occurrence instead of the first, is find_end.

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).
pred
Binary predicate taking two elements as argument (one of each of the two sequences), and returning the result of the comparison between them, with true (non-zero) meaning that they are to be considered equal, and false (zero) that they are not-equal. This can either be a pointer to a function or an object whose class overloads operator().


Return value

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

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
// search algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

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


  // using default comparison:
  int match1[] = {40,50,60,70};
  it = search (myvector.begin(), myvector.end(), match1, match1+4);

  if (it!=myvector.end())
    cout << "match1 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match1 not found" << endl;

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

  if (it!=myvector.end())
    cout << "match2 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match2 not found" << endl;
  
  return 0;
}


Output:
match1 found at position 3
match2 not found


Complexity

At most, performs count2*(1+count1-count2) comparisons or applications of pred (where countX is the distance between firstX and lastX).

See also

find_end Find last subsequence in range (function template)
search_n Find succession of equal values in range (function template)
equal Test whether the elements in two ranges are equal (function template)
mismatch Return first position where two ranges differ (function template)
find Find value in range (function template)