[func.search]

# 22 General utilities library [[utilities]](./#utilities)

## 22.10 Function objects [[function.objects]](function.objects#func.search)

### 22.10.18 Searchers [func.search]

#### [22.10.18.1](#general) General [[func.search.general]](func.search.general)

[1](#general-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15269)

Subclause [func.search] provides function object types ([[function.objects]](function.objects "22.10 Function objects")) for
operations that search for a sequence [pat_first, pat_last) in another
sequence [first, last) that is provided to the object's function call
operator[.](#general-1.sentence-1)

The first sequence (the pattern to be searched for) is provided to
the object's constructor, and the second (the sequence to be searched) is
provided to the function call operator[.](#general-1.sentence-2)

[2](#general-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15277)

Each specialization of a class template specified in [func.search]
shall meet the [*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]") and [*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#general-2.sentence-1)

Template parameters named

- [(2.1)](#general-2.1)

ForwardIterator,

- [(2.2)](#general-2.2)

ForwardIterator1,

- [(2.3)](#general-2.3)

ForwardIterator2,

- [(2.4)](#general-2.4)

RandomAccessIterator,

- [(2.5)](#general-2.5)

RandomAccessIterator1,

- [(2.6)](#general-2.6)

RandomAccessIterator2, and

- [(2.7)](#general-2.7)

BinaryPredicate

of templates specified in
[func.search] shall meet the same requirements and semantics as
specified in [[algorithms.general]](algorithms.general "26.1 General")[.](#general-2.sentence-2)

Template parameters named Hash shall meet the [*Cpp17Hash*](hash.requirements#:Cpp17Hash "16.4.4.5 Cpp17Hash requirements [hash.requirements]") requirements (Table [37](hash.requirements#tab:cpp17.hash "Table 37: Cpp17Hash requirements"))[.](#general-2.sentence-3)

[3](#general-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15296)

The Boyer-Moore searcher implements the Boyer-Moore search algorithm[.](#general-3.sentence-1)

The Boyer-Moore-Horspool searcher implements the Boyer-Moore-Horspool search algorithm[.](#general-3.sentence-2)

In general, the Boyer-Moore searcher will use more memory and give better runtime performance than Boyer-Moore-Horspool[.](#general-3.sentence-3)

#### [22.10.18.2](#default) Class template default_searcher [[func.search.default]](func.search.default)

[ð](#lib:default_searcher)

namespace std {template<class ForwardIterator1, class BinaryPredicate = equal_to<>>class default_searcher {public:constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
 BinaryPredicate pred = BinaryPredicate()); template<class ForwardIterator2>constexpr pair<ForwardIterator2, ForwardIterator2>operator()(ForwardIterator2 first, ForwardIterator2 last) const; private: ForwardIterator1 pat_first_; // *exposition only* ForwardIterator1 pat_last_; // *exposition only* BinaryPredicate pred_; // *exposition only*};}

[ð](#lib:default_searcher,constructor)

`constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
                           BinaryPredicate pred = BinaryPredicate());
`

[1](#default-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15331)

*Effects*: Constructs a default_searcher object, initializing pat_first_ with pat_first, pat_last_ with pat_last, andpred_ with pred[.](#default-1.sentence-1)

[2](#default-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15338)

*Throws*: Any exception thrown by the copy constructor of BinaryPredicate orForwardIterator1[.](#default-2.sentence-1)

[ð](#lib:operator(),default_searcher)

`template<class ForwardIterator2>
  constexpr pair<ForwardIterator2, ForwardIterator2>
    operator()(ForwardIterator2 first, ForwardIterator2 last) const;
`

[3](#default-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15352)

*Effects*: Returns a pair of iterators i and j such that

- [(3.1)](#default-3.1)

i == search(first, last, pat_first_, pat_last_, pred_), and

- [(3.2)](#default-3.2)

if i == last, then j == last,
otherwise j == next(i, distance(pat_first_, pat_last_))[.](#default-3.sentence-1)

#### [22.10.18.3](#bm) Class template boyer_moore_searcher [[func.search.bm]](func.search.bm)

[ð](#lib:boyer_moore_searcher)

namespace std {template<class RandomAccessIterator1, class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>, class BinaryPredicate = equal_to<>>class boyer_moore_searcher {public: boyer_moore_searcher(RandomAccessIterator1 pat_first,
 RandomAccessIterator1 pat_last,
 Hash hf = Hash(),
 BinaryPredicate pred = BinaryPredicate()); template<class RandomAccessIterator2> pair<RandomAccessIterator2, RandomAccessIterator2>operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; private: RandomAccessIterator1 pat_first_; // *exposition only* RandomAccessIterator1 pat_last_; // *exposition only* Hash hash_; // *exposition only* BinaryPredicate pred_; // *exposition only*};}

[ð](#lib:boyer_moore_searcher,constructor)

`boyer_moore_searcher(RandomAccessIterator1 pat_first,
                     RandomAccessIterator1 pat_last,
                     Hash hf = Hash(),
                     BinaryPredicate pred = BinaryPredicate());
`

[1](#bm-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15399)

*Preconditions*: The value type of RandomAccessIterator1 meets
the [*Cpp17DefaultConstructible*](utility.arg.requirements#:Cpp17DefaultConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]"),[*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]"), and[*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#bm-1.sentence-1)

[2](#bm-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15406)

Let V be iterator_traits<RandomAccessIterator1>​::​value_type[.](#bm-2.sentence-1)

For any two values A and B of type V,
if pred(A, B) == true, then hf(A) == hf(B) is true[.](#bm-2.sentence-2)

[3](#bm-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15411)

*Effects*: Initializespat_first_ with pat_first,pat_last_ with pat_last,hash_ with hf, andpred_ with pred[.](#bm-3.sentence-1)

[4](#bm-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15420)

*Throws*: Any exception thrown by the copy constructor of RandomAccessIterator1,
or by the default constructor, copy constructor, or the copy assignment operator of the value type of RandomAccessIterator1,
or the copy constructor or operator() of BinaryPredicate or Hash[.](#bm-4.sentence-1)

May throw bad_alloc if additional memory needed for internal data structures cannot be allocated[.](#bm-4.sentence-2)

[ð](#lib:operator(),boyer_moore_searcher)

`template<class RandomAccessIterator2>
  pair<RandomAccessIterator2, RandomAccessIterator2>
    operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
`

[5](#bm-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15436)

*Mandates*: RandomAccessIterator1 and RandomAccessIterator2 have the same value type[.](#bm-5.sentence-1)

[6](#bm-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15441)

*Effects*: Finds a subsequence of equal values in a sequence[.](#bm-6.sentence-1)

[7](#bm-7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15445)

*Returns*: A pair of iterators i and j such that

- [(7.1)](#bm-7.1)

i is the first iterator
in the range [first, last - (pat_last_ - pat_first_)) such that
for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds:pred(*(i + n), *(pat_first_ + n)) != false, and

- [(7.2)](#bm-7.2)

j == next(i, distance(pat_first_, pat_last_))[.](#bm-7.sentence-1)

Returns make_pair(first, first) if [pat_first_, pat_last_) is empty,
otherwise returns make_pair(last, last) if no such iterator is found[.](#bm-7.sentence-2)

[8](#bm-8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15459)

*Complexity*: At most (last - first) * (pat_last_ - pat_first_) applications of the predicate[.](#bm-8.sentence-1)

#### [22.10.18.4](#bmh) Class template boyer_moore_horspool_searcher [[func.search.bmh]](func.search.bmh)

[ð](#lib:boyer_moore_horspool_searcher)

namespace std {template<class RandomAccessIterator1, class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>, class BinaryPredicate = equal_to<>>class boyer_moore_horspool_searcher {public: boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
 RandomAccessIterator1 pat_last,
 Hash hf = Hash(),
 BinaryPredicate pred = BinaryPredicate()); template<class RandomAccessIterator2> pair<RandomAccessIterator2, RandomAccessIterator2>operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; private: RandomAccessIterator1 pat_first_; // *exposition only* RandomAccessIterator1 pat_last_; // *exposition only* Hash hash_; // *exposition only* BinaryPredicate pred_; // *exposition only*};}

[ð](#lib:boyer_moore_horspool_searcher,constructor)

`boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                              RandomAccessIterator1 pat_last,
                              Hash hf = Hash(),
                              BinaryPredicate pred = BinaryPredicate());
`

[1](#bmh-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15501)

*Preconditions*: The value type of RandomAccessIterator1 meets the [*Cpp17DefaultConstructible*](utility.arg.requirements#:Cpp17DefaultConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]"),[*Cpp17CopyConstructible*](utility.arg.requirements#:Cpp17CopyConstructible "16.4.4.2 Template argument requirements [utility.arg.requirements]"), and [*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements[.](#bmh-1.sentence-1)

[2](#bmh-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15506)

Let V be iterator_traits<RandomAccessIterator1>​::​value_type[.](#bmh-2.sentence-1)

For any two values A and B of type V,
if pred(A, B) == true, then hf(A) == hf(B) is true[.](#bmh-2.sentence-2)

[3](#bmh-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15511)

*Effects*: Initializespat_first_ with pat_first,pat_last_ with pat_last,hash_ with hf, andpred_ with pred[.](#bmh-3.sentence-1)

[4](#bmh-4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15520)

*Throws*: Any exception thrown by the copy constructor of RandomAccessIterator1,
or by the default constructor, copy constructor, or the copy assignment operator of the value type of RandomAccessIterator1,
or the copy constructor or operator() of BinaryPredicate or Hash[.](#bmh-4.sentence-1)

May throw bad_alloc if additional memory needed for internal data structures cannot be allocated[.](#bmh-4.sentence-2)

[ð](#lib:operator(),boyer_moore_horspool_searcher)

`template<class RandomAccessIterator2>
  pair<RandomAccessIterator2, RandomAccessIterator2>
    operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
`

[5](#bmh-5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15536)

*Mandates*: RandomAccessIterator1 and RandomAccessIterator2 have the same value type[.](#bmh-5.sentence-1)

[6](#bmh-6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15541)

*Effects*: Finds a subsequence of equal values in a sequence[.](#bmh-6.sentence-1)

[7](#bmh-7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15545)

*Returns*: A pair of iterators i and j such that

- [(7.1)](#bmh-7.1)

i is the first iterator in the range
[first, last - (pat_last_ - pat_first_)) such that
for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds:pred(*(i + n), *(pat_first_ + n)) != false, and

- [(7.2)](#bmh-7.2)

j == next(i, distance(pat_first_, pat_last_))[.](#bmh-7.sentence-1)

Returns make_pair(first, first) if [pat_first_, pat_last_) is empty,
otherwise returns make_pair(last, last) if no such iterator is found[.](#bmh-7.sentence-2)

[8](#bmh-8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15559)

*Complexity*: At most (last - first) * (pat_last_ - pat_first_) applications of the predicate[.](#bmh-8.sentence-1)
