std::search
From Cppreference
Defined in header <algorithm>
|
||
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last, |
(1) | |
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last, |
(2) | |
Searches for the first subsequence of elements [s_first, s_last) in the range [first, last). The first version uses operator== to compare the elements, the second version uses the given binary predicate p.
Contents |
[edit] Parameters
first, last | - | the range of elements to examine | |||||||||
s_first, s_last | - | the range of elements to search for | |||||||||
p | - | binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. |
[edit] Return value
iterator to the beginning of first subsequence [s_first, s_last) in the range [first, last). If no such subsequence is found, last is returned.
[edit] Complexity
At most S*N comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).
[edit] Equivalent function
First version |
---|
template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 s_first, ForwardIterator2 s_last) { ForwardIterator1 t_last = first; size_t cmp_len = std::distance(first, last) - std::distance(s_first - s_last) + 1; std::advance(t_last, cmp_len); for (; first != t_last; ++first) { ForwardIterator1 it = first; ForwardIterator2 s_it = s_first; while (*it == *s_it) { ++it; ++s_it; if (s_it == s_last) { return first; } } } return last; } |
Second version |
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 s_first, ForwardIterator2 s_last, BinaryPredicate p) { ForwardIterator1 t_last = first; size_t cmp_len = std::distance(first, last) - std::distance(s_first - s_last) + 1; std::advance(t_last, cmp_len); for (; first != t_last; ++first) { ForwardIterator1 it = first; ForwardIterator2 s_it = s_first; while (p(*it, *s_it)) { ++it; ++s_it; if (s_it == s_last) { return first; } } } return last; } |
[edit] Example
This section is incomplete |
[edit] See also
|
finds the last sequence of elements in a certain range (function template) |
||
|
determines if two sets of elements are the same (function template) |
||
|
finds the first element satisfying specific criteria (function template) |
||
|
returns true if one range is lexicographically less than another (function template) |
||
|
finds the first position where two ranges differ (function template) |
||
|
searches for a number consecutive copies of an element in a range (function template) |