308 lines
14 KiB
Markdown
308 lines
14 KiB
Markdown
[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)
|