Login
\\
Searches for the first occurrence of a subrange
Key Facts
Gyroscopic Couple: The rate of change of angular momentum (= Moment of Inertia.
= Angular velocity
= Angular velocity of precession.
Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.
Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.
Definition
The search() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.Interface
#include <algorithm> template < class ForwardIterator1, class ForwardIterator2 > ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); template < class ForwardIterator1, class ForwardIterator2, class Pr > ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 BinaryPredicate comp );Parameters:
| Parameter | Description |
|---|---|
| first1 | A forward iterator addressing the position of the first element in the range to be searched |
| last1 | A forward iterator addressing the position one past the final element in the range to be searched |
| first2 | A forward iterator addressing the position of the first element in the range to be matched |
| last2 | A forward iterator addressing the position one past the final element in the range to be matched |
| comp | User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied |
Description
This function searches a subsequence (elements fromfi rst2 to last2 ) into sequence (elements from first1 to last1 ).
The two forms of search differ in how they determine if two elements are the same: the first uses operator== and the second uses the user-supplied function object comp.Return Value
The return value is a forward iterator addressing the position of the first element of the first subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate. If the subsequence wasn't found,last1 is returned.Complexity
The complexity is linear, and worst case complexity is also linear with respect to the size of the sequence being searched for.References
Example:
Example - search algorithm
Problem
This program illustrates the use of the STL search() algorithm (default version) to find the first occurrence of one range of integer values in a vector within another range of integer values, also in a vector.
Workings
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 9, 10, 11}; vector<int> v1(a1, a1+14); cout <<"\nHere are the contents of v1:\n"; for (vector<int>::size_type i=0; i<v1.size(); i++) cout <<v1.at(i)<<" "; int a2[] = {3, 4, 5}; vector<int> v2(a2, a2+3); cout <<"\nHere are the contents of v2:\n"; for (vector<int>::size_type i=0; i<v2.size(); i++) cout <<v2.at(i)<<" "; vector<int>::iterator p; p = search(v1.begin(), v1.end(), v2.begin(), v2.end()); if (p != v1.end()) cout <<"\nThe first instance of v2 in v1 begins at location "<<(int)(p-v1.begin()+1)<<"."; else cout <<"\nNo instance of v2 was found in v1."; p = search(p+1, v1.end(), v2.begin(), v2.end()); if (p != v1.end()) cout <<"\nThe next instance of v2 in v1 begins at location "<<(int)(p-v1.begin()+1)<<"."; else cout<<"\nNo further instance of v2 was found in v1."; p = search(p+1, v1.end(), v2.begin(), v2.end()); if (p != v1.end()) cout <<"\nThe next instance of v2 in v1 begins at location "<< (int)(p-v1.begin()+1)<<"."; else cout <<"\nNo further instance of v2 was found in v1."; return 0; }
Solution
Output:
Here are the contents of v1:
1 2 3 4 5 6 7 8 3 4 5 9 10 11
Here are the contents of v2:
3 4 5
The first instance of v2 in v1 begins at location 3.
The next instance of v2 in v1 begins at location 9.
No further instance of v2 was found in v1.
References