101 lines
4.5 KiB
Markdown
101 lines
4.5 KiB
Markdown
[func.search.bm]
|
||
|
||
# 22 General utilities library [[utilities]](./#utilities)
|
||
|
||
## 22.10 Function objects [[function.objects]](function.objects#func.search.bm)
|
||
|
||
### 22.10.18 Searchers [[func.search]](func.search#bm)
|
||
|
||
#### 22.10.18.3 Class template boyer_moore_searcher [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](#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[.](#1.sentence-1)
|
||
|
||
[2](#2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15406)
|
||
|
||
Let V be iterator_traits<RandomAccessIterator1>::value_type[.](#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[.](#2.sentence-2)
|
||
|
||
[3](#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[.](#3.sentence-1)
|
||
|
||
[4](#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[.](#4.sentence-1)
|
||
|
||
May throw bad_alloc if additional memory needed for internal data structures cannot be allocated[.](#4.sentence-2)
|
||
|
||
[ð](#lib:operator(),boyer_moore_searcher)
|
||
|
||
`template<class RandomAccessIterator2>
|
||
pair<RandomAccessIterator2, RandomAccessIterator2>
|
||
operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
|
||
`
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15436)
|
||
|
||
*Mandates*: RandomAccessIterator1 and RandomAccessIterator2 have the same value type[.](#5.sentence-1)
|
||
|
||
[6](#6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15441)
|
||
|
||
*Effects*: Finds a subsequence of equal values in a sequence[.](#6.sentence-1)
|
||
|
||
[7](#7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/utilities.tex#L15445)
|
||
|
||
*Returns*: A pair of iterators i and j such that
|
||
|
||
- [(7.1)](#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)](#7.2)
|
||
|
||
j == next(i, distance(pat_first_, pat_last_))[.](#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[.](#7.sentence-2)
|
||
|
||
[8](#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[.](#8.sentence-1)
|