std::search() algorithm
- od C++20
- od C++17
- do C++17
// (1)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (4)
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (5)
template< class ForwardIt, class Searcher >
constexpr ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );
// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (4)
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy,
ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (5)
template< class ForwardIt, class Searcher >
ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );
// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
Searches for the first occurence of a range of elements inside another range.
-
(1 - 4) Searches for the first occurrence of the sequence of elements [
s_first
;s_last
) in the range [first
;last
):-
(1) Elements are compared using
operator==
. -
(2) Elements are compared using the given binary predicate
p
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(od C++20) istrue
.
-
-
(5) Searches the sequence [
first
;last
) for the pattern specified in the constructor ofsearcher
. Effectively executesreturn searcher(first, last).first;
.importantSearcher cannot be CopyConstructible.
The standard library provides the following searchers:
- od C++17
default_searcher Standard C++ library search algorithm implementation. boyer_moore_searcher Boyer-Moore search algorithm implementation. boyer_moore_horspool_searcher Boyer-Moore-Horspool search algorithm implementation.
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
|
Type requirements
ForwardIt1 ForwardIt2 | LegacyForwardIterator |
Searcher | Searcher |
Return value
-
(1 - 4) Iterator to the beginning of first occurrence of the sequence [
s_first
;s_last
) in the range [first
;last
). If [s_first
;s_last
) is empty or if no such sequence is found,last
is returned. (od C++11)
If no such sequence is found,last
is returned. (do C++11) -
(5) Returns the result of searcher's
operator()
, that is, an iterator to the location at which the substring is found or a copy oflast
if it was not found.
Complexity
(1 - 4) Given S
as std::distance(s_first, s_last)
and N
as std::distance(first, last)
:
At most S * N comparisons.
(5) Depends on the searcher. Standard searchers don't have a guaranteed complexity.
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 and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
search (1)
template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last)
{
while (true)
{
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;
}
++first;
}
}
search (2)
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p)
{
while (true)
{
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;
}
++first;
}
}
Examples
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <vector>
using namespace std::literals;
bool contains(const auto& cont, std::string_view s)
{
// str.find() (or str.contains(), since C++23) can be used as well
return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
int main()
{
const auto str {"why waste time learning, when ignorance is instantaneous?"sv};
std::cout << std::boolalpha
<< contains(str, "learning") << '\n' // true
<< contains(str, "lemming") << '\n'; // false
const std::vector vec(str.begin(), str.end());
std::cout << contains(vec, "learning") << '\n' // true
<< contains(vec, "leaning") << '\n'; // false
// The C++17 overload with searchers demo:
constexpr auto haystack
{
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
"do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
};
for (const auto needle : {"pisci"sv, "Pisci"sv})
{
const std::boyer_moore_searcher searcher(needle.begin(), needle.end());
const auto it = std::search(haystack.begin(), haystack.end(), searcher);
std::cout << "The string " << std::quoted(needle) << ' ';
if (it == haystack.end())
std::cout << "not found\n";
else
std::cout << "found at offset " << it - haystack.begin() << '\n';
}
}
true
false
true
false
The string "pisci" found at offset 43
The string "Pisci" not found
Hover to see the original license.