std::search
Defined in header
<algorithm>
|
||
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, |
(1) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, |
(2) | (since C++17) |
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, |
(3) | |
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, |
(4) | (since C++17) |
template<class ForwardIterator, class Searcher>
ForwardIterator search( ForwardIterator first, ForwardIterator last, |
(5) | (since C++17) |
[s_first, s_last)
in the range [first, last - (s_last - s_first))
.operator==
.p
.policy
. These overloads do not participate in overload resolution unless std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is truesearcher
. Effectively executes return searcher(first, last).first;. Searcher
need not be CopyConstructible
.
The standard library provides the following searchers:
|
(since C++17) |
Contents |
[edit] Parameters
first, last | - | the range of elements to examine |
s_first, s_last | - | the range of elements to search for |
policy | - | the execution policy to use. See execution policy for details. |
searcher | - | the searcher encapsulating the search algorithm and the pattern to look 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: bool pred(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function must not modify the objects passed to it. |
Type requirements | ||
-
ForwardIt1, ForwardIt2 must meet the requirements of ForwardIterator .
|
||
-
Searcher must meet the requirements of Searcher .
|
[edit] Return value
[s_first, s_last)
in the range [first, last - (s_last - s_first))
. If no such subsequence is found, last
is returned.If
[s_first, s_last)
is empty, first
is returned. (since C++11)
searcher.operator()
, that is, an iterator to the location at which the substring is found or a copy of last
if it was not found.[edit] Complexity
S*N
comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).[edit] Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception,
-
- if
policy
is std::parallel_vector_execution_policy, std::terminate is called - if
policy
is std::sequential_execution_policy or std::parallel_execution_policy, the algorithm exits with an std::exception_list containing all uncaught exceptions. If there was only one uncaught exception, the algorithm may rethrow it without wrapping in std::exception_list. It is unspecified how much work the algorithm will perform before returning after the first exception was encountered. - if
policy
is some other type, the behavior is implementation-defined
- if
- If the algorithm fails to allocate memory (either for itself or to construct an std::exception_list when handling a user exception), std::bad_alloc is thrown.
[edit] Possible implementation
First version |
---|
template<class ForwardIt1, class ForwardIt2> ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last) { for (; ; ++first) { ForwardIt1 it = first; for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) { if (s_it == s_last) { return first; } if (it == last) { return last; } if (!(*it == *s_it)) { break; } } } } |
Second version |
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate> ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p) { for (; ; ++first) { ForwardIt1 it = first; for (ForwardIt2 s_it = s_first; ; ++it, ++s_it) { if (s_it == s_last) { return first; } if (it == last) { return last; } if (!p(*it, *s_it)) { break; } } } } |
[edit] Example
#include <string> #include <algorithm> #include <iostream> #include <vector> template<typename Container> bool in_quote(const Container& cont, const std::string& s) { return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end(); } int main() { std::string str = "why waste time learning, when ignorance is instantaneous?"; // str.find() can be used as well std::cout << std::boolalpha << in_quote(str, "learning") << '\n' << in_quote(str, "lemming") << '\n'; std::vector<char> vec(str.begin(), str.end()); std::cout << std::boolalpha << in_quote(vec, "learning") << '\n' << in_quote(vec, "lemming") << '\n'; // The C++17 overload demo: std::string in = "Lorem ipsum dolor sit amet, consectetur adipiscing elit," " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua"; std::string needle = "pisci"; auto it = std::search(in.begin(), in.end(), std::make_boyer_moore_searcher( needle.begin(), needle.end())); if(it != in.end()) std::cout << "The string " << needle << " found at offset " << it - in.begin() << '\n'; else std::cout << "The string " << needle << " not found\n"; }
Output:
true false true false The string pisci found at offset 43
[edit] See also
finds the last sequence of elements in a certain range (function template) |
|
returns true if one set is a subset of another (function template) |
|
determines if two sets of elements are the same (function template) |
|
(C++11)
|
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) |
|
(C++17)
|
standard C++ library search algorithm implementation (class template) |
(C++17)
|
Boyer-Moore search algorithm implementation (class template) |
(C++17)
|
Boyer-Moore-Horspool search algorithm implementation (class template) |
(parallelism TS)
|
parallelized version of std::search (function template) |