std::search

Defined in header `<algorithm>`
	(1)
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );			(until C++20)
template< class ForwardIt1, class ForwardIt2 > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );			(since C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );		(2)	(since C++17)
		(3)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );				(until C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );				(since C++20)
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 );			(4)	(since C++17)
			(5)
template< class ForwardIt, class Searcher > ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );					(since C++17) (until C++20)
template< class ForwardIt, class Searcher > constexpr ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );					(since C++20)

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==.

3) Elements are compared using the given binary predicate p.

2,4) Same as (1,3), but executed according to policy. These overloads do not participate in overload resolution unless std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> (until C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> (since C++20) is true.

5) Searches the sequence

[first, last)

for the pattern specified in the constructor of searcher. Effectively executes return searcher(first, last).first;. Searcher need not be CopyConstructible.

The standard library provides the following searchers:

default_searcher (C++17)	standard C++ library search algorithm implementation (class template)
boyer_moore_searcher (C++17)	Boyer-Moore search algorithm implementation (class template)
boyer_moore_horspool_searcher (C++17)	Boyer-Moore-Horspool search algorithm implementation (class template)

(since C++17)

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); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for `Type1` a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that objects of types ForwardIt1 and ForwardIt2 can be dereferenced and then implicitly converted to Type1 and Type2 respectively.
Type requirements
- `ForwardIt1, ForwardIt2` must meet the requirements of LegacyForwardIterator.
- `Searcher` must meet the requirements of 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 no such occurrence is found, last is returned.
If [s_first, s_last) is empty, first is returned. (since C++11)

5) Returns the result of 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.

Complexity

1-4) At most S*N comparisons where S = std::distance(s_first, s_last) and N = std::distance(first, last).

5) Depends on the searcher

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 other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

First version

template<class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last)
{
    while (1) {
        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;
    }
}

Second version

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last, 
                            BinaryPredicate p)
{
    while (1) {
        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;
    }
}

Example

Run this code

#include <string_view>
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
 
template <typename Container>
bool contains(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 << contains(str, "learning") << '\n'   // true
                                << contains(str, "lemming")  << '\n';  // false
 
    std::vector<char> vec(str.begin(), str.end());
    std::cout << contains(vec, "learning") << '\n'   // true
              << contains(vec, "leaning")  << '\n';  // false
 
    // The C++17 overload demo:
    constexpr std::string_view haystack =
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua";
    const std::string needle {"pisci"};
 
    if (auto it = std::search(haystack.begin(), haystack.end(),
                      std::boyer_moore_searcher(needle.begin(), needle.end()));
        it != haystack.end())
    {
        std::cout << "The string " << quoted(needle, '\'') << " found at offset "
                  << it - haystack.begin() << '\n';
    } else {
        std::cout << "The string " << std::quoted(needle) << " not found\n";
    }
}

Output:

true
false
true
false
The string 'pisci' found at offset 43

Compiler support
Freestanding and hosted
Language
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Technical specifications
Symbols index
External libraries

find_end	finds the last sequence of elements in a certain range (function template)
includes	returns true if one sequence is a subsequence of another (function template)
equal	determines if two sets of elements are the same (function template)
findfind_iffind_if_not (C++11)	finds the first element satisfying specific criteria (function template)
lexicographical_compare	returns true if one range is lexicographically less than another (function template)
mismatch	finds the first position where two ranges differ (function template)
search_n	searches a range for a number of consecutive copies of an element (function template)
default_searcher (C++17)	standard C++ library search algorithm implementation (class template)
boyer_moore_searcher (C++17)	Boyer-Moore search algorithm implementation (class template)
boyer_moore_horspool_searcher (C++17)	Boyer-Moore-Horspool search algorithm implementation (class template)
ranges::search (C++20)	searches for a range of elements (niebloid)