From Jason Turner

[func.search]

C++20 → C++23 8.2 KB 70 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpih1zu9no/{from.md → to.md} +33 -26
tmp/tmpih1zu9no/{from.md → to.md} RENAMED
@@ -1,28 +1,31 @@
1
  ### Searchers <a id="func.search">[[func.search]]</a>
2
 
3
- This subclause provides function object types [[function.objects]] for
4
- 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 *Cpp17CopyConstructible* and
12
- *Cpp17CopyAssignable* 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 *Cpp17Hash* requirements
25
  ([[cpp17.hash]]).
26
 
27
  The Boyer-Moore searcher implements the Boyer-Moore search algorithm.
28
  The Boyer-Moore-Horspool searcher implements the Boyer-Moore-Horspool
@@ -30,10 +33,11 @@ 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
  constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
39
  BinaryPredicate pred = BinaryPredicate());
@@ -45,14 +49,15 @@ template<class ForwardIterator1, class BinaryPredicate = equal_to<>>
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
- constexpr 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
@@ -74,10 +79,11 @@ template<class ForwardIterator2>
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:
@@ -94,30 +100,30 @@ template<class RandomAccessIterator1,
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
  *Preconditions:* The value type of `RandomAccessIterator1` meets the
109
- *Cpp17DefaultConstructible* requirements, the *Cpp17CopyConstructible*
110
- requirements, and the *Cpp17CopyAssignable* requirements.
111
 
112
- *Preconditions:* Let `V` be
113
- `iterator_traits<RandomAccessIterator1>::value_type`. For any two values
114
- `A` and `B` of type `V`, if `pred(A, B) == true`, then `hf(A) == hf(B)`
115
- is `true`.
116
 
117
  *Effects:* Initializes `pat_first_` with `pat_first`, `pat_last_` with
118
- `pat_last`, `hash_` with `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
@@ -151,10 +157,11 @@ found.
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:
@@ -171,10 +178,11 @@ template<class RandomAccessIterator1,
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,
@@ -184,22 +192,21 @@ boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
184
 
185
  *Preconditions:* The value type of `RandomAccessIterator1` meets the
186
  *Cpp17DefaultConstructible*, *Cpp17CopyConstructible*, and
187
  *Cpp17CopyAssignable* requirements.
188
 
189
- *Preconditions:* Let `V` be
190
- `iterator_traits<RandomAccessIterator1>::value_type`. For any two values
191
- `A` and `B` of type `V`, if `pred(A, B) == true`, then `hf(A) == hf(B)`
192
- is `true`.
193
 
194
  *Effects:* Initializes `pat_first_` with `pat_first`, `pat_last_` with
195
- `pat_last`, `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>
@@ -212,11 +219,11 @@ 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
 
 
1
  ### Searchers <a id="func.search">[[func.search]]</a>
2
 
3
+ #### General <a id="func.search.general">[[func.search.general]]</a>
 
 
 
 
 
4
 
5
+ Subclause [[func.search]] provides function object types
6
+ [[function.objects]] for operations that search for a sequence
7
+ \[`pat``first`, `pat_last`) in another sequence \[`first`, `last`) that
8
+ is provided to the object’s function call operator. The first sequence
9
+ (the pattern to be searched for) is provided to the object’s
10
+ constructor, and the second (the sequence to be searched) is provided to
11
+ the function call operator.
12
+
13
+ Each specialization of a class template specified in [[func.search]]
14
+ shall meet the *Cpp17CopyConstructible* and *Cpp17CopyAssignable*
15
+ requirements. Template parameters named
16
 
17
  - `ForwardIterator`,
18
  - `ForwardIterator1`,
19
  - `ForwardIterator2`,
20
  - `RandomAccessIterator`,
21
  - `RandomAccessIterator1`,
22
  - `RandomAccessIterator2`, and
23
  - `BinaryPredicate`
24
 
25
+ of templates specified in [[func.search]] shall meet the same
26
+ requirements and semantics as specified in [[algorithms.general]].
27
  Template parameters named `Hash` shall meet the *Cpp17Hash* requirements
28
  ([[cpp17.hash]]).
29
 
30
  The Boyer-Moore searcher implements the Boyer-Moore search algorithm.
31
  The Boyer-Moore-Horspool searcher implements the Boyer-Moore-Horspool
 
33
  memory and give better runtime performance than Boyer-Moore-Horspool.
34
 
35
  #### Class template `default_searcher` <a id="func.search.default">[[func.search.default]]</a>
36
 
37
  ``` cpp
38
+ namespace std {
39
  template<class ForwardIterator1, class BinaryPredicate = equal_to<>>
40
  class default_searcher {
41
  public:
42
  constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
43
  BinaryPredicate pred = BinaryPredicate());
 
49
  private:
50
  ForwardIterator1 pat_first_; // exposition only
51
  ForwardIterator1 pat_last_; // exposition only
52
  BinaryPredicate pred_; // exposition only
53
  };
54
+ }
55
  ```
56
 
57
  ``` cpp
58
+ constexpr default_searcher(ForwardIterator1 pat_first, ForwardIterator1 pat_last,
59
  BinaryPredicate pred = BinaryPredicate());
60
  ```
61
 
62
  *Effects:* Constructs a `default_searcher` object, initializing
63
  `pat_first_` with `pat_first`, \texttt{pat_last\_} with `pat_last`, and
 
79
  `j == next(i, distance(pat_first_, pat_last_))`.
80
 
81
  #### Class template `boyer_moore_searcher` <a id="func.search.bm">[[func.search.bm]]</a>
82
 
83
  ``` cpp
84
+ namespace std {
85
  template<class RandomAccessIterator1,
86
  class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
87
  class BinaryPredicate = equal_to<>>
88
  class boyer_moore_searcher {
89
  public:
 
100
  RandomAccessIterator1 pat_first_; // exposition only
101
  RandomAccessIterator1 pat_last_; // exposition only
102
  Hash hash_; // exposition only
103
  BinaryPredicate pred_; // exposition only
104
  };
105
+ }
106
  ```
107
 
108
  ``` cpp
109
  boyer_moore_searcher(RandomAccessIterator1 pat_first,
110
  RandomAccessIterator1 pat_last,
111
  Hash hf = Hash(),
112
  BinaryPredicate pred = BinaryPredicate());
113
  ```
114
 
115
  *Preconditions:* The value type of `RandomAccessIterator1` meets the
116
+ *Cpp17DefaultConstructible*, the *Cpp17CopyConstructible*, and the
117
+ *Cpp17CopyAssignable* requirements.
118
 
119
+ Let `V` be `iterator_traits<RandomAccessIterator1>::value_type`. For any
120
+ two values `A` and `B` of type `V`, if `pred(A, B) == true`, then
121
+ `hf(A) == hf(B)` is `true`.
 
122
 
123
  *Effects:* Initializes `pat_first_` with `pat_first`, `pat_last_` with
124
+ `pat_last`, `hash_` with `hf`, and \texttt{pred\_} with `pred`.
125
 
126
  *Throws:* Any exception thrown by the copy constructor of
127
  `RandomAccessIterator1`, or by the default constructor, copy
128
  constructor, or the copy assignment operator of the value type of
129
  `RandomAccessIterator1`, or the copy constructor or `operator()` of
 
157
  applications of the predicate.
158
 
159
  #### Class template `boyer_moore_horspool_searcher` <a id="func.search.bmh">[[func.search.bmh]]</a>
160
 
161
  ``` cpp
162
+ namespace std {
163
  template<class RandomAccessIterator1,
164
  class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
165
  class BinaryPredicate = equal_to<>>
166
  class boyer_moore_horspool_searcher {
167
  public:
 
178
  RandomAccessIterator1 pat_first_; // exposition only
179
  RandomAccessIterator1 pat_last_; // exposition only
180
  Hash hash_; // exposition only
181
  BinaryPredicate pred_; // exposition only
182
  };
183
+ }
184
  ```
185
 
186
  ``` cpp
187
  boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
188
  RandomAccessIterator1 pat_last,
 
192
 
193
  *Preconditions:* The value type of `RandomAccessIterator1` meets the
194
  *Cpp17DefaultConstructible*, *Cpp17CopyConstructible*, and
195
  *Cpp17CopyAssignable* requirements.
196
 
197
+ Let `V` be `iterator_traits<RandomAccessIterator1>::value_type`. For any
198
+ two values `A` and `B` of type `V`, if `pred(A, B) == true`, then
199
+ `hf(A) == hf(B)` is `true`.
 
200
 
201
  *Effects:* Initializes `pat_first_` with `pat_first`, `pat_last_` with
202
+ `pat_last`, `hash_` with `hf`, and \texttt{pred\_} with `pred`.
203
 
204
  *Throws:* Any exception thrown by the copy constructor of
205
  `RandomAccessIterator1`, or by the default constructor, copy
206
  constructor, or the copy assignment operator of the value type of
207
+ `RandomAccessIterator1`, or the copy constructor or `operator()` of
208
  `BinaryPredicate` or `Hash`. May throw `bad_alloc` if additional memory
209
  needed for internal data structures cannot be allocated.
210
 
211
  ``` cpp
212
  template<class RandomAccessIterator2>
 
219
 
220
  *Effects:* Finds a subsequence of equal values in a sequence.
221
 
222
  *Returns:* A pair of iterators `i` and `j` such that
223
 
224
+ - `i` is the first iterator in the range \[`first`,
225
  `last - (pat_last_ - pat_first_)`) such that for every non-negative
226
  integer `n` less than `pat_last_ - pat_first_` the following condition
227
  holds: `pred(*(i + n), *(pat_first_ + n)) != false`, and
228
  - `j == next(i, distance(pat_first_, pat_last_))`.
229