From Jason Turner

[func.search]

C++14 → C++17 9.3 KB 232 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpp5f332qw/{from.md → to.md} +229 -0
tmp/tmpp5f332qw/{from.md → to.md} RENAMED
@@ -0,0 +1,229 @@
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ ### Searchers <a id="func.search">[[func.search]]</a>
2
+
3
+ This subclause provides function object types ([[function.objects]])
4
+ for operations that search for a sequence \[`pat``first`, `pat_last`) in
5
+ another sequence \[`first`, `last`) that is provided to the object’s
6
+ function call operator. The first sequence (the pattern to be searched
7
+ for) is provided to the object’s constructor, and the second (the
8
+ sequence to be searched) is provided to the function call operator.
9
+
10
+ Each specialization of a class template specified in this subclause
11
+ [[func.search]] shall meet the `CopyConstructible` and `CopyAssignable`
12
+ requirements. Template parameters named
13
+
14
+ - `ForwardIterator`,
15
+ - `ForwardIterator1`,
16
+ - `ForwardIterator2`,
17
+ - `RandomAccessIterator`,
18
+ - `RandomAccessIterator1`,
19
+ - `RandomAccessIterator2`, and
20
+ - `BinaryPredicate`
21
+
22
+ of templates specified in this subclause [[func.search]] shall meet the
23
+ same requirements and semantics as specified in [[algorithms.general]].
24
+ Template parameters named `Hash` shall meet the requirements as
25
+ specified in [[hash.requirements]].
26
+
27
+ The Boyer-Moore searcher implements the Boyer-Moore search algorithm.
28
+ The Boyer-Moore-Horspool searcher implements the Boyer-Moore-Horspool
29
+ search algorithm. In general, the Boyer-Moore searcher will use more
30
+ memory and give better runtime performance than Boyer-Moore-Horspool.
31
+
32
+ #### Class template `default_searcher` <a id="func.search.default">[[func.search.default]]</a>
33
+
34
+ ``` cpp
35
+ template <class ForwardIterator1, class BinaryPredicate = equal_to<>>
36
+ class default_searcher {
37
+ public:
38
+ default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
39
+ BinaryPredicate pred = BinaryPredicate());
40
+
41
+ template <class ForwardIterator2>
42
+ pair<ForwardIterator2, ForwardIterator2>
43
+ operator()(ForwardIterator2 first, ForwardIterator2 last) const;
44
+
45
+ private:
46
+ ForwardIterator1 pat_first_; // exposition only
47
+ ForwardIterator1 pat_last_; // exposition only
48
+ BinaryPredicate pred_; // exposition only
49
+ };
50
+ ```
51
+
52
+ ``` cpp
53
+ default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
54
+ BinaryPredicate pred = BinaryPredicate());
55
+ ```
56
+
57
+ *Effects:* Constructs a `default_searcher` object, initializing
58
+ `pat_first_` with `pat_first`, \texttt{pat_last\_} with `pat_last`, and
59
+ `pred_` with `pred`.
60
+
61
+ *Throws:* Any exception thrown by the copy constructor of
62
+ `BinaryPredicate` or `ForwardIterator1`.
63
+
64
+ ``` cpp
65
+ template<class ForwardIterator2>
66
+ pair<ForwardIterator2, ForwardIterator2>
67
+ operator()(ForwardIterator2 first, ForwardIterator2 last) const;
68
+ ```
69
+
70
+ *Effects:* Returns a pair of iterators `i` and `j` such that
71
+
72
+ - `i == search(first, last, pat_first_, pat_last_, pred_)`, and
73
+ - if `i == last`, then `j == last`, otherwise
74
+ `j == next(i, distance(pat_first_, pat_last_))`.
75
+
76
+ #### Class template `boyer_moore_searcher` <a id="func.search.bm">[[func.search.bm]]</a>
77
+
78
+ ``` cpp
79
+ template <class RandomAccessIterator1,
80
+ class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
81
+ class BinaryPredicate = equal_to<>>
82
+ class boyer_moore_searcher {
83
+ public:
84
+ boyer_moore_searcher(RandomAccessIterator1 pat_first,
85
+ RandomAccessIterator1 pat_last,
86
+ Hash hf = Hash(),
87
+ BinaryPredicate pred = BinaryPredicate());
88
+
89
+ template <class RandomAccessIterator2>
90
+ pair<RandomAccessIterator2, RandomAccessIterator2>
91
+ operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
92
+
93
+ private:
94
+ RandomAccessIterator1 pat_first_; // exposition only
95
+ RandomAccessIterator1 pat_last_; // exposition only
96
+ Hash hash_; // exposition only
97
+ BinaryPredicate pred_; // exposition only
98
+ };
99
+ ```
100
+
101
+ ``` cpp
102
+ boyer_moore_searcher(RandomAccessIterator1 pat_first,
103
+ RandomAccessIterator1 pat_last,
104
+ Hash hf = Hash(),
105
+ BinaryPredicate pred = BinaryPredicate());
106
+ ```
107
+
108
+ *Requires:* The value type of `RandomAccessIterator1` shall meet the
109
+ `DefaultConstructible` requirements, the `CopyConstructible`
110
+ requirements, and the `CopyAssignable` requirements.
111
+
112
+ *Requires:* For any two values `A` and `B` of the type
113
+ `iterator_traits<RandomAccessIterator1>::value_type`, if
114
+ `pred(A, B) == true`, then `hf(A) == hf(B)` shall be `true`.
115
+
116
+ *Effects:* Constructs a `boyer_moore_searcher` object, initializing
117
+ `pat_first_` with `pat_first`, `pat_last_` with `pat_last`, `hash_` with
118
+ `hf`, and `pred_` with `pred`.
119
+
120
+ *Throws:* Any exception thrown by the copy constructor of
121
+ `RandomAccessIterator1`, or by the default constructor, copy
122
+ constructor, or the copy assignment operator of the value type of
123
+ `RandomAccessIterator1`, or the copy constructor or `operator()` of
124
+ `BinaryPredicate` or `Hash`. May throw `bad_alloc` if additional memory
125
+ needed for internal data structures cannot be allocated.
126
+
127
+ ``` cpp
128
+ template <class RandomAccessIterator2>
129
+ pair<RandomAccessIterator2, RandomAccessIterator2>
130
+ operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
131
+ ```
132
+
133
+ *Requires:* `RandomAccessIterator1` and `RandomAccessIterator2` shall
134
+ have the same value type.
135
+
136
+ *Effects:* Finds a subsequence of equal values in a sequence.
137
+
138
+ *Returns:* A pair of iterators `i` and `j` such that
139
+
140
+ - `i` is the first iterator in the range \[`first`,
141
+ `last - (pat_last_ - pat_first_)`) such that for every non-negative
142
+ integer `n` less than `pat_last_ - pat_first_` the following condition
143
+ holds: `pred(*(i + n), *(pat_first_ + n)) != false`, and
144
+ - `j == next(i, distance(pat_first_, pat_last_))`.
145
+
146
+ Returns `make_pair(first, first)` if \[`pat_first_`, `pat_last_`) is
147
+ empty, otherwise returns `make_pair(last, last)` if no such iterator is
148
+ found.
149
+
150
+ *Complexity:* At most `(last - first) * (pat_last_ - pat_first_)`
151
+ applications of the predicate.
152
+
153
+ #### Class template `boyer_moore_horspool_searcher` <a id="func.search.bmh">[[func.search.bmh]]</a>
154
+
155
+ ``` cpp
156
+ template <class RandomAccessIterator1,
157
+ class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
158
+ class BinaryPredicate = equal_to<>>
159
+ class boyer_moore_horspool_searcher {
160
+ public:
161
+ boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
162
+ RandomAccessIterator1 pat_last,
163
+ Hash hf = Hash(),
164
+ BinaryPredicate pred = BinaryPredicate());
165
+
166
+ template <class RandomAccessIterator2>
167
+ pair<RandomAccessIterator2, RandomAccessIterator2>
168
+ operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
169
+
170
+ private:
171
+ RandomAccessIterator1 pat_first_; // exposition only
172
+ RandomAccessIterator1 pat_last_; // exposition only
173
+ Hash hash_; // exposition only
174
+ BinaryPredicate pred_; // exposition only
175
+ };
176
+ ```
177
+
178
+ ``` cpp
179
+ boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
180
+ RandomAccessIterator1 pat_last,
181
+ Hash hf = Hash(),
182
+ BinaryPredicate pred = BinaryPredicate());
183
+ ```
184
+
185
+ *Requires:* The value type of `RandomAccessIterator1` shall meet the
186
+ `DefaultConstructible`, `CopyConstructible`, and `CopyAssignable`
187
+ requirements.
188
+
189
+ *Requires:* For any two values `A` and `B` of the type
190
+ `iterator_traits<RandomAccessIterator1>::value_type`, if
191
+ `pred(A, B) == true`, then `hf(A) == hf(B)` shall be `true`.
192
+
193
+ *Effects:* Constructs a `boyer_moore_horspool_searcher` object,
194
+ initializing `pat_first_` with `pat_first`, `pat_last_` with `pat_last`,
195
+ `hash_` with `hf`, and `pred_` with `pred`.
196
+
197
+ *Throws:* Any exception thrown by the copy constructor of
198
+ `RandomAccessIterator1`, or by the default constructor, copy
199
+ constructor, or the copy assignment operator of the value type of
200
+ `RandomAccessIterator1` or the copy constructor or `operator()` of
201
+ `BinaryPredicate` or `Hash`. May throw `bad_alloc` if additional memory
202
+ needed for internal data structures cannot be allocated.
203
+
204
+ ``` cpp
205
+ template <class RandomAccessIterator2>
206
+ pair<RandomAccessIterator2, RandomAccessIterator2>
207
+ operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
208
+ ```
209
+
210
+ *Requires:* `RandomAccessIterator1` and `RandomAccessIterator2` shall
211
+ have the same value type.
212
+
213
+ *Effects:* Finds a subsequence of equal values in a sequence.
214
+
215
+ *Returns:* A pair of iterators `i` and `j` such that
216
+
217
+ - `i` is the first iterator `i` in the range \[`first`,
218
+ `last - (pat_last_ - pat_first_)`) such that for every non-negative
219
+ integer `n` less than `pat_last_ - pat_first_` the following condition
220
+ holds: `pred(*(i + n), *(pat_first_ + n)) != false`, and
221
+ - `j == next(i, distance(pat_first_, pat_last_))`.
222
+
223
+ Returns `make_pair(first, first)` if \[`pat_first_`, `pat_last_`) is
224
+ empty, otherwise returns `make_pair(last, last)` if no such iterator is
225
+ found.
226
+
227
+ *Complexity:* At most `(last - first) * (pat_last_ - pat_first_)`
228
+ applications of the predicate.
229
+