From Jason Turner

[func.search]

C++17 → C++20 7.8 KB 74 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpw2r9gl4q/{from.md → to.md} +32 -32
tmp/tmpw2r9gl4q/{from.md → to.md} RENAMED
@@ -1,17 +1,17 @@
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`,
@@ -19,12 +19,12 @@ requirements. Template parameters named
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.
@@ -33,26 +33,26 @@ memory and give better runtime performance than Boyer-Moore-Horspool.
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
@@ -61,11 +61,11 @@ default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
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
 
@@ -103,21 +103,21 @@ 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
@@ -128,12 +128,12 @@ needed for internal data structures cannot be allocated.
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
 
@@ -180,21 +180,21 @@ 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
@@ -205,12 +205,12 @@ needed for internal data structures cannot be allocated.
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
 
 
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`,
 
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
29
  search algorithm. In general, the Boyer-Moore searcher will use more
30
  memory and give better runtime performance than Boyer-Moore-Horspool.
 
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());
40
 
41
  template<class ForwardIterator2>
42
+ constexpr 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
+ 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
 
61
  *Throws:* Any exception thrown by the copy constructor of
62
  `BinaryPredicate` or `ForwardIterator1`.
63
 
64
  ``` cpp
65
  template<class ForwardIterator2>
66
+ constexpr 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
 
 
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
 
128
  template<class RandomAccessIterator2>
129
  pair<RandomAccessIterator2, RandomAccessIterator2>
130
  operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
131
  ```
132
 
133
+ *Mandates:* `RandomAccessIterator1` and `RandomAccessIterator2` have the
134
+ 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
 
 
180
  RandomAccessIterator1 pat_last,
181
  Hash hf = Hash(),
182
  BinaryPredicate pred = BinaryPredicate());
183
  ```
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
 
205
  template<class RandomAccessIterator2>
206
  pair<RandomAccessIterator2, RandomAccessIterator2>
207
  operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
208
  ```
209
 
210
+ *Mandates:* `RandomAccessIterator1` and `RandomAccessIterator2` have the
211
+ 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