From Jason Turner

[alg.min.max]

C++17 → C++20 14.6 KB 226 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/tmpohb8638v/{from.md → to.md} +161 -59
tmp/tmpohb8638v/{from.md → to.md} RENAMED
@@ -1,107 +1,170 @@
1
  ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
2
 
3
  ``` cpp
4
- template<class T> constexpr const T& min(const T& a, const T& b);
 
5
  template<class T, class Compare>
6
  constexpr const T& min(const T& a, const T& b, Compare comp);
 
 
 
 
7
  ```
8
 
9
- *Requires:* For the first form, type `T` shall be `LessThanComparable`
10
- (Table  [[tab:lessthancomparable]]).
11
 
12
  *Returns:* The smaller value.
13
 
14
  *Remarks:* Returns the first argument when the arguments are equivalent.
 
 
15
 
16
- *Complexity:* Exactly one comparison.
 
17
 
18
  ``` cpp
19
  template<class T>
20
- constexpr T min(initializer_list<T> t);
21
  template<class T, class Compare>
22
- constexpr T min(initializer_list<T> t, Compare comp);
 
 
 
 
 
 
 
 
 
23
  ```
24
 
25
- *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
26
- first form, type `T` shall be `LessThanComparable`.
 
 
27
 
28
- *Returns:* The smallest value in the initializer_list.
29
 
30
- *Remarks:* Returns a copy of the leftmost argument when several
31
- arguments are equivalent to the smallest. 
 
 
32
 
33
- *Complexity:* Exactly `t.size() - 1` comparisons.
 
34
 
35
  ``` cpp
36
- template<class T> constexpr const T& max(const T& a, const T& b);
 
37
  template<class T, class Compare>
38
  constexpr const T& max(const T& a, const T& b, Compare comp);
 
 
 
 
39
  ```
40
 
41
- *Requires:* For the first form, type `T` shall be `LessThanComparable`
42
- (Table  [[tab:lessthancomparable]]).
43
 
44
  *Returns:* The larger value.
45
 
46
  *Remarks:* Returns the first argument when the arguments are equivalent.
 
 
47
 
48
- *Complexity:* Exactly one comparison.
 
49
 
50
  ``` cpp
51
  template<class T>
52
- constexpr T max(initializer_list<T> t);
53
  template<class T, class Compare>
54
- constexpr T max(initializer_list<T> t, Compare comp);
 
 
 
 
 
 
 
 
 
55
  ```
56
 
57
- *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
58
- first form, type `T` shall be `LessThanComparable`.
 
 
59
 
60
- *Returns:* The largest value in the initializer_list.
61
 
62
- *Remarks:* Returns a copy of the leftmost argument when several
63
- arguments are equivalent to the largest.
 
 
64
 
65
- *Complexity:* Exactly `t.size() - 1` comparisons.
 
66
 
67
  ``` cpp
68
- template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
 
69
  template<class T, class Compare>
70
  constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
 
 
 
 
 
71
  ```
72
 
73
- *Requires:* For the first form, type `T` shall be `LessThanComparable`
74
- (Table  [[tab:lessthancomparable]]).
75
 
76
- *Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
77
- and `pair<const T&, const T&>(a, b)` otherwise.
78
 
79
- *Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
80
- are equivalent.
81
 
82
- *Complexity:* Exactly one comparison.
 
83
 
84
  ``` cpp
85
  template<class T>
86
  constexpr pair<T, T> minmax(initializer_list<T> t);
87
  template<class T, class Compare>
88
  constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
 
 
 
 
 
 
 
 
 
 
89
  ```
90
 
91
- *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
92
- first form, type `T` shall be `LessThanComparable`.
 
 
93
 
94
- *Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
95
- the largest value in the initializer list.
 
96
 
97
- *Remarks:* `x` is a copy of the leftmost argument when several arguments
98
- are equivalent to the smallest. `y` is a copy of the rightmost argument
99
- when several arguments are equivalent to the largest.
100
 
101
- *Complexity:* At most (3/2)`t.size()` applications of the corresponding
102
- predicate.
 
103
 
104
  ``` cpp
105
  template<class ForwardIterator>
106
  constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
107
 
@@ -114,19 +177,34 @@ template<class ForwardIterator, class Compare>
114
  Compare comp);
115
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
116
  ForwardIterator min_element(ExecutionPolicy&& exec,
117
  ForwardIterator first, ForwardIterator last,
118
  Compare comp);
 
 
 
 
 
 
 
 
119
  ```
120
 
 
 
 
121
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
122
- that for every iterator `j` in the range \[`first`, `last`) the
123
- following corresponding conditions hold: `!(*j < *i)` or
124
- `comp(*j, *i) == false`. Returns `last` if `first == last`.
125
 
126
- *Complexity:* Exactly max(`last - first - 1`, 0) applications of the
127
- corresponding comparisons.
 
 
 
 
 
 
128
 
129
  ``` cpp
130
  template<class ForwardIterator>
131
  constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
132
  template<class ExecutionPolicy, class ForwardIterator>
@@ -138,19 +216,34 @@ template<class ForwardIterator, class Compare>
138
  Compare comp);
139
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
140
  ForwardIterator max_element(ExecutionPolicy&& exec,
141
  ForwardIterator first, ForwardIterator last,
142
  Compare comp);
 
 
 
 
 
 
 
 
143
  ```
144
 
 
 
 
145
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
146
- that for every iterator `j` in the range \[`first`, `last`) the
147
- following corresponding conditions hold: `!(*i < *j)` or
148
- `comp(*i, *j) == false`. Returns `last` if `first == last`.
149
 
150
- *Complexity:* Exactly max(`last - first - 1`, 0) applications of the
151
- corresponding comparisons.
 
 
 
 
 
 
152
 
153
  ``` cpp
154
  template<class ForwardIterator>
155
  constexpr pair<ForwardIterator, ForwardIterator>
156
  minmax_element(ForwardIterator first, ForwardIterator last);
@@ -164,17 +257,26 @@ template<class ForwardIterator, class Compare>
164
  minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
165
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
166
  pair<ForwardIterator, ForwardIterator>
167
  minmax_element(ExecutionPolicy&& exec,
168
  ForwardIterator first, ForwardIterator last, Compare comp);
 
 
 
 
 
 
 
 
 
169
  ```
170
 
171
- *Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
172
- otherwise `make_pair(m, M)`, where `m` is the first iterator in
173
- \[`first`, `last`) such that no iterator in the range refers to a
174
- smaller element, and where `M` is the last iterator[^5] in \[`first`,
175
- `last`) such that no iterator in the range refers to a larger element.
176
 
177
- *Complexity:* At most
178
- $\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ applications of
179
- the corresponding predicate, where N is `last - first`.
180
 
 
1
  ### Minimum and maximum <a id="alg.min.max">[[alg.min.max]]</a>
2
 
3
  ``` cpp
4
+ template<class T>
5
+ constexpr const T& min(const T& a, const T& b);
6
  template<class T, class Compare>
7
  constexpr const T& min(const T& a, const T& b, Compare comp);
8
+
9
+ template<class T, class Proj = identity,
10
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
11
+ constexpr const T& ranges::min(const T& a, const T& b, Comp comp = {}, Proj proj = {});
12
  ```
13
 
14
+ *Preconditions:* For the first form, `T` meets the
15
+ *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
16
 
17
  *Returns:* The smaller value.
18
 
19
  *Remarks:* Returns the first argument when the arguments are equivalent.
20
+ An invocation may explicitly specify an argument for the template
21
+ parameter `T` of the overloads in namespace `std`.
22
 
23
+ *Complexity:* Exactly one comparison and two applications of the
24
+ projection, if any.
25
 
26
  ``` cpp
27
  template<class T>
28
+ constexpr T min(initializer_list<T> r);
29
  template<class T, class Compare>
30
+ constexpr T min(initializer_list<T> r, Compare comp);
31
+
32
+ template<copyable T, class Proj = identity,
33
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
34
+ constexpr T ranges::min(initializer_list<T> r, Comp comp = {}, Proj proj = {});
35
+ template<input_range R, class Proj = identity,
36
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
37
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
38
+ constexpr range_value_t<R>
39
+ ranges::min(R&& r, Comp comp = {}, Proj proj = {});
40
  ```
41
 
42
+ *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
43
+ namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
44
+ For the first form, `T` meets the *Cpp17LessThanComparable* requirements
45
+ ([[cpp17.lessthancomparable]]).
46
 
47
+ *Returns:* The smallest value in the input range.
48
 
49
+ *Remarks:* Returns a copy of the leftmost element when several elements
50
+ are equivalent to the smallest. An invocation may explicitly specify an
51
+ argument for the template parameter `T` of the overloads in namespace
52
+ `std`.
53
 
54
+ *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
55
+ many applications of the projection, if any.
56
 
57
  ``` cpp
58
+ template<class T>
59
+ constexpr const T& max(const T& a, const T& b);
60
  template<class T, class Compare>
61
  constexpr const T& max(const T& a, const T& b, Compare comp);
62
+
63
+ template<class T, class Proj = identity,
64
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
65
+ constexpr const T& ranges::max(const T& a, const T& b, Comp comp = {}, Proj proj = {});
66
  ```
67
 
68
+ *Preconditions:* For the first form, `T` meets the
69
+ *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
70
 
71
  *Returns:* The larger value.
72
 
73
  *Remarks:* Returns the first argument when the arguments are equivalent.
74
+ An invocation may explicitly specify an argument for the template
75
+ parameter `T` of the overloads in namespace `std`.
76
 
77
+ *Complexity:* Exactly one comparison and two applications of the
78
+ projection, if any.
79
 
80
  ``` cpp
81
  template<class T>
82
+ constexpr T max(initializer_list<T> r);
83
  template<class T, class Compare>
84
+ constexpr T max(initializer_list<T> r, Compare comp);
85
+
86
+ template<copyable T, class Proj = identity,
87
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
88
+ constexpr T ranges::max(initializer_list<T> r, Comp comp = {}, Proj proj = {});
89
+ template<input_range R, class Proj = identity,
90
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
91
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
92
+ constexpr range_value_t<R>
93
+ ranges::max(R&& r, Comp comp = {}, Proj proj = {});
94
  ```
95
 
96
+ *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
97
+ namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
98
+ For the first form, `T` meets the *Cpp17LessThanComparable* requirements
99
+ ([[cpp17.lessthancomparable]]).
100
 
101
+ *Returns:* The largest value in the input range.
102
 
103
+ *Remarks:* Returns a copy of the leftmost element when several elements
104
+ are equivalent to the largest. An invocation may explicitly specify an
105
+ argument for the template parameter `T` of the overloads in namespace
106
+ `std`.
107
 
108
+ *Complexity:* Exactly `ranges::distance(r) - 1` comparisons and twice as
109
+ many applications of the projection, if any.
110
 
111
  ``` cpp
112
+ template<class T>
113
+ constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
114
  template<class T, class Compare>
115
  constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
116
+
117
+ template<class T, class Proj = identity,
118
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
119
+ constexpr ranges::minmax_result<const T&>
120
+ ranges::minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {});
121
  ```
122
 
123
+ *Preconditions:* For the first form, `T` meets the
124
+ *Cpp17LessThanComparable* requirements ([[cpp17.lessthancomparable]]).
125
 
126
+ *Returns:* `{b, a}` if `b` is smaller than `a`, and `{a, b}` otherwise.
 
127
 
128
+ *Remarks:* An invocation may explicitly specify an argument for the
129
+ template parameter `T` of the overloads in namespace `std`.
130
 
131
+ *Complexity:* Exactly one comparison and two applications of the
132
+ projection, if any.
133
 
134
  ``` cpp
135
  template<class T>
136
  constexpr pair<T, T> minmax(initializer_list<T> t);
137
  template<class T, class Compare>
138
  constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
139
+
140
+ template<copyable T, class Proj = identity,
141
+ indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
142
+ constexpr ranges::minmax_result<T>
143
+ ranges::minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {});
144
+ template<input_range R, class Proj = identity,
145
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
146
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
147
+ constexpr ranges::minmax_result<range_value_t<R>>
148
+ ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
149
  ```
150
 
151
+ *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
152
+ namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
153
+ For the first form, type `T` meets the *Cpp17LessThanComparable*
154
+ requirements ([[cpp17.lessthancomparable]]).
155
 
156
+ *Returns:* Let `X` be the return type. Returns `X{x, y}`, where `x` is a
157
+ copy of the leftmost element with the smallest value and `y` a copy of
158
+ the rightmost element with the largest value in the input range.
159
 
160
+ *Remarks:* An invocation may explicitly specify an argument for the
161
+ template parameter `T` of the overloads in namespace `std`.
 
162
 
163
+ *Complexity:* At most (3/2)`ranges::distance(r)` applications of the
164
+ corresponding predicate and twice as many applications of the
165
+ projection, if any.
166
 
167
  ``` cpp
168
  template<class ForwardIterator>
169
  constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
170
 
 
177
  Compare comp);
178
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
179
  ForwardIterator min_element(ExecutionPolicy&& exec,
180
  ForwardIterator first, ForwardIterator last,
181
  Compare comp);
182
+
183
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
184
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
185
+ constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
186
+ template<forward_range R, class Proj = identity,
187
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
188
+ constexpr borrowed_iterator_t<R>
189
+ ranges::min_element(R&& r, Comp comp = {}, Proj proj = {});
190
  ```
191
 
192
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
193
+ no parameters by those names.
194
+
195
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
196
+ that for every iterator `j` in the range \[`first`, `last`),
 
 
197
 
198
+ ``` cpp
199
+ bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))
200
+ ```
201
+
202
+ is `false`. Returns `last` if `first == last`.
203
+
204
+ *Complexity:* Exactly max(`last - first - 1`, 0) comparisons and twice
205
+ as many projections.
206
 
207
  ``` cpp
208
  template<class ForwardIterator>
209
  constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
210
  template<class ExecutionPolicy, class ForwardIterator>
 
216
  Compare comp);
217
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
218
  ForwardIterator max_element(ExecutionPolicy&& exec,
219
  ForwardIterator first, ForwardIterator last,
220
  Compare comp);
221
+
222
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
223
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
224
+ constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {});
225
+ template<forward_range R, class Proj = identity,
226
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
227
+ constexpr borrowed_iterator_t<R>
228
+ ranges::max_element(R&& r, Comp comp = {}, Proj proj = {});
229
  ```
230
 
231
+ Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
232
+ no parameters by those names.
233
+
234
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
235
+ that for every iterator `j` in the range \[`first`, `last`),
 
 
236
 
237
+ ``` cpp
238
+ bool(invoke(comp, invoke(proj, *i), invoke(proj, *j)))
239
+ ```
240
+
241
+ is `false`. Returns `last` if `first == last`.
242
+
243
+ *Complexity:* Exactly max(`last - first - 1`, 0) comparisons and twice
244
+ as many projections.
245
 
246
  ``` cpp
247
  template<class ForwardIterator>
248
  constexpr pair<ForwardIterator, ForwardIterator>
249
  minmax_element(ForwardIterator first, ForwardIterator last);
 
257
  minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
258
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
259
  pair<ForwardIterator, ForwardIterator>
260
  minmax_element(ExecutionPolicy&& exec,
261
  ForwardIterator first, ForwardIterator last, Compare comp);
262
+
263
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
264
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
265
+ constexpr ranges::minmax_result<I>
266
+ ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
267
+ template<forward_range R, class Proj = identity,
268
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
269
+ constexpr ranges::minmax_result<borrowed_iterator_t<R>>
270
+ ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
271
  ```
272
 
273
+ *Returns:* `{first, first}` if \[`first`, `last`) is empty, otherwise
274
+ `{m, M}`, where `m` is the first iterator in \[`first`, `last`) such
275
+ that no iterator in the range refers to a smaller element, and where `M`
276
+ is the last iterator[^5] in \[`first`, `last`) such that no iterator in
277
+ the range refers to a larger element.
278
 
279
+ *Complexity:* Let N be `last - first`. At most
280
+ $\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ comparisons and
281
+ twice as many applications of the projection, if any.
282